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 — 20%.
- Assignments — 20%
- Final Exam — 60%
Textbook
"Algorithm Design" by Tardos and Kleinberg, Addison Wesley.
Time table
- Lecture: Thursdays 4:00pm - 6:00pm, SIT Lecture Theater
- Lab: Thursdays 6:00pm - 7:00 pm, SIT Lab 115
Other Resources
Please go to the E-Learning site to access assignments, marks and the discussion board for this unit.
Schedule
| Date | Topic | Reference | Slides/Scribbles | Python | Tutorial |
|---|---|---|---|---|---|
| Mar 08 | Stable matching | 1.1 | slides | source | tut 1 |
| Basics of algorithm analysis | 2 | scribbles | interaction | ||
| March 15 | Basics of algorithm analysis, cont. | 2 | slides | source | tut 2 |
| Priority queues | 2.5 | slides scribbles |
interaction | ||
| March 22 | Breath First Search | 3 | slides | source | tut 3 |
| Depth First Search | scribbles | interaction | |||
| March 29 | Greedy algorithms: Interval scheduling, | 4.1,4.2 | slides | source | tut 4 |
| Kurskal's and Dijkstra's algorithm | 4.5,4.6 | scribbles | interaction | ||
| April 5 | Divide and conquer: Sorting | 5.1-2 | slides | code | tut 5 |
| integer multiplication, selection | 5.5 | scribbles | comparison | ||
| April 19 | Dynamic programming: weighted interval scheduling, | 6.1-2 | slides | code | tut 6 |
| longest increasing subsequence, knapsack | 6.4 | scribbles | interaction | ||
| April 26 | Dynamic programming: Nim, | slides | code | tut 7 | |
| RNA secondary structure | 6.5 | scribbles | interaction | ||
| May 3 | Network flows: Definition, FF algorithm | 7.1,2 | slides | tut 8 | |
| Bipartite matching | 7.5 | scribbles | |||
| May 10 | Network flows applications: Disjoint paths | 7.6 | slides | tut 9 | |
| airline scheduling, project selection | 7.9,7.11 | scribbles | |||
| May 17 | Reductions | 8.1-2 | slides | tut 10 | |
| NP-completeness | 8.3-4 8.6 | scribbles | |||
| May 24 | Weak NP-hardness, coNP | 8.8-9 | slides | tut 11 | |
| PSPACE | 9.1-3 | scribbles |