CS9212 DATA STRUCTURES AND ALGORITHMS
UNIT I COMPLEXITY ANALYSIS & ELEMENTARY DATA STRUCTURES
Asymptotic notations – Properties of big oh notation – asymptotic notation with several
parameters – conditional asymptotic notation – amortized analysis – NP-completeness –
NP-hard – recurrence equations – solving recurrence equations – arrays – linked lists –
trees.
UNIT II HEAP STRUCTURES
Min-max heaps – Deaps – Leftist heaps –Binomial heaps – Fibonacci heaps – Skew
heaps - Lazy-binomial heaps.
UNIT III SEARCH STRUCTURES
Binary search trees – AVL trees – 2-3 trees – 2-3-4 trees – Red-black trees – B-trees –
splay trees – Tries.
UNIT IV GREEDY & DIVIDE AND CONQUER
Quicksort – Strassen’s matrix multiplication – Convex hull - Tree-vertex splitting – Job
sequencing with deadlines – Optimal storage on tapes
UNIT V DYNAMIC PROGRAMMING AND BACKTRACKING
Multistage graphs – 0/1 knapsack using dynamic programming – Flow shop scheduling
– 8-queens problem – graph coloring – knapsack using backtracking
REFERENCES:
1. E. Horowitz, S.Sahni and Dinesh Mehta, Fundamentals of Data structures in C++,
Galgotia, 1999.
2. E. Horowitz, S.Sahni and S. Rajasekaran, Computer Algorithms / C++, Galgotia,
1999.
3. Adam Drozdex, Data Structures and algorithms in C++, Second Edition, Thomson
learning – vikas publishing house, 2001.
4. G. Brassard and P. Bratley, Algorithmics: Theory and Practice, Printice –Hall, 1988.
5. Thomas H.Corman, Charles E.Leiserson, Ronald L. Rivest, ”Introduction to
Algorithms”, Second Edition, PHI 2003.
No comments:
Post a Comment