COMP3600: Algorithms
The standard algorithms course: proving correctness and bounding running time, not just producing code that happens to pass the sample cases. The back third is NP-completeness, aimed at recognising when a problem is hard rather than searching forever for a clever solution.
Credit units
6 units
Instructor
Prof. Liam O'Connell
Prerequisites
COMP2100 and MATH1013, or equivalent.
Learning objectives
By the end of this course, students will be able to:
- Prove an algorithm's correctness rather than test it into plausibility
- Bound an algorithm's running time with the right notation
- Choose between greedy, divide-and-conquer and dynamic programming for a new problem
- Recognise when a problem is NP-complete instead of searching forever for a clever solution
Assessment
- Problem sets25%Five problem sets of proof and analysis questions.
- Assignment — algorithm design25%Design, prove correct and analyse an algorithm for a novel problem.
- Final exam50%Closed-book exam covering design, analysis and NP-completeness.
Problem sets and the assignment are submitted as written proofs; the exam is in-person and closed-book.
Timetable
Lecture: Tue 1pm–2pm, Manning Clark 2
2 tutorial option(s) — pick one on the timetable page after enrolling.
- Tutorial A: Wed 3pm–4pm, CSIT N202
- Tutorial B: Thu 2pm–3pm, CSIT N202
4/4 courses added.