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

III (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)

VIII. (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)