Computer Science


Advanced Design and Analysis of Algorithms: COMPSCI 720 Semester 1, City Campus


This course is aimed at graduate level students as preparation for research work in algorithms development. It is also useful for students intending to work in the general area of theoretical computer science, and to mathematics students interested in computational combinatorics.

Content

Course content varies substantially each year. Please contact the course coordinator/director (Mark Wilson) if you have questions. The course has been taught by Michael Dinneen and Mark Wilson for many years.

In 2017 the course will be in two parts. The first part is taught by Mark Wilson and will cover connections between algorithms and complexity, on the one hand, and economics on the other. More specifically, topics from computational social choice theory. Even more specifically, we will cover algorithms for 1- and 2-sided matching (e.g. house allocation, assigning students to schools). There will be 3 assignments. The second part is taught by Michael Dinneen and will have three parts, each with its own assignment. We start with the study of basic combinatorial algorithms (how to enumerate objects and rank/hash them). Then we study some advanced topics in graph algorithms such as linear-time dynamic programs for graphs of bounded treewidth, branchwidth and pathwidth. Finally we will cover fixed-parameter techniques for coping with NP-hard problems.

Assessment

Six assignments (written/programming): 40%

Final exam: 60%

Top


Apply now!


Handbook

Postgraduate study options

Computer Science Blog



Please give us your feedback or ask us a question

This message is...


My feedback or question is...


My email address is...

(Only if you need a reply)

A to Z Directory | Site map | Accessibility | Copyright | Privacy | Disclaimer | Feedback on this page