Skip Navigation | ANU Home | Search ANU | Search FEIT | Feedback

COMP3600: Algorithms

(6 units) Group C

Thirty lectures and four two-hour tutorial/laboratory sessions

Lecturer: Dr Weifa Liang

Prerequisites

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

Syllabus

This course deals with the study of algorithms for solving practical problems and the 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, minimum spanning trees, 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, 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 the 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 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:

• expose 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
• give them examples of where such algorithms can be used
• provide them the knowledge of how to design, select and evaluate new 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, minimum cut and maximum flow, transitive closure, and topological sort
• General algorithm paradigms: divide-and-conquer, greedy algorithms, and dynamic programming
• Data structures: hash tables, heaps, binary search trees, and red-black trees
• Analysis of algorithm resource usage, by 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 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.

Objectives

Upon completion of this course, the student will:

have a thorough understanding of a variety of algorithms with real-life applications and the resource requirements \biggsgrad{4}

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++ \biggsgrad{1,3,4}

have a basic understanding of the theory of intractability and have some experience in proving that certain kinds of problems are intractable \biggsgrad{1,8}

Assessment

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 10:35:20:35 weighting for the quizzes, assignments, and the examinations. The final mark is calculated using the following formula:

Total = 0.1Q+0.35A+0.2M+0.35F,

subject to necessary adjustment during the School examination meeting. The departmental policy on plagiarism will be enforced.

Recommended Reading

• T. H. Cormen , C. E. Leiserson , R. L. Rivest  and C. Stein. Introduction to Algorithms. 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.