Friday 22 February 2013

CS9212 DATA STRUCTURES AND ALGORITHMS


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