Introduction
This unit provides an introduction to the design and analysis of algorithms. The main aims are (i) to learn how to develop algorithmic solutions to computational problem and (ii) to develop understanding of algorithm efficiency and the notion of computational hardness.
Assumed Knowledge
This course assumes basic knowledge of discrete math. In particular, students should be familiar with graphs, Big O notation, and induction.
Assessment
- Quizzes (best 10 out of 12) — 20%
- Assignments (best 10 out of 12) — 20%
- Final Exam — 60%
Textbook
"Algorithm Design" by Tardos and Kleinberg, Addison Lecture.
Time table
- Main lecture: Mondays 10:00am - noon in Merewether Lecture Theatre 2 (Rm 136)
- Advanced lecture: Mondays 4:00pm - 5:00pm in New Law School Seminar 030
Other Resources
Please go to the E-Learning site to the full UoS outline, access assignments, quizzes, and your marks for this unit.
Schedule
| Date | Topic | Reference | Slides | Scribbles | Python code | Python output | Tutorial |
|---|---|---|---|---|---|---|---|
| July 30 | Algorithm analysis review | 2-1,2,4,5 | introduction analysis | scribbles | find_window |
interaction plot | problem set 1 |
| (Adv lecture) | Stable matching | 1.1 | stable matching | ||||
| August 6 | Graph algorithms | 3 notes |
graphs | scribbles | bfs | interaction | problem set 2 |
| (Adv lecture) | DFS on directed graphs | 3 | directed graphs | scribbles | |||
| August 13 | Greedy algorithms | 4.1,2,5,6 | greedy | scribbles | problem set 3 | ||
| (Adv lecture) | Fibonacci heaps | 3 | fibonacci | ||||
| August 20 | Divide and conquer | 5.1,2,5 | dnc | problem set 4 | |||
| (Adv lecture) | Fast Fourier Transform | 5.6 | fft | ||||
| August 27 | Dynamic programming | 6.1,2,4 | slides | scribbles | problem set 5 | ||
| (Adv lecture) | Bellman-Ford | 6.8,10 | slides | scribbles | |||
| September 3 | Dynamic programming 2 | 6.5,6 | slides | scribbles | nim | problem set 6 | |
| (Adv lecture) | Optimal binary search trees | scribbles | |||||
| September 10 | Network flows | 7.1,2,5 | slides | scribbles | problem set 7 | ||
| (Adv lecture) | Augmenting path rules | 7.3 | - | scribbles | |||
| September 17 | Network flows applications | 7.6,7,9,11 | slides | scribbles | problem set 8 | ||
| (Advanced) | Karger's algorithm | 13.2 | - | scribbles | |||
| October 8 | NP-completeness | 8.1,2,3,4.6 | slides | scribbles | problem set 9 | ||
| (Adv lecture) | PRIMES ni NP | notes | - | scribbles | |||
| October 15 | Weak NP-hardness, coNP | 8.8-9 | slides | scribbles | problem set 10 | ||
| (Adv lecture) | Polynomial time hierarchy | - | - | scribbles | |||
| October 22 | Coping with NP-hardness | 10.1,2 11.3 12.1,2,4 | slides | scribbles | problem set 11 | ||
| (Adv lecture) | Kernelization | notes | scribbles |