INF2IADS: 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 BellmanFord 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  ContextFree Languages and Grammars Prerecorded 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 Contextfree 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 NPcompleteness Lecture 24  Introduction to NPcompleteness (.key file, better animations)  Kleinberg and Tardos 8.1 (up to page 454), 8.4.  
Fri 16 Feb  Lecture 10  Aris  Lecture 25  NPcompleteness of Vertex Cover Lecture 25 NPcompleteness 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  NPcompleteness: A closer look Lecture 26  NPcompleteness: 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) PolynomialTime Approximation Schemes Lecture 28 (Fully) PolynomialTime 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  SeamCarving by Dynamic Programming (with seamcarving demo video) video playlist (parts 12), 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 35), 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  Contextfree Languages and Grammars  
4  varies  Tutorial 7  *  
Tues 6 Feb  Lecture 22  John  Parsing for Contextfree 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  *  Dropin for coursework 2  
Tues 5 Mar  Lecture 25  Mary  Satisfiability and NPcompleteness  CLRS 34.4, 34.5 OR "Algorithms Illuminated" Sects 22.3, 22.4, 22.5  
8  varies  Lab 10  *  Dropin for coursework 2  
varies  Tutorial 9  *  NPcompleteness  
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 