INF2-IADS: Schedule and Course Materials for Semester 2 (Spring 2027)
| Week (commencing) | Date | Event | Lecturer | Topic | Reading |
| 1 (11 Jan) | Tue 12 Jan | Lecture 16 | Mary |
| [CLRS] (ed 4), 22.2, 22.3, 22.5 OR [Roughgarden] 9.1, 9.2, and (faster Heap impl) 10.4, 10.5
|
| Fri 15 Jan | Lecture 17 | Mary | Lecture 17 - Introduction to Greedy Algorithms new lecture - no pre-recorded video | [CLRS] (ed 4) 15.1 (general), 22.4 (proof of Dijkstra) [Roughgarden] 13.1 (general), 9.3 (proof of Dijkstra) | |
| 2 (18 Jan) | Tue 19 Jan | Lecture 18 | Mary | [Roughgarden] 16.4, "general principles of DP" [Kleinberg and Tardos] 6.2 J.W. Wright "The change-making problem", J ACM 1975. | |
| Fri 22 Jan | Lecture 19 | Mary | The original "Seam Carving" paper is here. | ||
| InfBase for help | Labsheet 4 | Lab Sheet 4: Greedy Algorithms (and some dynamic programming) dijkstra.py (as txt), coin_changing.py (as txt), 7nodes (as .txt) solutions (as .txt): coin_changing_sol, dijkstra_sol | |||
| 3 (25 Jan) | Multiple dates | Tutorial 1 | Tutorial 6 - Greedy and Dynamic Programming Solutions, slides | ||
| Tue 26 Jan | Lecture 20 | Mary | Sequence alignment: [KT] 6.6 [CLRS] 14.4 [Roughgarden] 17.1 | ||
| Fri 29 Jan | Lecture 21 | Mary | Lecture 21 - Probabilistic FSMs and Maximum Likelihood Estimation | No texts for this topic! | |
| InfBase for help | Labsheet 5 | Solution (in .txt) | |||
| available Wed 27 | Quiz 3 | DUE 12 NOON Mon 1st Feb (to be completed) | |||
| 4 (1 Feb) | Multiple dates | Tutorial 2 | Tutorial 7 - Dynamic Programming Solutions, slides | ||
| Tue 2 Feb | Lecture 22 | John | Lecture 22 - 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 | |
| Fri 5 Feb | Lecture 23 | John | Other resources as listed on slides. | ||
| 5 (8 Feb) | Multiple dates | Tutorial 3 | Tutorial 8 - CFGs and Parsing Algorithms Solutions, slides | ||
| Tue 9 Feb | Lecture 24 | John | Lecture 24 - Predictive Parsing
| ||
| Fri 12 Feb | Lecture 25 | Mary | Exam prep lecture (11am): pre-recorded video from 2020/21 Hackerdashery video for inspiration | [CLRS] Chapter 34 intro, 34.1, 34.2, 34.3 (early part) OR [Roughgarden] 19.2, 19.3, 19.5, 19.6 OR [KT] 8.1, 8.2, 8.4. Scott Aaronson "P vs NP" paper | |
| Fri 12 Feb | Coursework 2 released | DUE 12 NOON Tuesday 9th March (to be submitted) | |||
| 6 (22 Feb) | Tue 23 Feb | Lecture 26 | Mary |
[KT] 8.3. | |
| Fri 26 Mar | Lecture 27 | Mary | Lecture 27 - Dealing with NP-completeness (Approximation Algorithms) | [KT] 13.3, 13.3 OR [CLRS] 35.4 | |
| Available Fri 26 | Quiz 4 | DUE 12 NOON Wed 3rd March (to be completed) | |||
| 7 (1 Mar) | Multiple dates | Tutorial 4 | Tutorial 9 - NP-completeness and Approx Algorithms Solutions, slides | ||
| Tue 2 Mar | Lecture 28 | Mary | Lecture 28 - Dealing with NP-completeness (Recursive backtracking) | No texts for this topic. | |
| Fri 5 Mar | Lecture 29 | John | M. Sipser, Introduction to the Theory of Computation (3rd ed.), Chapter 3. Available online from UoE library | ||
| multiple dates | Drop-in Lab (AT-4.12) | (for assistance with coursework 2) | |||
| 8 (8 Mar) | Multiple dates | Tutorial 5 | Tutorial 10 - Register machines and computability Solutions | ||
| Tue 9th Mar | Lecture 30 | John | |||
| multiple dates | Drop-in Lab (AT-4.12) | (for assistance with coursework 2) | |||
| Wed 10th onwards | Quiz 5 | DUE 12 NOON Mon 15th March (to be completed) |