CLR refers to Cormen, Leiserson, Rivest and Stein: "Introduction to Algorithms (Third Edition)".

Lecture 1 (Jan 6)

General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, comparison model. RAM model (or uniform cost model), bit model (or: logarithmic cost model). Definition and examples of oracles (not done explicitly),. The Fibonacci example: introduce recursion, iteration (the array method), and fast exponentiation. Worst-case time complexity. Landau symbols: O, Omega, Theta, small o, small omega. Examples of many complexity classes (linear, quadratic, polynomial, exponential).

Resources:

• CLR, chapters 1, 2 and 3.
• Scribed notes on the Fibonacci example.
• Scribed notes on Landau symbols.

Exercise mentioned during the lecture:

• Show that (log n)^1000 = o(n^0.001), n^1000=o(1.001^n), and 1000^n = o(n!).
• Show that n ln (n) / ln (n!) -> 1 as n -> infinity.

Exercise to chew on, but not mentioned in class:

• Show that for the fast exponentiation method in the RAM model, T_n = O(log(n)) even if n is not a power of 2.
• Determine in Big Theta notation the bit model time complexities of the recursion method, the array method, and the fast exponentiation method in the Fibonacci example. In class, we only did the RAM model complexities.

Lecture 2 (Jan 8)

Assignment 1 handed out: this handwritten assignment is due on January 20 at 1:05 pm, in class.

Introduction to the divide-and-conquer principle. Fast exponentiation revisited. Introduction to recurrences. The divide-and-conquer solution to the chip testing problem in CLR. Divide-and-conquer (Karatsuba) multiplication. Mergesort, convex hulls in the plane. We covered all of chapter 2 and part of chapter 3 of CLR.

Resources:

• CLR, chapter 4.
• Scribed notes on divide-and-conquer (part I).

Exercises mentioned during the lecture:

• Describe in algorithmic form the linear time upper hull merge algorithm outlined in class.

Exercises not mentioned during the lecture:

• One student asked if bad chips would have to lie. If they have to lie, then the problem is done with n-1 tests. Do you see that?

Lecture 3 (Jan 13)

Binary search using a ternary oracle (with analysis by the substitution method). Strassen matrix multiplication. Euclid's method for the greatest common divisor. The master theorem (statement only). Recursion tree to explain the master theorem.

Resources:

• CLR, chapter 4.
• Scribed notes on divide-and-conquer (part II).

Exercises mentioned during the lecture:

• Write the binary search algorithm using a binary oracle.
• For the adventurous: Show that the bit complexity of Euclid's algorithm for gcd (n,m) is O( log n . log m ).
• What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0? (This was not mentioned but may make you think about recursion trees.)

Lecture 4 (Jan 15)

The induction method illustrated on mergesort and binary search with a ternary oracle. Linear time selection: finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan. O(n) complexity proof based on induction.

Resources:

• CLR, chapter 9.
• Scribed notes on divide-and-conquer (part III).

Exercises mentioned during the lecture:

• For the binary search algorithm with binary oracle, show by induction on n that the worst-case number of comparisions T_n satisfies
  T_n ≤ 2 + ⌈log_2 (n)⌉
  for all n. Convince yourself that T_1 =2, and that
  T_n = 1 + T_{⌊(1+n)/2⌋}.
• Using the recursion tree, analyze the median-of-three algorithm and convince yourself that its worst-case time complexity is Θ(n log n).

Lecture 5 (Jan 20)

Assignment 1 due at 1:05 pm in class, handwritten on paper; groups of 2 are allowed (one copy per pair); iPad printouts are permitted. The Fast Fourier Transform. Multiplying polynomials in time O(n log n).

Resources:

• CLR, chapter 30.
• Luc's notes given in a link during the lecture.

Exercise: We saw the FFT conversion algorithm from N coefficients to N values, evaluated at ω⁰, ω¹, ... ω^N-1, where ω is the N-th root of unity. Take N=4. The algorithm computes polynomial P at 4 points. It builds on two recursions which compute two polynomials at two points, and finally, each of these two recursions uses two recursions computing a polynomial at one point. This gives a total of 7 function calls. It is useful to work out the outputs of these seven calls, i.e., a vector of size 4, two vectors of size 2, and 4 vectors of size 1. Express these vectors as a function of ω and the coefficients of P. Then express these same vectors in complex number form.

Lecture 6 (Jan 22)

Assignment 2 handed out: this handwritten assignment is due on February 3 at 1:05 pm, in class. Note: the k+1 +k log_2 (n/k) complexity in exercise 2 should be replaced by O(k+1 +k log_2 (n/k)).

Dynamic programming. Computing binomial coefficients and partition numbers. The traveling salesman problem. The knapsack problem. The longest common subsequence problem.

Resources:

• Scribed notes on dynamic programming. These notes have a bit more than we will see in class.

Exercises mentioned in class:

• In the shortest path problem, formulate the sub-solutions necessary so that when asked, one can get the shortest path sequence from an arbitrary node j to node 1 in time O(n), where n is the number of nodes. And tell us how to modify or update the TSP algorithm seen in class.
• Given the longest common subsequence table and the input bit strings of lengths n and m, write an algorithm that outputs the positions of the matched bit pairs in time O(n+m).
• Modify the knapsack algorithm so that you can output the items that fit in a knapsack given that P[n,k]=1.

Note about assignment 2: the k+1 +k log_2 (n/k) complexity in exercise 2 should be replaced by O(k+1 +k log_2 (n/k)).

Exercises not mentioned in class:

• Modify the knapsack algorithm for the case that we have an unlimited supply of items of the given sizes.
• Can you count the number of knapsack solutions by dynamic programming?
• Can you count the number of ways of paying a bill of n dollars with coins of values c_1 < c_2 < ... < c_k? Here the input is n, k, c_1,...,c_k.

Lecture 7 (Jan 27)

Lower bounds. Oracles. Viewing algorithms as decision trees. Proof of lower bound for worst-case complexity based on decision trees. Examples include sorting and searching. Lower bounds for board games. Finding the median of 5 with 6 comparisons. Merging two sorted arrays using finger lists.

Resources:

• Scribed notes on lower bounds (first half).
• CLR section 8.1 (for the lower bound for sorting).

Practice: What is meant by the statement that for an algorithm A, the worst-case time T_n (A) is Ω(n^2)? And what is meant when we say that for a given problem, the lower bound is Ω(n^7)?

Lecture 8 (Jan 20)

Lower bounds via witnesses: finding the maximum. Lower bounds via adversaries. Guessing a password. The decision tree method as a special case of the method of adversaries. Finding the maximum and the minimum. Finding the two largest elements. Finding the median.

Resources:

• Scribed notes on lower bounds (second half).

An exercise:

• We mentioned that the height of a complete binary tree on n leaves is ⌈log_2 n⌉. Prove this. And show that for any binary tree, this is a lower bound.

Lecture 9 (Feb 3)

Assignment 2 due at 1:05 pm, in class. Assignment 3 handed out: this handwritten assignment is due on February 12 at 1:05 pm, in class. Note added late: in exercise 2, the oracle can ask whether x < A[i,j], x ≤ A[i,j], x > A[i,j] and x ≥ A[i,j].

Introductory remarks about ADTs (abstract data types). Lists. Primitive ADTs such as stacks, queues, deques, and lists. Classification and use of linked lists, including representations of large integers and polynomials, window managers, and available space lists. Uses of stacks and queues in recursions and as scratchpads for organizing future work. Introduction to trees: free trees, ordered trees, position trees, binary trees. Bijection between ordered trees (forests) and binary trees via oldest child and next sibling pointers. Relationship between number of leaves and number of internal nodes with two children in a binary tree. Complete binary trees: implicit storage, height.

Resources:

• For the notation for list operations, see chapter 1 of Data Structures and Network Algorithms (R.E. Tarjan, SIAM, Philadelphia, 1983).
• CLR, chapter 10.
• Scribed notes on ADTs, lists, stacks.
• Scribed notes on trees.

Exercises mentioned in class:

• We saw the way of navigating a complete binary tree using the locations of the nodes in an array. Generalize the navigation rules by computing for a given node i in a complete k-ary tree with n nodes, the parent, the oldest child and the youngest child (and indicate when any of these do not exist).
• Prove by induction that in a binary tree, the number of leaves is equal to the number of nodes with two children plus one.
• Write an O(n) time program for creating the oldest-child-next-sibling binary tree seen in class from a given ordered tree in which the children of a node are stored from oldest to youngest in a linked list. Conversely, from a binary tree in which the root only has a left child, recreate in O(n) time the corresponding ordered tree.

Lecture 10 (Feb 5)

Continuing with trees. Depth, height, external nodes, leaves, preorder numbers, postorder numbers. Preorder, postorder, inorder and level order listings and traversals. Recursive and nonrecursive traversals. Stackless traversal if parent pointers are available. Representing and storing trees: binary trees require about 2n bits. Counting binary trees (Catalan's formula) via counting Dyck paths. Expression trees, infix, postfix (reverse Polish), and prefix (Polish) notation.

Resources:

• CLR, sections 10.3 and 10.4.
• Scribed notes on trees.

Exercises mentioned in class:

• Write linear time algorithms to go between any of the 2n-bit representations of binary trees, and a binary tree.
• Write an O(n) algorithm that computes for all nodes in an ordered tree of size n the sizes of their subtrees (and stores those sizes in the corresponding cells).

Exercises not mentioned in class:

• How many bits are needed to store the shape of a binary expression tree on n nodes?
• How many bits are needed to store the shape of a rooted ordered tree on n nodes?
• Determine in time O(n) whether a coded bit sequence of length 2n that uses the codes 00, 01, 10 and 11 for the four kinds of nodes, is a legal sequence, i.e., one that corresponds to a binary tree on n nodes.

Lecture 11 (Feb 10)

Introduction to the ADT Dictionary. Definition of a binary search tree. Standard operations on binary search trees, all taking time O(h), where h is the height. Generic tree sort. The browsing operations. Definition of red-black trees. Red-black trees viewed as 2-3-4 trees.

Resources:

• Binary search trees: chapter 13 of CLR.
• Scribed notes entitled Dictionary, binary search tree.

Exercises mentioned in class:

• Show that √n sorted lists, each of length √n, can be merged into one sorted list of length n using only about (1/2) n log_2 n comparisons. Furthermore, show that an unsorted list of n items can be turned ino √n sorted lists, each of length √n using only about (1/2) n log_2 n comparisons.

Exercise not mentioned in class:

• We are given an arbitrary binary tree representing an electrical network. Within each node, we store the resistance of the left and right edges emanating from the node (if they exist). Imagine connecting all leaves to the ground (run a wire through all of them). Then your task is to write a linear time algorithm that computes the resistance between the root and the ground.

Lecture 12 (Feb 12)

Relationships between rank, height and number of nodes. Insert operation on red-black trees. Standard deletion is not covered in class. Lazy delete. Split and join in red-black trees. Application to list implementations (concatenate and sublist in O(log n) time). Definition of HB-k, AVL and 2-3 trees.

Resources:

• Red-black trees (chapter 14 of CLR).
• Scribed notes on red-black trees.

Exercises mentioned in class:

• Write a simple recursive algorithm to construct a red-black tree from a sorted array of n elements. Your algorithm should take O(n) RAM time, and should not use any key comparisons.
• Show by induction that for a red-black tree, r ≤ h ≤ 2r, where r is the rank of the root and h is the height of a red-black tree.
• Convince yourself that the split operation can be implemented in O(log n) time.

Midterm examination (Feb 17)

Room LEAR 232, 1-2:30 pm.

Lecture 13 (Feb 19)

Augmented data structures. Examples:

• Data that participate in several data structures.
• Combining search trees and sorted linked lists.
• Order statistics trees. Operations rank and selection.
• Lists as trees using the red-black tree operations "join" and "split".
• Interval trees. VLSI chip layout application. Sweepline paradigm.

Not done in 2026:

• k-d-trees. Range search, partial match search, quadtrees.
• Quadtrees.
• Definition of BSP (binary space partition) trees. Painter's algorithm.

Resources:

• CLR, chapter 14.
• Scribed notes on augmented data structures.

Exercises mentioned in class:

• Write a simple algorithm for a classical insert in a binary search tree, augmented with a a sorted linked list.

Lecture 15 (Feb 24)

Assignment 4 handed out, 2:25 pm on March 10, 2026. Cartesian trees. Random binary search trees. Treaps. Analysis of the expected time of the main operations. Quicksort revisited.

Resources:

• CLR, section 12.4 (for random binary search trees).
• CLR, chapter 7 (for quicksort).
• Scribed notes.

Lecture 16 (Feb 26)

(Lecture halved by a fire alarm.) Priority queues (as abstract data types). Uses, such as in discrete event simulation and operating systems. Binary heaps. k-ary heaps.

Resources:

• Chapter 6 of CLR (for binary heaps).
• Scribed notes.

Exercises mentioned in class:

• Determine the navigation details for array-based k-ary heaps.

Lecture 17 (Mar 10)

Assignment 4 due at 2:25 pm, in class. Heapsort. Bottom-up heapsort. Tournament trees. Amortization. Potential functions. Examples:

• Binary addition.
• Stack with multipop.
• Lazy delete in red-black trees.

Resources:

• CLR, chapter 17.
• Scribed notes.

Suggested exercise: in class, we implemented a lazy deletemin in a tournament tree. How would you implement a true deletemin?

Lecture 18 (Mar 12)

Amortized analysis, continued. Further examples:

• Weight-balanced search trees.
• Splay trees.

Resources:

• CLR, chapter 17.
• Scribed notes.
• Scribed notes on splay trees.

Exercise mentioned in class: consider a 1-step splay tree in which splay steps use one-level rotations instead of the two-step rotation seen in class. Exhibit a sequence of n standard operations (search, insert, delete), starting from an empty tree, such the total complexity is Ω(n^2), and not O(n log n).

Lecture 19 (Mar 17)

Assignment 5 handed out, due 2:25 pm on March 26, 2026. Stringology. Data structures for strings and compression. Tries, PATRICIA trees, digital search trees. Suffix tries, suffix trees, suffix arrays. String searching in a large file via the Knuth-Morris-Pratt algorithm.

Resources:

• CLR, section 32.4 (for the Knuth-Morris-Pratt algorithm).
• Scribed notes.

Exercises:

• Show that for a k-ary PATRICIA tree on n strings, in which some strings can be prefixes of other strings, the number of the nodes in the tree is at most 2n.
• Add one or two lines to the KMP algorithm to make it return all pattern matches, not just one.

Lecture 20 (Mar 19)

Introduction to compression and coding. Fixed and variable width codes. Prefix codes. Huffman trees. Huffman code. An O(n log n) algorithm for finding the Huffman tree. Definition of a greedy algorithm. Data structures for Huffman coding. Merging sorted lists by the greedy method. Generating a random integer.

Resources:

• Scribed notes: introduction to information theory.
• CLR, section 16.2 (for prefix and Huffman codes).

Exercises mentioned in class:

• Show by example that there is a set of symbol weights for which the table of codewords for the Huffman codes takes Ω (n^2) space.
• Why is the expected length of a Huffman codeword for an n-symbol alphabet at most ⌈log_2 n⌉?
• Practice: Given a prefix code tree, write an algorithm to compress an input message, and write another algorithm to un-compress a compressed binary sequence to recover the original input.

Lecture 21 (Mar 24)

Definition of entropy and Shannon's result on best possible compression ratios. Entropy of an input source. Kraft's inequality. Proof of Shannon's theorem. The Shannon-Fano code. Lempel-Ziv compression. Data structures for Lempel-Ziv compression. Digital search tree.

Resources:

• Scribed notes: Shannon's theory.
• Scribed notes: Lempel-Ziv compression.

Exercises:

• Prove Kraft's inequality by induction on the height.
• Write a one-pass linear time algorithm to create the digital search tree for Lempel-Ziv compression.

Lecture 22 (Mar 26)

Introduction to graphs: notation, definitions, adjacency matrix, adjacency lists. Graph traversals as the fundamental procedures for most graph algorithms: depth first search. DFS forest and DFS properties. Classification of edges. Detecting cycles.

Resources:

• CLR, sections 22.1, 22.2 and 22.3.
• Scribed notes on graph algorithms.

Exercises:

• Show that one can order all adjacency lists in O(|V|+|E|) time.
• What is the worst-case time of the DFS algorithm for detecting a cycle that we saw in class?
• Suggest an O(|V|) method for detecting a cycle in an undirected graph given in adjacency list format.

Lecture 23 (Mar 31)

Euler tour. Breadth first search. BFS tree. Shortest path problem. Shortest path properties. Dijkstra's greedy algorithm for shortest paths.

Resources:

• CLR, section 22.2.
• Scribed notes on graph algorithms.
• CLR, section 24.3 (Dijkstra's algorithm for shortest paths).

Exercises:

• Modify the BFS algorithm to decide if a given graph is bipartite.
• Suggest a data structure for managing the adjacency lists in the Euler tour algorithm.

Lecture 24 (Apr 2)

Minimal spanning tree. Main properties. Greedy approach for the MST: the Prim-Dijkstra algorithm. Application in hierarchical clustering. Kruskal's algorithm. A two-approximation for the traveling salesman problem. The all-pairs shortest path algorithm of Floyd and Warshall. Transitive closure of a graph and matrix multiplication.

Resources:

• CLR, chapter 23 (minimal spanning trees).
• CLR, section 35.2 (the traveling salesman problem).
• CLR, section 25.1 (transitive closure of a graph).
• CLR, section 25.2 (the Floyd-Warshall algorithm).
• Scribed notes on MST and shortest paths.

Exercises:

• How would you find a spanning tree that minimizes the maximal weight (not the sum of the weights)?
• Discuss the choice of priority queue in Dijkstra's algorithms for shortest path and MST when all edge weights are integers between $1$ and $10$. What is the overall complexity?
• How would you pick k if a k-ary heap is used in Dijkstra's algorithms for shortest path and MST?
• Show that the set membership contribution to Kruskal's algorithm takes only time $O(|V| \log |V|)$ if we always change the labels of the nodes in the smallest set. And how would you then keep track of the sizes of the sets?

Lecture 25 (Apr 7)

Directed acyclic graphs (or: dags). Topological sorting. Activity (PERT) networks. NIM games. Strongly connected components in directed graphs.

Resources:

• Scribed notes.
• CLR, section 22.5 (strongly connected components).

Exercises:

• Add a few lines to the algorithms for NIM games and PERT networks to compute for each node the perfect move (in a NIM game) and the critical path (in a PERT network), respectively.
• How would you determine if a dag contains a node u that can be reached from all roots?

Lecture 26 (Apr 9)

Network flows. The Ford-Fulkerson method. The Edmonds-Karp algorithm.

Resources:

• CLR, section 26.1 (network flows) and 26.2 (the Ford-Fulkerson method).
• Scribed notes.