CS2253 COMPUTER ORGANIZATION AND ARCHITECTURE APRIL/MAY 2010 ANNA UNIVERSITY QU

[jagathesh]

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010
Fourth Semester
Computer Science and Engineering
CS2253 — COMPUTER ORGANIZATION AND ARCHITECTURE
(Common to Information Technology)
(Regulation 2008)
Time: Three hours Maximum: 100 Marks
Answer ALL Questions
PART A — (10 × 2 = 20 Marks)
1. Distinguish between autoincrement and autodecrement addressing mode.
2. Compare RISC with CISC architecture.
3. Under what situations the micro program counter is not incremented after a
new instruction is fetched from micro program memory?
4. What are the relative merits of horizontal and vertical microinstruction
format?
5. What is pipelining and what are the advantages of pipelining?
6. List the key aspects in gaining the performance in pipelined systems.
7. How many memory chips are needed to construct 2 M × 16 memory system
using 512 K × 8 static memory chips?
8. What is virtual memory and what are the benefits of virtual memory?
9. What is meant by bus arbitration?
10. Name and give the purpose of widely used bus standard.
PART B — (5 × 16 = 80 Marks)
11. (a) (i) Describe the role of system software to improve the performance of
a computer.         [8]
(ii) Design a 4-bit adder/subtracter circuit using full adders and explain
its function.         [8]
Or
(b) (i) What are the special registers in a typical computer? Explain their
purposes in detail.         [8]
(ii) Design a 4-bit fast adder and explain its function in detail.         [8]
12. (a) (i) Draw and explain the block diagram of a complete processor.         [6]
(ii) Briefly describe the design of a hardwired control unit.         [10]
Or
(b) (i) Explain the basic organization of a microprogrammed control unit
and the generation of control signals using microprogram.         [12]
(ii) What are the advantages and disadvantages of hardwired and
microprogrammed control?         [4]
13. (a) (i) Describe the role of cache memory in pipelined system.         [8]
(ii) Discuss the influence of pipelining on instruction set design.         [8]
Or
(b) What is instruction hazard? Explain the methods for dealing with the
instruction hazards.         [16]
14. (a) (i) What are the different secondary storage devices? Elaborate on any
one of the devices.         [8]
(ii) Explain how the virtual address is converted into real address in a
paged virtual memory system.         [8]
Or
(b) (i) Explain approaches for addressing multiple-module memory
systems with suitable diagrams.         [6]
(ii) Briefly describe magnetic disk principles and also the organization
and accessing of data on a disk.         [10]
15. (a) (i) Describe the hardware mechanism for handling multiple interrupt
requests.         [8]
(ii) What are handshaking signals? Explain the handshake control of
data transfer during input and output operation.         [8]
Or
(b) (i) What are the needs for input-output interface? Explain the
functions of a typical 8-bit parallel interface in detail.         [10]
(ii) Describe the USB architecture with the help of a neat diagram.         [6]

[jagathesh]

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What do you mean by linear search?
2. What is the properties of big-Oh notation.
3. What greedy algorithms?
4. What Knapsack problem?
5. What is traveling salesperson problem?
6. What do you mean by multistage graphs?
7. State the general backtracking method?
8. What is graph cloning?
9. What is spanning tree? Give an example.
10. What is NP Completeness?
PART B — (5 × 16 = 80 marks)
11. (a) (i) Define Asymptotic notations. Distinguish between Asymptotic notation and conditional asymptotic notation.         [10]
(ii) Explain how the removing condition is done from the conditional Asymptotic notation with an example.         [6]
Or
(b) (i) Explain how analysis of linear search is done with a suitable illustration.         [10]
(ii) Define recurrence equation and explain how solving recurrence equations are done.         [6]
12. (a) What is divide and conquer strategy and explain the binary search with suitable example problem.
Or
(b) Distinguish between Quick sort and Merge sort, and arrange the following numbers in increasing order using merge sort. (18, 29, 68, 32, 43,37, 87, 24, 47, 50)
13. (a) (i) Explain the multistage graph problem with an example.         [8]
          (ii) Find an optimal solution to the knapsack instance n = 7, m= 15 (p1, p2, p3, ....p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, w3, ... w7) (2, 3, 5, 7, 1, 4, 1)         [8]
Or
(b) Describe binary search tree with three traversal patterns? Give suitable example with neat diagram for all three traversal of binary search tree..         [16]
14. (a) (i) How does backtracking work on the 8 Queens problem with suitable example?         [8]
(ii) Explain elaborately recursive backtracking algorithm?         [8]
Or
(b) What is Hamiltonian problem? Explain with an example using backtracking.         [16]

15. (a) Write a complete LC branch-and-bound algorithm for the job sequencing with deadlines problem. Use the fixed tuple size formulation.         [16]
Or
(b) Write a non-deterministic algorithm to find whether a given graph contains a Hamiltonian cycle.        [16]