You are here: Computer Science > Courses > Level-3 > aa

Advanced Algorithms (3301 and 7301)

The development of a sound theoretical understanding of advanced algorithms and practical problem solving skills using them. Advanced algorithm topics chosen from: Dynamic Programming, Linear Programming, Matching, Max Flow / Min Cut, P and NP, Approximation Algorithms, Randomized Algorithms, Computational Geometry.

Course Details

• Course Code: COMP SCI 3301 and 7301
• Coordinating Unit: School of Computer Science
• Course Coordinator: Dr. Mingyu Guo
• Term: Semester 1
• Location/s: North Terrace Campus
• Units: 3
• Contact: Up to 3 hours per week
• Available for Study Abroad and Exchange: Y
• Prerequisites: COMP SCI 2201

Course Learning Outcomes

1. Students should develop a sound theoretical understanding of advanced algorithms and practical problem solving skills using them.
2. Students should develop basic knowledge of a wide range of advanced algorithm design techniques including dynamic programming, linear programming, approximation algorithms, and randomized algorithms.
3. Students should develop basic advanced algorithm analysis skills for analyzing the approximation ratio of approximation algorithms and the probability of randomized algorithms.
4. Students should gain a good understanding on a wide range of advanced algorithmic problems, their relations and variants, and application to real-world problems.

Resources (Recommended)

Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press
Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press 1995, isbn 0-521-47465-5
Vijay V. Vazirani: Approximation algorithms. Springer 2001, isbn 978-3-540-65367-7, pp. I-IXI, 1-378

Assessment Summary

3 assignments worth 30% (each worth 10% of the final mark)

Final Exam worth 70%

For P/G stduents at least one assignment will contain a component that would require a deeper understanding to the learnt knowledge than U/G students.

Students have to achieve at least 40% of the exam marks, and overall at least 50% in order to pass the course.

Course Schedule by Week

1. Course Overview, Dynamic programming, Pseudo polynomial time approximation
2. Linear programming 1, Simplex method, Dual form
3. Linear programming 2, Maximum flow min cut theorem, Ford-Fulkerson algorithm
4. Maximum matching, Integrality theorem
5. Approximation algorithms 1, Bin packing, Vertex cover
6. Approximation algorithms 2, Travelling salesman problem (TSP)
7. Fixed parameter algorithms, Vertex cover, Euclidean TSP
8. Randomized algorithms 1, Inequalities and sampling algorithms
9. Randomized algorithms 2, K-SAT
10. Computational Geometry, Graham algorithm
11. Algorithmic game theory, Stable matching, Selfish flow, Kidney exchange
12. Exam Reviewing

Course Offerings

• Semester 1, 2016, Main offering