Graduate Comprehensive Examination
Algorithms
Coordinator:
William Shoaff
<wds@cs.fit.edu>.
For this exam you should be able to analyze a give 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).
Topics
- Time and Space complexity
- Mathematical Tools
- Growth Rate: O, Omega, and Theta notations
- Properties of Logarithms
- Summing Sequences
- Binomial Coefficients
- Factorials
- Harmonic Numbers
- Generating Functions
- Recurrence Equations
- Building them for recursive algorithms
- Solving recurrences
- Sorting Algorithms (classification, analysis and comparison)
- Searching Algorithms (linear, binary, finite-state-machine based, etc.)
- Graph Algorithms (minimal spanning trees, shortest path, topological
sorting, breadth-first and depth-first)
- Divide and Conquer Algorithms (description, properties, and example problems)
- Greedy Algorithms (features, limitations, analysis, and example problems)
- Numerical Algorithms
References
- Brassard and Bratley, Prentice Hall, 1988.
Algorithmics Theory and Practice
- Brassard and Bratley, Prentice Hall, 1996.
Fundamentals of Algorithmics
- Corman, Leiserson, and Rivest, McGraw-Hill, 1990.
Introduction to Algorithms
- Graham, Knuth, and Patashnik, Addison Wesley, 1989.
Concrete Mathematics
- Sedgewick, Addison-Wesley, 1992.
Algorithms in C++
- Sedgewick and Flajolet, Addison Wesley, 1996.
Analysis of Algorithms
- Weiss, Addison Wesley, 1999, Data Structures & Algorithm Analysis in
JAVA (or C++)
Last modified: Mon Sept 27 1999