| Course Code: CS203 Course Name: Algorithms and Data Structures Prerequisites: NIL Syllabus: Models of Computation; representations of algorithms; the concept of problem size; performance of algorithms: space and time complexity measures, asymptotics, worst case and average case analyses, lower and upper bounds. Operations on data; elementary Data structures: linked lists, arrays, matrices, stacks, queues, binary trees, trees, heaps; tree traversals; linear search and binary search; priority queues: lists and heaps. Sorting algorithms: insertion-sort, bubble-sort, selection sort, shellsort, quicksort, mergesort, heapsort; Analysis of sorting algorithms; lower bound for sorting; selection. Search Trees: binary search trees, (a,b)-trees, red-black trees, AVL trees, splay trees, B-trees. Graphs: representations, depth first search, breadth first search, connectivity. Hashing: separate chaining, linear probing, quadratic probing. The disjoint-set union-find data structure (without the amortized analysis). Strings, suffix arrays, tries. Texts: 1. M. A. Weiss, Data Structures and Algorithm Analysis in C++, 4th Edition, Pearson, 2014. 2. T. H. Cormen, C. F. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, Prentice Hall of India, 2009. References: 1. A. V. Aho, J. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison- Wesley, 1983. 2. A. V. Aho, J. Hopcroft, J. D. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974. |