INF2-IADS: Schedule and Course Materials for Semester 2 (Spring 2025)
| Week (commencing) | Date | Event | Lecturer | Topic | Reading | |
| 1 (13 Jan) | Tue 14 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 17 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 (20 Jan) | Tue 21 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 24 Jan | Lecture 19 | Mary | Lecture cancelled due to storm | |||
| Mon 20, Fri 24 Jan | Lab 1 | 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 (27 Jan) | Tue 28 Jan | Lecture 20 | Mary | Sequence alignment: [KT] 6.6 [CLRS] 14.4 [Roughgarden] 17.1 The original "Seam Carving" paper is here. | ||
| Fri 31 Jan | Lecture 21 | Mary | Lecture 21 - Probabilistic FSMs and Maximum Likelihood Estimation | No texts for this topic! | ||
| Multiple dates | Tutorial 1 | |||||
| Fri 31 onwards | Quiz 3 | DUE 12 NOON Wed 5th Feb (to be completed) | ||||
| 4 (3 Feb) | Tue 4 Feb | Lecture 22 | John | Lecture 22 - Context-Free Languages and Grammars Pre-recorded video version (including song) | ||
| Fri 7 Feb | Lecture 23 | John | 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 2 | |||||
| Mon 22, Fri 26 Jan | Lab 6 | Solution (in .txt) | ||||
| 5 (10 Feb) | Tue 11 Feb | Lecture 24 | John | Lecture 24 - Predictive Parsing
| ||
| Fri 14 Feb | Lecture 25 | Mary | 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. | ||
| 6 (24 Feb) | Tue 25 Feb | Lecture 26 | Mary |
[KT] 8.3. | ||
| Wed 26 | Coursework 2 released | DUE 12 NOON Wednesday 12th March (to be submitted) | ||||
| Multiple dates | Tutorial 3 | |||||
| Mon 22, Fri 26 Jan | Drop-in Labs | (for assistance with coursework 2) | ||||
| Wed 26 onwards | Quiz 3 | DUE 12 NOON Mon 3rd March (to be completed) | ||||
| 7 (3 Mar) | Tue 4 Mar | Lecture 27 | Mary | Lecture 27 - Dealing with NP-completeness (Approximation Algorithms) | [KT] 13.3, 13.3 OR [CLRS] 35.4 | |
| Mon 22/Fri 26 Jan | Drop-in Labs | (for assistance with coursework 2) | ||||
| 8 (10 Mar) | Tue 11 Mar | Lecture 28 | Mary | Lecture 28 - Dealing with NP-completeness (Recursive backtracking) | No texts for this topic. | |
| Multiple dates | Tutorial 4 | |||||
| Mon 22, Fri 26 Jan | Drop-in Labs | (for assistance with coursework 2) | ||||
| 9 (17 Mar) | Tue 18 Mar | Lecture 29 | John | M. Sipser, Introduction to the Theory of Computation (3rd ed.), Chapter 3. Available online from UoE library | ||
| 10 (24 Mar) | Tue 25 Mar | Lecture 30 | John | |||
| Multiple dates | Tutorial 5 | |||||
| Wed 26 onwards | Quiz 5 | DUE 12 NOON Mon 31st March (to be completed) |