CSC752 - Advanced Algorithm & Analysis

Course Outcomes
After completing this course, the students should be able to:
1. recognize a collection of important and practical algorithms.
2. apply complexity analysis techniques for assessing the efficiency of algorithms.
3. select and apply efficient algorithms to solve computational problems.
4. identify and modify existing algorithms to design appropriate solutions to solve similar but more complex problems.

Course Description
Algorithmic problems form the core of computer science, and thus algorithm design and analysis is among its most fundamental elements. This course focuses on the clean mathematical modeling of real-world problems, identifying the appropriate advanced algorithm design techniques to these problems, and analyzing these algorithms. This is done by exploring a variety of real-world problems in various applications.
The algorithms topics and applications include divide and conquer, greedy algorithms, dynamic programming, network flow, NP-complete, approximation and other advanced algorithms.

Syllabus & Scheme of Work

1. Introduction
• Fundamentals of Algorithm Analysis
• Asymptotic Notation
• Basic Asymptotic Efficiency Classes
2. Divide and Conquer
• Mergesort
• Closest Pair of Points
3. Dynamic Programming
• Coin Changing
• Longest-Common-Subsequence Problem
• Floyd & Warsall's Algorithms
• Knapsack
4. Greedy Algorithms
• Coin Changing
• Kruskal's & Prim's Algorithms
• Dijkstra's Algorithm
5. Network Flow
• Network Flow Problem
• Ford-Fulkerson Algorithm & Max-Flow/Min-Cut Problem
• Network Flow Applications
6. Approximation Algorithms
• Traveling Salesman Problem
• Knapsack Problem
• Other Applications
7. Other Advanced Algorithms & Problems
• Local Search
• Randomized Algorithms
• Parallel Algorithms

References

Johnsonbaugh R. & Schaefer M., Algorithms, Pearson Prentice Hall, 2004.

Kleinberg, J. & Tardos, E. Algorithm Design, Addison Wesley, 2005.

Levitin, A. Introduction to Design and Analysis of Algorithms. Addison Wesley, 2003.

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. Introduction to Algorithms, 2nd Ed, McGraw-Hill, 2001.

Sedgewick, R. & Flajolet, P. An Introduction to the Analysis of Algorithms. Addison-Wesley Longman Publishing Co., Inc. 1996

Sipser, M. Introduction to the Theory of Computation, Brooks/Cole Pub. Co., 1996.

Garey, M.R. & Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman Publishing, 1979.

Hochbaum, D. (Ed.). Approximation Algorithms for NP-Hard Problems, PWS, 1997

Motwani, R. & Raghavan P. Randomized Algorithms, Cambridge University Press, 1995.