Algorithms COMP6466

Course overview

Course description

This course deals with the study of algorithms for solving practical problems as well as the data structures used in their implementation. A large variety of algorithms are candidates for study including greedy algorithms, dynamic programming, divide and conquer, exhaustive search, graph algorithms, heaps, network flow algorithms, string matching and so on. Analysis of the resource requirements of algorithms will be an important issue of study.

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 ofefficient 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, 2nd Edition, 2002.

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.