Algorithms COMP3600

Course overview

Course description

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.

Rationale

Aims to give the students an exposure to a variety of algorithms that can be used for solving real life problems. This should help them acquire the necessary skills to recognize problem scenarios where such algorithms can be used, to modify an existing algorithm or develop a new one to provide a solution, and to also show that the given problem does not lead itself to an efficient solution, if such be the case. It will also provide further experience in the development of efficient software for nontrivial purposes.

Ideas

This course will carry the main responsibility for:

• item exposing the students to a variety of algorithms that can be used to solve real problems, as well as doing a detailed resource analysis of each one
• giving them examples of where such algorithms can be usedgiving them the knowledge of how to design, select and evaluate new algorithms,
• introducing them to the principle of NP-completeness and showing them different ways in which a given problem can be shown to be intractable.

Topics

The topics covered could include the following:

• Mathematical analysis tools
• Data Structures: Hash tables, binary search trees, red-black trees, etc.
• Graph algorithms: minimum spanning trees, shortest paths, minimum cut and maximum flow,  transitive closure and topological sort.
• General algorithm paradigms, such as greedy algorithms and dynamic programming.
• Analysis of algorithm resource usage, by counting and recurrence  techniques.

Technical skills

Will acquire a good knowledge of a variety of algorithms that have real-life applications; will further develop skills in the analysis of algorithms;  will get some hands-on experience in the design, analysis and implementation of algorithms for some nontrivial problems; will get an exposure to the theory of intractability; will get some experience in how one can go about showing that certain problems are intractable.

Textbooks

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.

Workload

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