INFORMATION STRUCTURES

Schedule.

Week 1.
  • Monday September 5th. Holiday: No Lecture.
  • Wednesday September 7tt. Recurrences: understanding the master theorem; merge-sort.

    Week 2.
  • Monday September 12th. Recurrences: randomised selection.
  • Wednesday September 14th. Recurrences: using recurrence trees; deterministic selection.

    Week 3.
  • Monday September 19th. Recurrences: domain transformation; quicksort; lower bounds on sorting.
  • Wednesday September 21st. Heaps: heapsort.

    Week 4.
  • Monday September 26th. Heaps: minimum spanning trees.
  • Wednesday September 28th. Binary Search Trees.

    Week 5.
  • Monday October 3rd. Binary Search Trees: randomly built BSTs. Linear time sorting.
  • Wednesday October 5th. Red-Black Trees: insertions.

    Week 6.
  • Monday October 10th. Holiday: No Lecture.
  • Wednesday October 12th. Red-Black Trees: deletions and joins.

    Week 7.
  • Monday October 17th. Red-Black Trees: line segment intersection.
  • Wednesday October 19th. Hashing: chaining, open addressing.

    Week 8.
  • Monday October 24th. No Lecture.
  • Wednesday October 26th. Amortized Analysis.

    Week 9.
  • Monday October 31st. Splay Trees.
  • Wednesday November 2nd. Binomial Trees.

    Week 10.
  • Monday November 7th. Fibonacci Heaps: Dijkstra's algorithm.
  • Wednesday November 9th. Skip Lists; Matrix Muliplication.

    Week 11.
  • Monday November 14th. Weight Balanced Trees; Probabilistic Checking.
  • Wednesday November 16th. Treaps.

    Week 12.
  • Monday November 21st. Data Structures for Disjoint Sets: Kruskals algorithm.
  • Wednesday November 23rd. Leftist Heaps.

    Week 13.
  • Monday November 28th. Minimum Cut: randomised algorithm.
  • Wednesday November 30th. Fast Fourier Transforms.
  • Thursday December 1st. The Last Lecture.

    Week 14.
  • Thursday December 8th. Final Exam.