Session diary 2026

General information

We may attempt to live stream, the live in-person sessions. Please note that it is UCL’s expectation that students attend in-person. The Zoom link is available here. Not all sessions will be recorded or streamed. The recording link is password protected, with the password available on Moodle.

Homework

By UCL week

Week 6

• Read the first two chapters of the notes.

Week 6a

• We introduced divide-and-conquer type arguments

• Binary search

• A version of the King’s salary see Peter Winkler’s book, page 18

• We introduced a version of selection sort

Week 6b

• We introduced faster than \(O(n^2)\) multiplication, where \(n=2^k\) is the number of digits, due to Karatsuba; we got \(O(n^{\log_2 3})\); this is \(3^k\), which corresponds to the number of single digit multiplications at the end of the divide and conquer.
  • Although the final answer is correct, in my haste, I think I did not properly estimate the number of additions/subtractions required. I should of said that each level \(j\), we basically have \(3^j\) additions with numbers that which are of length \(2^{k-j}\), this gives the summation, \[\sum_{j=1}^k 2^{k-j}3^j \leq 3\cdot3^{k}.\]
• We formally introduced the big \(O\) notation and gave a sufficient condition in terms of limits
• We analysed more carefully the selection sort algorithm.
  • We introduced the concept of a loop-invariant
  • We wrote some R code for this sorting algorithm

Week 7

• Starting looking at Chapter 3 of the notes.

Week 7a

• We introduced merge sort and discussed why it is \(O(n\log n)\)
  • We coded it, but it had a bug; the bug was that v, the second half the split of x, was wrongly defined. The version done in class will be posted along with the videos, and a working version is available here.

Week 7b

• We discussed the recurrence: \(T(n) = 2T(n/2) +O(n)\) and some ways of solving it.

• We manifested arrays and linked lists in C++ and discussed the pros/cons.

  • A very brief introduction to C++, originally written for Stat9
  • Code for illustrating pointers and arrays in C++
  • Code for making a short linked list in C++

Week 8

Week 8a

• We discussed stacks, queues, and trees

Week 8b

• We sketched a proof of the Master theorem, where I fumbled on the third case. I should of wrote:
  • The regularity assumption implies that \(f(b^{\ell}) \leq (c/a)^{k-\ell} f(b^k)\).
  • Then \(T(n) = T(b^k) = \Theta(a^k) + \sum_{\ell=0} ^{k-1} + \Theta(a^k) + a^{k-1-\ell}f(b^\ell) \leq a^{-1}f(b^k)\sum_{\ell=0} ^{k-1} c^{k-\ell} \leq \Theta(a^k) + \frac{a^{-1}f(b^k)}{1-c}.\)
  • The result that \(T(n) = T(b^k) =O(f(n))\) now follows, since by assumption \(f(n) = \Omega(n^{\log_b a + \epsilon})\); it is not much harder to get that it is actually \(\Theta(f(n))\).
  • More details in Section 4.6 of the CLRS-Algorithms book.
• We discussed simple uniform hashing.
• We introduced the adjacency matrix for counting walks on graphs.

Week 9

• Start looking at Chapter 4 of the notes.

Week 9a

• We started a discussion about dynamic programming
  • Fibonacci numbers, python code
• We introduced breadth and depth first search
  • BFS Python code
  • DFS Python code
• We had some A/V issues
• We introduced spanning trees
  • board1
  • board2

Week 9b

• We discussed the notion of a predecessor subgraph in the BFS algorithm.
• We introduced the notion of a light edge.
  • We discussed Prim’s and Kruskal’s algorithms (CLRS Chapters 22.1, 22.2)
• We introduced the notation of relaxation
  • We discussed the Bellman-Ford Algorithm (CLRS, Chapter 24.1)

Week 10

• Read chapter 5 of the notes

Week 10a

• We discussed Dijkstra’s algorithm
• We introduced binary heaps (CLRS, Chapter 6)

Week 10b

• We continued our discussion of heaps and priority queues and their role in Dijkstra’s algorithm
• We continued our discussion on dynamics programming and the role of bottom up coding and memoization

Week 11

Reading break

Week 12

Week 12a

• Hidden Markov chains and the filtering problem (forward algorithm)

Version: 08 November 2026