INF2-IADS: Schedule and Course Materials for Semester 1 (Autumn 2024)

Below you can find the schedule and materials for Semester 1.
The video recordings of this year's lectures will all be available via the course's Learn page, but you may also find the lecture recordings from previous years helpful - perhaps more polished and better edited than most live lectures, and they also feature music and songs :-) You can access these in either of two ways:

Go to the IADS 2021-22 channel on Media Hopper Create, and select the playlist for the lecture you want, OR
Go to media.ed.ac.uk, log on to Media Hopper Create using the person icon at top right, and the 'Recording from previous years' links below will then take you directly to the playlists.

Week (commencing)	Date	Event	Lecturer	Topic	Reading (For details of the textbooks referenced here, choose 'Resource List' from the navigation menu on the right.)
1 (16 Sept)	Tue 17 Sept	Lecture 1	John	Lecture 0 - Course admin Lecture 1 - Overview of course content Recording from previous years	Algorithms Illuminated 1.1., 10.1. CLRS 1
1 (16 Sept)	Thu 19 Sept	Lecture 2	John	Lecture 2 - Inefficient vs. efficient algorithms Recording from previous years	CLRS 2.1, CLRS 2.3, CLRS 31.6 (second half) Algorithms Illuminated 1.4, 1.5. KT 2.1, 2.4. (Merging two sorted lists), 5.1. (only page 210, but read through 5.1 if you are interested).
2 (23 Sept)	Mon 23 Wed 25 Sept	Lab 1		Lab Sheet 1: Getting started in Python Sheet 1 solutions Lab Sheet 2: Writing programs in Python Sheet 2 solutions
	Tue 24 Sept	Lecture 3	John	Lecture 3 - Asymptotic notation: Little o and omega Recording from previous years	Algorithms Illuminated 2 KT 2.2, 2.4 CLRS 3 (does everything) GGT 3.3, 3.4
	Thu 26 Sept	Lecture 4	John	Lecture 4 - More asymptotics: Big O, Omega, and Theta Recording from previous years	As for Lecture 3
3 (30 Sept)	Mon 02 Wed 04 Oct	Lab 2		Lab Sheet 3: Classes and more Supporting files: numbers1.txt, numbers2.txt, numbers3.txt, numbers4.txt, numbers5.txt Sheet 3 solutions
	Multiple dates	Tutorial 1		Tutorial 1 - Asymptotic Notation Solutions, slides
	Tue 1 Oct	Lecture 5	John	Lecture 5 - Asymptotic analysis of sorting algorithms Recording from previous years	Roughgarden 1.5, 1.6 KT 2.4/4.1 CLRS 2.2
	Thu 3 Oct	Lecture 6	John	Lecture 6 - Representation of program data in memory Recording from previous years	CLRS 10.2, 10.3 Python documentation: Data model (just 3.1)
4 (07 Oct)	Multiple dates	Tutorial 2		Tutorial 2 - Analysis of Algorithms Solutions, slides
	Tue 8 Oct	Lecture 7	John	Lecture 7 - Abstract data types: Lists, stacks, queues Recording from previous years	Array expansion: GTG 5.1-5.4, Sedgewick 1.4, CLRS 17.4 (3rd ed) or 16.4 (4th ed) Stacks + queues: GTG 6.1, 6.2, 7.1, Sedgewick 1.3, CLRS 10
	Thu 10 Oct	Lecture 8	John	Lecture 8 - Sets, dictionaries and hashing Recording from previous years	Roughgarden 12.1-12.4 (recommended!), GTG 10.1, 10.2, Sedgewick 3.4
5 (14 Oct)	Tue 15 Oct	Lecture 9	John	Lecture 9 - Balanced trees Recording from previous years	Sedgewick 3.2 (first half) and 3.3 (second half) CLRS 12.1-3, 13.1-3
5 (14 Oct)	Thu 17 Oct	Lecture 10	John	Lecture 10 - Divide-conquer-combine and the Master Theorem Recording from previous years
6 (21 Oct)	Multiple Dates	Lab 3		Drop-in for coursework 1
	Multiple Dates	Tutorial 3		Tutorial 3 - Data structures for lists and sets Solutions, slides
	Tue 22 Oct	Lecture 11	Mary	Lecture 11 - The Heap data structure Recording from previous years	CLRS 6.1-6.4 KT 2.5 (uses min-heap) [AI] (Roughgarden) 10.1, 10.2, 10.5 (major differences: [AI] uses min-heap, but also uses "Heapify" to refer to our Build-Max-Heap, and implements Min-Heapify as part of "ExtractMin").
7 (28 Oct)	Multiple Dates	Lab 4		Drop-in for coursework 1
7 (28 Oct)	Tue 29 Oct	Lecture 12	Mary	Lecture 12 - Buildheap and HeapSort Recording from previous years	CLRS 6.5 KT 2.5 (uses min-heap) [AI] (Roughgarden): 10.3, 10.5 (major differences: RG uses min-heap, uses "Heapify" for our Build-Max-Heap, and implements Min-Heapify as part of "ExtractMin").
8 (4 Nov)	Multiple Dates	Lab 5	*	Drop-in for coursework 1
	Multiple Dates	Tutorial 4	*	Tutorial 4 - The Master Theorem and Heaps Solutions, slides
	Tue 5 Nov	Lecture 13	Mary	Lecture 13 - Quicksort Recording from previous years	CLRS 7.1-7.3. Roughgarden 5.1, 5.3 (5.2 - but this is different to our Partition)
9 (11 Nov)	Tue 12 Nov	Lecture 14	Mary	Lecture 14 - Graphs 1: BFS and DFS Recording from previous years	KT 3.2., 3.3. Roughgarden Ch 7, 8.1., 8.2., 8.4. CLRS 20.1., 20.2., 20.3.
10 (18 Nov)	Multiple Dates	Tutorial 5	*	Quicksort, BFS, and DFS Solutions, slides
10 (18 Nov)	Tue 19 Nov	Lecture 15	Mary	Lecture 15 - DFS and Topological Sort Recording from previous years	KT 3.4., 3.6. Roughgarden 8.3, 8.4 8.5. CLRS 20.4.