CS
2251 DESIGN AND ANALYSIS OF ALGORITHMS - Syllabus
L T P C
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 PERIODS
TEXT BOOKS:
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