This course deals with the study of algorithms for solving practical problems, and of the data structures used in their implementation. Detailed analysis of the resource requirements of algorithms will be an important issue.

A large variety of algorithms are candidates for study. These include, but are not limited to, the following: greedy algorithms, dynamic programming, divide-and-conquer, exhaustive search, graph algorithms, advanced data structures such as binomial heaps and Fibonacci heaps, network flow algorithms, algorithms for string matching, parallel algorithms, heuristics and approximation algorithms, and an introduction to intractability. As well as studying the implementation, the mathematical tools used to study the resource usage of algorithms will be considered.

On completion of this course the student will:

• Have a thorough understanding of a variety of algorithms, including linear selection, minimum spanning trees, single source shortest path, Huffman coding, etc, with real-life applications and the resource requirements.
• Be able to apply the algorithmic techniques including dynamic programming, greedy policy, and divide-and-conquer, to solve some practical problems.
• Be able to analyze time and space complexities of algorithms.
• Have some experience in the design and implementation of algorithms for practical problems, using languages like C, C++.

Assignments (40%); Final Exam (60%)

Thirty one-hour lectures and four two-hour tutorial/laboratory sessions.

COMP2100 or COMP2500 or COMP1140; 6 units of 2000-level COMP courses or enrollment in BComptlSci; and 6 units of 2000-level MATH courses or COMP2600.

The following text book will be used for this course:

• Cormen, T., Leiserson, C.E. Rivest. R.L. & Stein, C. Introduction to Algorithms MIT Press, 3rd Edition, 2009.

The following reference books are recommended for this course:

• Baase, S. & Van Gelder, Allen Computer Algorithms - Introduction to Design and Analysis by Addison-Wesley, 3rd Edition, 2000.
• Sedgewick, Robert Algorithms in C , 3rd Edition, 2002.
• Aho, Alfred V., Hopcroft, John E., & Ullman, Jeffrey D. The Design and Analysis of Computer Algorithms , Addison-Wesley, 1974.
• Kleinberg, John & Tardos, Eva Algorithms Design, Addison-Wesley, 2005.