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