10-04-2017, 08:51 PM
BRANCH: COMPUTER SCIENCE AND ENGINEERING
CS 010 405- MICROPROCESSOR SYSTEMS (CS)
Part A
Answer all questions.
Each Question Carries 3 marks
1. What is microprocessor? Give the power supply and Clock frequency of 8085
2. Define instruction cycle, machine cycle and T-state
3. Explain the signals HOLD, READY and SID.
4. What is synchronous data transfer?
5. What is the use of modem control unit in 8251?
Part B
Answer all questions
Each question carries 5 marks
6. Compare CALL and PUSH instructions
7. Difference between memory mapped I/O and peripheral I/O
8. Explain briefly about the different types of interrupts in 8085
9. Briefly explain the DMA data transfer
10. Discuss the features of 8251
Part C
Answer all questions
Each question carries 12 marks
11. Explain the addressing modes of 8085 with example
or
12. Explain the different types of instruction in 8085
13. Explain the various machine cycles supported by 8085
or
14. Write a program to arrange 'n' numbers in ascending order
15. With neat sketch, explain the function of Programmable Interrupt Controller
or
16. Explain hardware and software interrupts in 8085 microprocessor
17.Explain any of the modes of 8255 in detail
or
18. Differentiate synchronous and asynchronous data transfer schemes
19. With neat sketch, explain the functions of 8251
or
20. Design an interface circuit needed to connect DIP switch as an input device and display the value of the key pressed using a 7 segment LED display. Using 8085 system, write a program to implement the same.
IT/CS 604 ANALYSIS AND DESIGN OF ALGORITHMS
I. (a) Explain dynamic programming with an example.
(b) Solve:
T (n) = 2T (%) + n3.
© Differentiate between binomial heap and Fibonacci heap.
(d) What is amortized time analysis?
(e) Explain the strongly connected component of a directed graph with an example.
(f) Write Wars hall s algorithm for transitive closure.
(g) Distinguish between NP hard and NP complete problem.
(h) Explain first fit decreasing strategy for solving bin packing problem.
PART B
(4 x15= 60)
II. Explain the various criteria used for analyzing algorithm with suitable examples. (15)
OR
II (a) Explain Recursion tree. (5 marks)
(b) Explain the different asymptotic notations used for specifying the growth rate of functions. (10 marks)
IV. Explain any one searching algorithm with an example. Also derive the worst case and average case time complexity. (15 marks)
OR
V Write the merge sort algorithm and analyze the worst case and average case time complexity. (15 marks
VI (a) Explain transitive closure of a binary relation. (5 marks)
(b) Explain any one algorithm for finding the all pair shortest path in graphs. (10 marks)
OR
VII. What is a binary search tree? Explain an algorithm for constructing an optimal binary search tree. Analyze its complexity.(15 marks)
VII. (a) Explain approximation of algorithms.(5 marks)
(b) Write and explain Widgerson s graph coloring algorithm. (10 marks)
OR
IX. Explain the three possible strategies for travelling salesman s problem. (15 marks)