Reg. No.:

END-SEMESTER EXAMINATION (DECEMBER – 2014)

SEMESTER – III (SESSION – 2014-15)

( B.Tech.)

Subject Code:CS0207 Duration: 3 hours

Subject: Computer organization and Archetecture Max. Marks: 100

Instructions

·  All Questions are compulsory

·  The Question paper consists of 2 sections - Part A contains 10 questions of 2 marks each. Part B consists of 5 questions of 16 marks each.

·  There is no overall choice. Only Part B question include internal choice.

PART – A

(2 * 10 = 20 Marks)

PART – B

(16 * 5 = 80 Marks)

11 (a)

OR (first unit)

11(b)

12(a)

OR (second unit)

12(b)

13(a)

OR( Third unit)

13(b

14(a)

OR( forth unit)

14(b

15(a)

OR (fifth unit)

15(b)

PURPOSE

This course will provide an understanding of how to write algorithms for various problems and do an analysis of the same

INSTRUCTIONAL OBJECTIVES

1. Divide and Conquer , Dynamic Programming techniques

2. Backtracking , NP complete problems

3. Various analysis of algorithms

UNIT 1 ANALYSIS OF ALGORITHM / 9
Introduction - Algorithms – Pseudo code for algorithms – present – future. Mathematics for / Algorithms –
Definitions – Notation and Basic results – Asymptotic Notation- Mathematical Induction / – Analysis of
Algorithms - Recurrence relations.
UNIT 2 DIVIDE AND CONQUER METHOD / 9
General Method - Binary Search – Finding Maximum and Minimum – Merge Sort – Quick Sort Greedy
Method – General Method – KnapSack Problem – Minimum Spanning Tree Algorithm – Single Source Shortest
Path Algorithm.
UNIT 3 DYNAMIC PROGRAMMING / 9

General Method–Multistage Graph – All Pairs Shortest Path Algorithm – 0/1 Knapsack Problem – Traveling Salesman Problem - Basic search techniques and traversal techniques –bi-connected components – Depth First Search – Breadth First Search.

UNIT 4 BACKTRACKING / 9
The General Method – 8-Queens Problem- Sum of Subsets – Graph Coloring- Hamiltonian Cycle-Knapsack
Problem – Branch and Bound Method – 0/1 Knapsack Problem – Traveling Salesman Problem
UNIT 5 P and NP / 9

Polynomial time – Nondeterministic Algorithms and NP – Reducibility and NP completeness – NO complete Problems – More on NP completeness. Case studies

TOTAL 45

TEXT BOOKS

1.  E.Horowitz , Sahni & Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”, Galgotia Publications,1997

2.  Richard Johnsonbaugh , Marcus Schaefer , “ Algorithms “ , Pearson Education, 2006 3rd edition (chapter 1,2,10)

33

REFERENCE BOOKS

1.  Aho, Ullman & Hopcraft, “The Design and Analysis of Algorithms”, Pearson Education, 2001

2.  S.E.Goodman , S.T.Hedetniemi , “Introduction to the Design and Analysis of Algorithms”, McGraw Hill , 2002

3.  Sara Baase , “Computer Algorithms - Introduction to design and analysis”, Pearson Education, 1998