Study Guide for the Algorithms Comprehensive Examination
Coordinator: William Shoaff, .
For this exam you should be able to analyze a given algorithm. You may need to understand what the algorithm does, study its time complexity, study its space complexity, calculate number of time a specific operation is performed, and/or compare it to other algorithm(s). Requisite mathematical background is expected.
- Time and Space complexity
- Mathematical Tools
- Growth Rate: O, Omega, and Theta notations
- Properties of Logarithms
- Summing Sequences
- Inductive proof technique
- Recurrence Equations
- Setting up for recursive algorithms
- Solving recurrences
- Divide and Conquer Algorithms (description, properties, and example algorithms including those for sorting)
- Greedy Algorithms (features, limitations, analysis, and example algorithms)
- Dynamic Programming Algorithms (features, limitations, analysis, and example algorithms)
- Backtracking algorithms with pruning, or branch and bound.
- Graph Algorithms (Djikstra's shortest path finding algorithm, topological sorting, breadth-first and depth-first search, finding strongly connected components)
- Basics of complexity theory (NP-completeness)
- Class notes of CSE5210: cs.fit.edu/~dmitra/Algorithms
- Corman, Leiserson, and Rivest, McGraw-Hill, 1990. Introduction to Algorithms
- Brassard and Bratley, Prentice Hall, 1996. Fundamentals of Algorithmics
- Sedgewick and Flajolet, Addison Wesley, 1996. Analysis of Algorithms
- Weiss, Addison Wesley, 1999, Data Structures & Algorithm Analysis in JAVA (or C++)