 |
Comprehensive Examination Syllabus
Syllabus
- General Search Methods: Review of Depth First Search and Breadth First Search; Back-track search; branch-and-bound.
- Basic Strategies: Greedy algorithms; divide-and-conquer; dynamic programming; randomized algorithms.
- Basic Graph Problems: Shortest Path; Minimum Spanning Tree; Connectivity; Biconnectivity; Strong Connectivity; Transitive Closure; Augmenting Path algorithms (bipartite mathching, network flow, minimum cut problems)
- Sorting, Searching and Selection: Binary Search; Basic sorting algorithms (insertion sort, merge sort, quick sort, heap sort, radix sort); Linear time selection; Lower bound techniques (decision trees and adversary arguments)
- Algebraic Problems: Greatest Common Divisor; Matrix Multiplication; Polynomial Evaluation; Fast Fourier Transform and applications.
Background Material
- Data Structures: linked lists, heaps, binary search trees, hash tables, B-trees, disjoint set union-find.
- Elementary Discrete Mathematics: Basic enumeration and probability, recurrence relations, basic definitions concerning sets, relations and functions.
- Analytical notation: Big O, SZ, O notation.
References
- Corman, Leiserson, Rivest and Stein, Introduction to Algorithms, McGraw-Hill
- Horowitz and Sahani, Fundamentals of Computer Algorithms (Chapters 6,7,8)
- Aho, Hopcroft and Ullman The Design and Analysis of Computer Algorithms
Reference (1) covers all the required material and background except for "General Search Methods", which can be found in more than adequate detail in (2). Reference (3) provides an alternative source for many of the topics.
| |
