INF2-IADS: Schedule and Course Materials for Semester 2 (Spring 2024)
| Week (commencing) | Date | Event | Lecturer | Topic | Reading | |
| 1 (15 Jan) | Tue 16 Jan | Lecture 1 | Aris | Lecture 16a - Semester 2 Introduction Lecture 16 - Greedy Algorithms: Interval Scheduling Lecture 16 - Greedy Algorithms: Interval Scheduling (.key file, better animations) | Kleinberg and Tardos 4.1 (online version from the library), 5.1. (printed version). | |
| Fri 19 Jan | Lecture 2 | Aris | Lecture 17 - Greedy Algorithms: Dijkstra's algorithm for shortest paths Recordings | Kleinberg and Tardos 4.4 (online version from the library), 5.4. (printed version). | ||
| 2 (22 Jan) | Tue 23 Jan | Lecture 3 | Aris | Lecture 18 - Dynamic Programming: Weighted Interval Scheduling Lecture 18 - Dynamic Programming: Weighted Interval Scheduling (.pptx) | Kleinberg and Tardos 6.1 | |
| Fri 26 Jan | Lecture 4 | Aris | Lecture 19 - Dynamic Programming: Subset Sum and Knapsack Lecture 19 - Dynamic Programming: Subset Sum and Knapsack (.key file, better animations) | Kleinberg and Tardos 6.4 Roughgarden 16.5 | ||
| Mon 22 Fri 26 Jan | Lab 6 | |||||
| 3 (29 Jan) | Tue 30 Jan | Lecture 5 | Aris | Lecture 20 - Dynamic Programming: The Bellman-Ford Algorithm for Shortest Paths | Kleinberg and Tardos 6.8.(see also 6.10 if you are interested in how to find negative cycles, when they exist). CLRS 22.1. Roughgarden 18.1, 18.2. | |
| Fri 2 Feb | Lecture 6 | John | Lecture 21 - Context-Free Languages and Grammars Pre-recorded video version (including song) | M. Sipser, Introduction to the Theory of Computation (3rd ed.), Section 2.1. Available online from UoE library. Wikipedia article on Context-free grammar Other resources as listed on Slide 21. | ||
| Multiple dates | Tutorial 1 | |||||
| 4 (5 Feb) | Tue 6 Feb | Lecture 7 | John | |||
| Fri 9 Feb | Lecture 8 | John | ||||
| Multiple dates | Tutorial 2 | |||||
| Mon 22 Fri 26 Jan | Lab 6 | Lab Sheet 5: Dynamic Programming Solutions | ||||
| 5 (12 Feb) | Tue 13 Feb | Lecture 9 | Aris | Lecture 24 - Introduction to NP-completeness Lecture 24 - Introduction to NP-completeness (.key file, better animations) | Kleinberg and Tardos 8.1 (up to page 454), 8.4. | |
| Fri 16 Feb | Lecture 10 | Aris | Lecture 25 - NP-completeness of Vertex Cover Lecture 25 NP-completeness of Vertex Cover (.key file, better animations) | M. Sipser, Introduction to the Theory of Computation (3rd ed.), Section 7.5, proof of Thm 7.44. Available online from UoE library. | ||
| 6 (26 Feb) | Tue 27 Feb | Lecture 11 | Aris | Lecture 26 - NP-completeness: A closer look Lecture 26 - NP-completeness: A closer look (.key file, better animations) | Kleinberg and Tardos 8.3., 8.10. Roughgarden Chapters 19, 23 (read through). | |
| Multiple dates | Tutorial 3 | |||||
| 7 (4 Mar) | Tue 5 Mar | Lecture 12 | Aris | Lecture 27 - Greedy Approximation Algorithms Lecture 27 - Greedy Approximation Algorithms (.key file, better animations) | Kleinberg and Tardos 11.1 Williamson and Shmoys, The Design of Approximation Algorithms, 1.1, 2.3. Available online from UoE library. | |
| 8 (11 Mar) | Tue 12 Mar | Lecture 13 | Aris | Lecture 28 - (Fully) Polynomial-Time Approximation Schemes Lecture 28- (Fully) Polynomial-Time Approximation Schemes(.key file, better animations) | Kleinberg and Tardos 11.8 Williamson and Shmoys, The Design of Approximation Algorithms, 3.1. Available online from UoE library. | |
| Multiple dates | Tutorial 3 | |||||
| Mon 11 Fri 15 Mar | Lab 7 | |||||
| 9 (18 Mar) | Tue 19 Mar | Lecture 14 | John | Lecture 29 - Intro to Computability Theory | M. Sipser, Introduction to the Theory of Computation (3rd ed.), Chapter 3. Available online from UoE library | |
| 10 (25 Mar) | Tue 26 Mar | Lecture 15 | John | Lecture 30 - Unsolvable Problems |
MATERIAL FROM LAST YEAR
| Week | Date | Event | Lecturer | Topic | Reading |
| 1 | Tue 16 Jan (2024) | Lecture 16 | Mary | Graphs III: Dijkstra's Algorithm video playlist, slides |
|
| Thu 18 Jan | Lecture 17 | Mary | Introduction to Dynamic Programming |
| |
| 2 | varies | Lab 6 | * | Lab sheet 4: Dynamic Programming in Python, solutions: coin_changing_sol.py, editdist_sol.py | |
| Tue 23 Jan | Lecture 18 | Mary | Seam-Carving by Dynamic Programming (with seam-carving demo video) video playlist (parts 1-2), seam carving video, slides | CLRS 15.3, 15.4 (though they refer to problems we don't consider) GTG 13.3.2 (somewhat relevant) The original "Seam Carving" paper is here. | |
| Thu 25 Jan | Lecture 19 | Mary | Edit distance by Dynamic Programming video playlist (parts 3-5), slides | ||
| 3 | varies | Lab 7 | * | Lab sheet 5: Dijkstra's algorithm in Python | |
| varies | Tutorial 6 | * | solutions, slides, Edit Distance trick (Raul Garcia) Jiaheng's slides part 1 (from 2022, please ignore Floyd), part 2 (knapsack) | ||
| Tues 30 Jan | Lecture 20 | Mary | Probabilistic Finite State Machines and the Viterbi Algorithm | ||
| Thu 1 Feb | Lecture 21 | John | Context-free Languages and Grammars | ||
| 4 | varies | Tutorial 7 | * | ||
| Tues 6 Feb | Lecture 22 | John | Parsing for Context-free Languages: The CYK Algorithm | ||
| Thu 8 Feb | Lecture 23 | John | LL(1) Predictive Parsing | ||
| 5 | Tues 13 Feb | Mary (CANCELLED due to strike) | |||
| Thu 15 Feb | Mary (CANCELLED due to strike) | ||||
| FLW | Mon 19 - Fri 23 Feb | NO COURSE ACTIVITIES | |||
| 6 | varies | Tutorial 8 | * | ||
| Tues 27 Feb | Lecture 24 | Mary | P and NP | CLRS 34 (intro), 34.1, 34.2, 34.3 OR "Algorithms Illuminated" Chap 19, Sects 22.1, 22.2 | |
| 7 | varies | Lab 9 | * | Drop-in for coursework 2 | |
| Tues 5 Mar | Lecture 25 | Mary | Satisfiability and NP-completeness | CLRS 34.4, 34.5 OR "Algorithms Illuminated" Sects 22.3, 22.4, 22.5 | |
| 8 | varies | Lab 10 | * | Drop-in for coursework 2 | |
| varies | Tutorial 9 | * | NP-completeness | ||
| Tues 12 Mar | Lecture 28 | John | Introduction to Computability Theory | ||
| 9 | Tues 20 Mar | Lecture 29 | John | Unsolvable Problems | |
| 10 | varies | Tutorial 10 | * | ||
| Tues 27 Mar | Lecture 30 | Mary | Revision Lecture
Sample paper and solutions |