Below you can find the schedule for Semester 1. You may also access the material from last year if you would like a preview of what's coming, but do keep in mind that this will eventually be replaced by new material - similar but updated.
Week (commencing) | Date | Event | Lecturer | Topic | Reading |
1 (18 Sept) | Tue 19 Sept | Lecture 1 | Aris and John | Algorithms Illuminated 1.1., 10.1. | |
Thu 21 Sept | Lecture 2 | John | Lecture 2 - Inefficient vs. efficient algorithms | CLRS 2.1, CLRS 2.3, CLRS 31.6 (second half) Algorithms Illuminated 1.4, 1.5. KT 2.1, 2.4. (Merging two sorted lists), 5.1. (only page 210, but read through 5.1 if you are interested). | |
2 (25 Sept) | Mon 25 Wed 27 Sept | Lab 1 | Lab Sheet 1: Getting started in Python | ||
Tue 26 Sept | Lecture 3 | John | Algorithms Illuminated 2 KT 2.2, 2.4 CLRS 3 (does everything) GGT 3.3, 3.4 | ||
Thu 28 Sept | Lecture 4 | John | As for Lecture 3 | ||
3 (02 Oct) | Mon 02 Wed 04 Oct | Lab 2 | queue.txt (.py file not accepted by OpenCourse - sorry for inconvenience!) | ||
Multiple dates | Tutorial 1 | ||||
Tue 3 Oct | Lecture 5 | John | Roughgarden 1.5, 1.6 KT 2.4/4.1 CLRS 2.2 | ||
Thu 5 Oct | Lecture 6 | John | CLRS 10.2, 10.3 Python documentation: Data model (just 3.1) | ||
4 (09 Oct) | Multiple dates | Tutorial 1 | |||
Tue 10 Oct | Lecture 7 | John | Array expansion: Stacks + queues: | ||
Thu 12 Oct | Lecture 8 | John | Roughgarden 12.1-12.4 (recommended!), GTG 10.1, 10.2, Sedgewick 3.4 | ||
5 (16 Oct) | Tue 17 Oct | Lecture 9 | John | Sedgewick 3.2 (first half) and 3.3 (second half) CLRS 12.1-3, 13.1-3 | |
Thu 19 Oct | Lecture 10 | John | |||
6 (23 Oct) | Multiple Dates | Lab 3 | Drop-in for coursework 1 | ||
Multiple Dates | Tutorial 3 | ||||
Tue 24 Oct | Lecture 11 | Aris | Lecture 11 - Heapsort (.key file, better animations) Recording from previous years | CLRS 6.1-6.4 KT 2.5 (uses min-heap) Roughgarden 10.2, 10.3.1, 10.5 (caution: RG uses min-heap and the terms "Heapify" for Build-Max-Heap and implements Min-Heapify as part of "ExtractMin"). | |
7 (30 Oct) | Multiple Dates | Lab 4 | Drop-in for coursework 1 | ||
Tue 31 Oct | Lecture 12 | Aris | Lecture 12 - Heap operations and Priority Queues Lecture 12 - Heap operations and Priority Queues (.key file, better animations) Recording from previous years | CLRS 6.5 KT 2.5 (uses min-heap) Roughgarden 10.2, 10.5 (caution: RG uses min-heap and the terms "Heapify" for Build-Max-Heap and implements Min-Heapify as part of "ExtractMin"). | |
8 (6 Nov) | Multiple Dates | Lab 5 | * | Drop-in for coursework 1 | |
Multiple Dates | Tutorial 4 | * | The Master Theorem and Heaps Solutions | ||
Tue 7 Nov | Lecture 13 | Aris | Lecture 13 - Quicksort and the limitations of sorting algorithms Recording from previous years | CLRS 7.1-7.3, 8.1. Roughgarden 5.1-5.4, 5.6 | |
9 (13 Nov) | Tue 14 Nov | Lecture 14 | Aris | Lecture 14 - Graphs, DFS, and BFS Lecture 14 - Graphs, DFS, and BFS (.pdf) Recording from previous years | KT 3.2., 3.3. Roughgarden 8.1., 8.2., 8.4. CLRS 20.1., 20.2., 20.3. |
10 (20 Nov) | Multiple Dates | Tutorial 5 | * | ||
Tue 21 Nov | Lecture 15 | Aris | Lecture 15 - Testing Bipartiteness and Topological Sort Lecture 15 - Testing Bipartiteness and Topological Sort (.pdf) Recording from previous years | KT 3.4., 3.6. Roughgarden 8.5. CLRS 20.4. Notes: Roughgarden and CLRS do not cover testing for bipartiteness. They also approach topological sort via DFS. | |
MATERIAL FROM PREVIOUS YEARS | |||||
10 (20 Nov) | varies | Tutorial 5 | * | Quicksort and BFS | |
Tue 21 Nov | Lecture 15 | Mary | CLRS 22.4 |