## 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.

##### Topics

- 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)

##### References

- 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++)