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

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++

Version: 16 October 2026