SYLLABUS
CS 2251 DESIGN AND ANALYSIS OF
ALGORITHMS 3 1 0 4
UNIT I
9
Algorithm Analysis – Time Space Tradeoff – Asymptotic
Notations – Conditional asymptotic notation – Removing condition from the
conditional asymptotic notation - Properties of big-Oh notation – Recurrence
equations – Solving recurrence equations – Analysis of linear search.
UNIT II 9
Divide and Conquer: General Method – Binary Search –
Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method –
Container Loading – Knapsack Problem.
UNIT III 9
Dynamic Programming: General Method – Multistage
Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack –
Travelling salesperson problem .
UNIT IV 9
Backtracking: General Method – 8 Queens
problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack
problem.
UNIT V 9
Graph Traversals – Connected Components – Spanning
Trees – Biconnected components – Branch and Bound: General Methods (FIFO &
LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.
TUTORIAL = 15 Total = 60
TEXT BOOK:
1.
Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran,
Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units
II to V)
2.
K.S. Easwarakumar, Object Oriented Data Structures
using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
REFERENCES:
1.
T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C.
Stein, "Introduction to Algorithms", Second Edition, Prentice Hall of India
Pvt. Ltd, 2003.
2. Alfred
V. Aho, John E. Hopcroft and Jeffrey D.
Ullman, "The Design and Analysis of Computer
Algorithms", Pearson Education,
1999.
No comments:
Post a Comment