Course title: Advanced Algorithm Analysis

• Course code: CS-702
• Credit Hours: 3
• Prerequisite: Data Structures and Algorithms

Course Outline:

• Advanced algorithm analysis including the introduction of formal techniques and the underlying mathematical theory.
• NP-completeness.
• Search Techniques.
• Randomized Algorithms.
• Heuristic and Approximation Algorithms.
• Topics include asymptotic analysis of upper and average complexity bounds using big-O, little-o, and theta notation.
• Fundamental algorithmic strategies (brute-force, greedy, divide-and-conquer, backtracking, branch-and-bound, pattern matching, and numerical approximations).
• Standard graph and tree algorithms.
• Standard complexity classes, time and space trade offs in algorithms
• Using recurrence relations to analyze recursive algorithms
• Non-computable functions
• The halting problem, and the implications of non-computability.

Course Objectives:

Upon completion of the course, students should be able to explain the mathematical concepts used in describing the complexity of an algorithm, and select and apply algorithms appropriate to a particular situation.

Reference materials:

1. Vijay V. Vazirani,Approximation Algorithms, Springer, 2004.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,Introduction to Algorithms, 3rd edition, Published by MIT Press, 2009.
3. Mikhail J. Atallah Contributor Mikhail J. Atallah,Algorithms and Theory of Computation Handbook, CRC Press, 1998.

Useful Online Resources:

1. VisuAlgo
2. MIT Introduction to Algorithms
3. Part 1 of Coursera course on Algorithms by Robert Sedgewick
4. Part 2 of Coursera course on Algorithms by Robert Sedgewick
5. Book Mathematics for Computer Science

6. How fast do algorithms improve