# COMP3600/COMP6466: Algorithms

*(6 units)* Group C

Twenty-eight lectures and six two-hour tutorial/laboratory sessions

Lecturers: Prof Weifa Liang, Prof John Lloyd and A/Prof Peter Strazdins

## Prerequisites

COMP1110 or or COMP1140 or COMP1600; and 6 units of 2000-level COMP courses and 6 units of 2000-level MATH courses or COMP2600.

## Syllabus

This course deals with the study of algorithms for solving practical problems and data structures used in the implementations of algorithms. 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 paradigm, basic graph algorithms like BFS and DFS trees, topological sort, minimum spanning tree algorithms, single source shortest path algorithms, all pairs of shortest paths algorithms, advanced data structures such as hash tables, binary search trees, and red-black trees, disjoint-set, etc. The mathematical tools used to study the resource usage of algorithms will be considered too.

## Description

A good knowledge of algorithms and algorithmic theory is essential for finding efficient solutions to real life problems, and for determining whether such a solution exists in the first place. This course aims to expose students to a variety of algorithms that have practical applications, while conducting detailed analysis of the resource requirements required by the algorithms.

## 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 necessary skills to recognize problem scenarios where such algorithms can be used, to modify an existing algorithm or develop a new one for new problems, and to show that the given problem does not lead itself to an efficient solution, if such is 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:- expose students to a variety of algorithms that can be used to solve real problems, as well as doing a detailed resource analysis of algorithms
- give them examples where such algorithms can be used
- provide them the knowledge of how to design, select and evaluate algorithms

## Topics

The topics covered could include the following:- Graph algorithms: connected components, minimum spanning trees, a single source shortest path, all pairs of shortest paths, transitive closure, and topological sort
- General algorithm paradigms: divide-and-conquer, greedy algorithms, and dynamic programming
- Data structures: hash tables, heaps, binary search trees, red-black trees, and disjoint-sets, DFS and BFS
- Analysis of algorithm resource usage, counting and recurrence techniques

## 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 non-trivial 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.

## Objectives

Upon completion of this course, the student will:

## Assessments

There will be**four**quizzes (Q),

**two**assignments (A),

**one**mid-semester exam (M), and

**one**final exam (F). The overall assessment will be based on a 15:35:20:30 weighting for the quizzes, assignments, and the examinations. The final mark is calculated, using the following formula:

Total = 0.15Q+0.35A+0.2M+0.3F,

subject to necessary adjustment during the School examination meeting. In order to pass the course, the final marks for both assignments and examinations are no less than 40% of their corresponding final mark allocations , i.e., your final score on assignments and examination are no less than 14/35 and 20/50, respectively, and all assignments and examinations are compulsory to pass the course. The school policy on plagiarism will be enforced. The university wide late submission policy will be applied, i.e., 5% late submission penalty will be applied per working day (from Monday to Friday, public holidays are exception)

## Recommended Reading

- T. H. Cormen , C. E. Leiserson , R. L. Rivest and C. Stein.
*Introduction to Algorithms (Textbook)*. MIT Press, 3rd Edition, 2009. - John Kleinberg and Eva Tardos.
*Algorithms Design*. Addison-Wesley, 2005. - Sara Baase and Allen Van Gelder.
*Computer Algorithms -- Introduction to Design and Analysis*. Addison-Wesley, 3rd Edition, 2000. - Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani.
*Algorithms*. McGraw Hill Higher Education, 2008. - Robert Sedgewick.
*Algorithms in C*. Addison-Wesley, 3rd Edition, 2002. - Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman.
*The Design and Analysis of Computer Algorithms*. Addison-Wesley, 1974.