Algorithms 1 & 2
Lecture notes and example sheets
- Printed notes for Algorithms 1 © Frank Stajano 2023, and short handout
- Printed notes for Algorithms 2
- Example sheets 1, 2, 3 for Algorithms 1 (the same exercises as for 2022/23)
- Example sheet 4, sheet 5, sheet 6 for Algorithms 2
Announcements, Q&A, tick submission
— MoodleSchedule
This is the planned lecture schedule. It will be updated as and when actual lectures deviate from schedule. Slides will be uploaded the night before a lecture.
| 2. Sorting | |
| Lecture 01 | 2.1 Insertsort |
| Lecture 02 |
2.3 Big-O notation
2.4 The cost of sorting 2.6–2.7 Binary insertsort, selectsort |
| Lecture 03 |
2.11 Quicksort 2.9 Mergesort 2.10 Heapsort |
| Lecture 04 |
2.14 Faster sorting: couting sort, bucket sort, radix sort 2.13 Stability Sorting algorithms compared 2.12 Median and order statistics using quicksort |
| Example sheet 1 [pdf]
Compulsory tick: mergesort, due 5 Feb Optional: sortbound. Why doesn't the Ω(n log n) bound apply to countingsort? |
|
| 3. Algorithm design | |
| Lecture 05 | 3.1 Dynamic programming |
| Lecture 06 | Dynamic programming examples |
| Lecture 07 |
3.2 Greedy algorithms |
|
First half of example sheet 2 [pdf]
Optional tick: huffman Compulsory tick: resalloc, due 19 Feb |
|
| 4. Data structures (intro) | |
| Lecture 08 |
4.1 Memory and pointers 4.1–4.2 List, tree, stack, queue, dictionary 4.7 Hash tables 4.9 Priority queues |
| Rest of example sheet 2 [pdf] | |
| 5. Graphs and path finding | |
| Lecture 09 |
5, 5.1 Graphs (14:27)
5.2 Depth-first search (11:37)
5.3 Breadth-first search (6:43)
|
| Lecture 10 |
5.4 Dikstra's algorithm (15:25) plus proof (24:01)
|
| Lecture 11 |
5.5 Algorithms and proofs (9:29)
5.6 Bellman-Ford (12:13)
|
| Lecture 12 |
5.7 Dynamic programming (13:06)
5.8 Johnson's algorithm (13:43)
|
|
Example sheet 4 [pdf]
Optional tick: bfs-all from ex4.q6
Optional challenge: chatgpt-bfs
Optional assignment: grade-chatgpt
Optional tick: bf-cycle from ex4.q19
|
|
| 6. Graphs and subgraphs | |
| Lecture 13 |
6.1 Flow networks (9:31)
6.2 Ford-Fulkerson algorithm (21:55)
|
| Lecture 14 |
6.3 Max-flow min-cut theorem (19:38)
|
| Lecture 15 |
6.4 Matchings (11:01)
6.7 Topological sort (14:16)
|
| Lecture 16 | |
|
Example sheet 5 [pdf]
Compulsory tick: max-flow, due 11 March
|
|
| 7. Advanced data structures | |
| Lecture 16 (ctd) |
7.1 Aggregate analysis (8:56)
|
| Lecture 17 |
7.2 Amortization: introduction (10:41)
7.3 Amortization: definition (10:59)
7.4 Potential functions (14:17)
|
| Lecture 18 |
4.7 Hash tables revisited 4.8 Binomial heap 7.5 Three priority queues (18:26)
|
| Lecture 19 |
7.6 Fibonacci heap (18:13)
|
| Lecture 20 |
7.8 (continued)
7.7 Implementing the Fibonacci heap
7.9 Disjoint sets (18:07)
|
| Lecture 21 | Review of amortized analysis |
|
Example sheet 6 [pdf]
Optional tick: dis-set from ex6.q12
Optional tick: fib-heap
|
|
| 4. Data structures (ctd) | |
| Lecture 21 ctd. |
4.3 Binary search trees |
| Lecture 22 |
4.4 2-3-4 trees 4.6 B-trees |
| Lecture 23 | 4.5 Red-black trees |
| Example sheet 3 [pdf] | |
| Epilog | |
| Lecture 24 |
What's examinable Proof by induction / bfs-all challenge |