Syllabus

• Introduction: data types, data structures and abstract data types; algorithmics and asymptotics.
• Basic data types: lists, stacks, queues, mappings.
• Trees and Sets: basic operations on trees and sets, binary trees, dictionary, hashing, priority queues, heaps, binary search trees, balanced tree implementations of sets.
• Graphs: directed graphs (the single source shortest paths problem, the all pairs shortest path problem, traversals, directed acyclic graphs, strong components), undirected graphs (minimum cost spanning trees, traversals, articulation points and bi-connected components, graph matching).
• Algorithm analysis techniques: efficiency of algorithms, analysis of recursive programs, recurrence equations and some general solutions.
• Algorithm design techniques: divide and conquer algorithms, dynamic programming, greedy algorithms, local search algorithms.
• Sorting: a sorting model, simple sorting schemes, quicksort, heapsort, bin sorting.
• Data structures and algorithms for external storage: external sorting, external search trees.

Recommended Reading

• Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D., Data Structures and Algorithms, Addison Wesley, Reading, Mass., 1987. PDF

• Cormen, Thomas V., Leiserson, Charles E., Rivest, Ronald R., Introduction to Algorithms, MIT Press 1990. Newer editions (like the 2001 edition) of this book are even better. PDF

• Preiss, Bruno R., Data Structures and Algorithms with Object-Oriented Design Patterns in C++ John Wiley, 1998, available for reading online.

• Knuth, D. E., The Art of Computer Programming Vol I: Fundamental Algorithms, Addison Wesley, Reading, Mass., 1968 (republished).
• Knuth, D. E., The Art of Computer Programming Vol III: Sorting and Searching, Addison Wesley, Reading, Mass., 1968. (republished)
• Wirth, N., Algorithms + Data Structures = Programs, Prentice Hall, Englewood Cliffs, N.J, 1976.