Lectures are usually twice a week:
-
Wednesdays 13-15, room EA.
-
Fridays 13-15, room EC.
You can find the full schedule on TimeEdit.
Lecture notes will appear here around the time of the lecture. The topics listed for future lectures are liable to change!
-
Tuesday 22nd March, 13-15, room EA. Introduction, dynamic arrays. Code used in the lecture: CopyString.java, CopyStringBuilder.java, CopyNaive.java, Copy100.java, CopyDouble.java. Sample input: War and Peace (run with e.g. java CopyDouble < pg2600.txt).
-
Wednesday 23rd March, 13-15, room EL41. Complexity. We didn’t get through all the slides in the lecture, but you should read them as preparation for doing the complexity hand-in.
-
Wednesday 13th April, 13-15, room EL41. Binary search, insertion sort, merge sort. Code: Sort.hs.
-
Friday 15th April, 13-15, room EC. Quicksort, recursive function complexity. Very optional: Finite calculus: a tutorial for solving nasty sums.
-
Wednesday 20th April, 13-15, room EA. Stacks, queues. Code: Queue.hs.
-
Friday 22nd April, 13-15, room EC. Priority queues, binary heaps. Binary heaps on Wikipedia.
-
Thursday 28th April, 13-15, room EA. Skew heaps, binary search trees, AVL trees. Skew heaps and AVL trees on Wikipedia. Visualising skew heaps and AVL trees.
-
Friday 29th April, 13-15, room EC. Finishing AVL trees, real-world sorting.
-
Wednesday 4th May, 13-15, room EA. 2-3 trees, B-trees, AA-trees. AA trees on Wikipedia. Really ugly code for 2-3 trees. For those who are interested, here are some nice notes I found on 2-3 trees, which include deletion. Visualising B-trees; by setting k to 3, you get 2-3 trees.
-
Wednesday 11th May, 13-15, room EA. Linked lists, skip lists.
-
Friday 13th May, 13-15, room EC. Hash tables. Bloom filters on Wikipedia.
-
Wednesday 18th May, 13-15, room EA. Graphs 1: depth-first search, topological sorting, strongly connected components. Very optional: Graph algorithms with a functional flavour.
-
Friday 20th May, 13-15, room EC. Graphs 2: finding paths (breadth-first search, Dijkstra’s algorithm), Prim’s algorithm.
-
Wednesday 25th May, 13-15, room EA. The end, exam practice.