Data Structure & Algorithm

 Course Materials

https://www.learn.ed.ac.uk/webapps/blackboard/content/listContent.jsp?course_id=_79967_1&content_id=_4768803_1&mode=reset

 

• 

  Schedule

  Attached Files:

  •  lecture14.pdf (1.27 MB)
  •  IADS_tutorial4_solutions.pdf (253.264 KB)

  Sample exam paper

  Paper  and solutions !

  Semester 1

  We think about our (pre-recorded) lectures as taking place on Tuesdays and Thursdays, although we will have them available before then, if you want to get a headstart.

  You may play the lecture videos using the links below (you will be prompted to click on a further link to open a new window). Each lecture consists of several files; the playlist allows you to watch all of these in succession.

  All the lecture videos are subtitled. If you wish to see the subtitles, for the time being we suggest playing the files separately rather than via the playlist. (Subtitles and playlists are not yet properly integrated - we've raised this as a bug.)

  Here is our Course Admin Video, to explain details of our lecture schedule, coursework schedule, and related matters.   The slides are here .

  Week	Date	Lecture #	Lecturer	Topic	Reading
  1	22 Sep 20	1.	John	Overview of course content Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5 Slides (pdf)	CLRS 1
  	24 Sep 20	2.	John	Inefficient vs. efficient algorithms Lecture video (playlist), Part 1, Part 2, Part 3, Part 4 Slides (pdf)	CLRS 2.1, 2.3, 31.6
  	25 Sep 20	*	Mary	Live discussion session (recording)
  2	29 Sep 20	3.	John	Asymptotics: Little o and omega Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5 Slides (pdf)	CLRS 3, GTG 3.3, 3.4
  	1 Oct 20	4.	John	More asymptotics: Big O, Omega and Theta Lecture video (playlist), Part 1, Part 2, Part 3, Part 4 Slides (pdf)	CLRS 3, GTG 3.3, 3.4
  	2 Oct 20	*	Mary	Live discussion session (recording)
  3	varies	Lab1	varies	Getting started in Python ; Writing programs in Python
  	varies	Tut1	varies	Asymptotic notation  Solutions  Slides Recording from Steve's Friday 12 tutorial
  	6 Oct 20	5.	John	Asymptotic analysis of sorting algorithms Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5 Slides (pdf) Last year's slides with some more detailed maths	CLRS 2.2
  	8 Oct 20	6.	John	Representation of program data in memory Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5 Slides (pdf)	CLRS 10, esp. 10.2, 10.3
  	9 Oct 20	*	Mary	Live discussion session (recording)
  4	varies	Lab2	varies	Classes in python
  	varies	Tut2	varies	Analysis of algorithms  Solutions  Slides Recording from KK's Tuesday 2pm tutorial
  	13 Oct 20	7.	John	Abstract data types: Lists, stacks, queues Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5, Part 6 Slides	CLRS 10, 17.4
  	15 Oct 20	8.	John	Sets, dictionaries and hashing Lecture video (playlist), Part 1, Part 2, Part 3, Part 4 Slides	CLRS 11
  	16 Oct 20	*	Mary	Live discussion session (recording)
  5	varies	Lab3	varies
  	20 Oct 20	9.	John	Balanced trees Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5, Part 6 Slides	CLRS 12.1-3, 13.1-3
  	22 Oct 20	10.	John	Divide-conquer-combine and the Master Theorem Lecture video (playlist), Part 1, Part 2, Part 3, Part 4, Part 5, Part 6, Part 7 Slides	CLRS 4 intro, 4.3-4.5
  	23 Oct 20	*	Mary	Live discussion session
  6	varies	Lab4	varies	"drop-in" for coursework 1
  	varies	Tut3	varies	Data structures for lists and sets  Solutions  Slides No sample recording for this week's tutorial, unfortunately.
  	30 Oct 20	*	-	NO Live discussion this week
  7	varies	Lab5	varies	"drop-in" for coursework 1
  	3 Nov 20	11.	Mary	The Heap Data Structure Lecture video (playlist): Part 1, Part 2, Part 3 Slides	CLRS 6.1-6.3
  	5 Nov 20	12.	Mary	BuildHeap and HeapSort Lecture video (playlist): Part 1, Part 2, Part 3, Part 4 Slides	CLRS 6.1-6.4
  	6 Nov 20	*	John	Live discussion session
  8	varies	Tut4	varies	The Master Theorem and Heaps   Solutions   Slides No sample recording for this week's tutorial, unfortunately.
  	10 Nov 20	13.	Mary	Quicksort Lecture video (Playlist): Part 1, Part 2, Part 3, Part 4 Slides	CLRS 7.1, 7.2, 7.4
  	13 Nov 20	*	John	Live discussion session
  9	17 Nov 20	14.	Mary	Graphs I: graphs, Breadth-first search, Depth-first search Lecture video (playlist): Part 1, Part 1a, Part 2, Part 3, Part 4, Part 5, Part 6 Slides	CLRS 22.1-3
  	20 Nov 20	*	John	Live discussion session (captions corrected)
  10	varies	Tut5	varies	Quicksort, Graphs   Solutions  Slides   Recording from Vesselin's Friday 2pm tutorial. Recording from Neo's Friday 2pm tutorial.
  	24 Nov 20	15.	Mary	Graphs II: DFS and Topological Sort Lecture video (playlist): Part 1, Part 1a, Part 2, Part 3, Part 4, Part 5 Slides	CLRS 22.4
  	27 Nov 20	*	John	Live discussion session

  
  

  Here is a .pdf of the Questions-and-Answers for Quiz 0

  Semester 2

  Again we think about our (pre-recorded) lectures as taking place on Tuesdays and Thursdays. Below is a tentative schedule (which may change a bit as the semester progresses).

  Week	Date	Lecture #	Lecturer	Topic	Reading
  1	12 Jan 21	16.	Mary	Introduction to Dynamic Programming Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5, Part 6 slides	slides, Wright's coin-changing paper (Uni library has subscription)
  	14 Jan 21	17.	Mary	Seam-Carving and Edit Distance by Dynamic Programming (seam-carving demo video) Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5 slides	CLRS 15.3 and 15.4 are relevant, though they refer to problems we don't consider.   GTG 13.3.2 is somewhat relevant. The original "Seam Carving" paper is here.
  	15 Jan 21	*	John	Live discussion session (captions corrected)
  2	19 Jan 21	18.	Mary	All-pairs shortest paths by Dynamic programming Lecture video (playlist): Part 1, Part 2, Part 3 slides	CLRS 25 (intro) and 25.2
  	21 Jan 21	19.	Mary	Probabilistic Finite State Machines and the Viterbi Algorithm Lecture video (playlist): Part 1, Part 2, Part 3, Part 4 slides	(just the slides)
  	22 Jan 21	*	John	Live discussion session
  3	varies	Tut6	varies	Dynamic Programming,  Solutions , Slides Recording of Steve's Tuesday tutorial
  	26 Jan 21	20.	John	Context-free Languages and Grammars Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5, Part 6 (song)  slides
  	28 Jan 21	21.	John	Parsing for Context-free Languages: The CYK Algorithm Lecture video (playlist): Part 1, Part 2, Part 3, Part 4 slides
  	29 Jan 21	*	Mary	Live discussion session
  4	varies	Tut7	varies	Viterbi Algorithm and Context-free Grammars,  solutions,  slides Recording from Steve's Friday tutorial
  	2 Feb 21	22.	John	LL(1) Predictive Parsing Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5,  Part 6 (non-examinable) slides
  	4 Feb 21		-	NO LECTURE
  	5 Feb 21	*	Mary	Live discussion session
  5	varies	Lab6	varies	Dynamic Programming in Python editdist.py , apsp.py
  	9 Feb 21	23.	Mary	P and NP Lecture video (playlist): Part 1, Part 2, Part 3, Part 4 Slides	CLRS 34 (intro), 34.1, 34.2, 34.3
  	11 Feb 21	24.	Mary	Satisfiability and NP-completeness Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5 Slides	CLRS 34.4, 34.5
  	12 Feb 21	*	John	Live discussion session
  FLW	-	-	-
  6	varies	Lab7	varies	"drop-in" for coursework 3
  	varies	Tut8	varies	LL(1) parsing and polytime reductions   Solutions    Slides Recording from Mary's Monday 5pm tutorial Recording from Steve's Friday tutorial
  	23 Feb 21	25.	Mary	Dealing with NP-completeness (approximation algorithms) Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5 Slides	CLRS 35 "intro", 35.1, 35.4
  	26 Feb 21	*	John	Live discussion session
  7	varies	Lab8	varies	"drop-in" for coursework 3
  	2 Mar 21	26.	Mary	Dealing with NP-completeness (recursive backtracking) Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Part 5 Slides
  	5 Mar 21	*	John	Live discussion session
  8	varies	Tut9	varies	NP-completeness and Approximation solutions , slides   Recording from Mary's 5pm Monday tutorial Recording from Steve's Friday tutorial
  	9 Mar 21	27.	John	Introduction to Computability Theory Lecture video (playlist), Part 1, Part 2, Part 3, Part 4 Part 5 (non-examinable) Slides	Turing's original paper Section 9 is especially relevant to the lecture For recreation: paper on black hole computers  .
  	12 Mar 21		Mary	Live discussion session
  9	16 Mar 21	28.	John	Unsolvable Problems Lecture video (playlist), Part 1, Part 2, Part 3, Part 4 (non-examinable) Slides
  	19 Mar 21		Mary	Live Discussion Session
  10	varies	Tut10	varies	Register machines and computability   solutions and slides
  	26 Mar 21		Mary	Live Discussion Session
  11	31 Mar 21	29.	Mary	Revision Lecture Lecture video (playlist): Part 1, Part 2, Part 3, Part 4, Finale! Sample exam paper and solutions slides
  	14 May 21	Revision		Live Discussion session

• 

  Tutorial and lab materials

  Attached Files:

  •  IADS_tutorial4_solutions.pdf (253.264 KB)

  The following links will become live when the materials are released.

  • Python lab sheet 1: Getting started in Python ,  Solutions
  • Python lab sheet 2: Writing programs in Python ,  Solutions
  • Python lab sheet 3: Classes and more , Test files (numbers1.txt , numbers2.txt , numbers3.txt , numbers4.txt , numbers5.txt ), Solutions
  • Tutorial sheet 1 ,  Solutions
  • Tutorial sheet 2 ,  Solutions
  • Tutorial sheet 3 ,  Solutions
  • Tutorial sheet 4 ,  Solutions
    
  • Tutorial sheet 5,  Solutions