Introduction - what's the book about?, mathematics review, a brief introduction to recursion, C++ at a glance; algorithm analysis - mathematical background, model, what to analyze, running time calculations; lists, stacks, and queues - abstract data types, the list ADT, the stack ADT, the queue ADT; trees - preliminaries, binary trees, the search tree ADT - binary search trees, AVL trees, splay trees, tree traversals, B-trees; hashing - general idea, hash function, open hashing, closed hashing, rehashing, extendible hashing; priority queues (heaps) - model, simple implementations, binary heap, applications of priority queues, d-heaps, leftist heaps, skew heaps, binomial queues; sorting - preliminaries, insertion sort, a lower bound, shellsort, heapsort, Mergesort, quicksort, sorting large records, a general lower bound for sorting, bucket sort, external sorting; the disjoint set ADT - equivalence relations, the dynamic equivalence problem, basic data structure, smart union algorithms, path compression, worst case for union-by-rank and path compression, an application; graph algorithms - definitions, topological sort, shortest-path algorithms, network flow problems, minimum spanning tree, applications of depth-first search, introduction to NP-completeness; algorithm design techniques - greedy algorithms, divide and conquer, dynamic programming, randomized algorithms, backtracking algorithms; amortized analysis - an unrelated puzzle, binomial queues, skew heaps, Fibonacci heaps, splay trees.
