Algorithms - MIT 6.006

MIT 6.006 Introduction to Algorithms, Spring 2020 - YouTube

This course provides a rigorous and comprehensive introduction to the design and analysis of fundamental algorithms and data structures. The curriculum is structured to build a strong foundation in computational thinking, moving from basic tools for storing and retrieving data to advanced paradigms for solving complex problems.
The course begins by establishing a formal framework for evaluating algorithms, centered on the core principles of correctness and efficiency. Students learn the language of asymptotic analysis (Big O, Omega, and Theta notation) and operate within the Word RAM model of computation to analyze performance in a machine-independent manner.
The first major unit focuses on the implementation of two primary interfaces: sequences (for maintaining extrinsic, user-defined order) and sets (for intrinsic, key-based queries). A series of data structures are explored, each presenting a fundamental trade-off. Simple arrays offer constant-time random access but suffer from linear-time updates, while linked lists provide constant-time updates at their ends but have linear-time access. This trade-off is elegantly resolved by dynamic arrays and the concept of amortized analysis. For sets, the course contrasts the O(n) search of unsorted arrays with the O(log n) efficiency of binary search on sorted arrays, thereby motivating the need for efficient sorting algorithms. Classic O(n^2) sorts like Selection and Insertion Sort are contrasted with the optimal O(n log n) performance of Merge Sort.
To break the Ω(n log n) barrier for comparison-based operations, the course introduces hashing, which provides constant expected time for dictionary operations (find, insert, delete) by mapping a large universe of keys to a small table, with chaining to resolve collisions and universal hashing to guarantee performance through randomization. For integer-specific data, the course explores linear-time sorting algorithms like Counting Sort and Radix Sort, which operate outside the comparison model. This unit culminates in the study of balanced binary search trees (AVL trees), a powerful, versatile data structure that achieves O(log n) worst-case time for both dynamic updates and ordered queries, effectively providing the "best of all worlds." The technique of subtree augmentation is introduced to further enhance the capabilities of these trees, enabling efficient solutions to complex problems like index-based queries in dynamic sequences.
The second unit transitions to graph algorithms, modeling problems where relationships between data points are explicit. Students learn the standard representations (adjacency lists) and master the two fundamental traversal methods: Breadth-First Search (BFS) and Depth-First Search (DFS). BFS is applied to solve the single-source shortest path (SSSP) problem on unweighted graphs, while DFS is used for applications like finding connected components, performing topological sorts on Directed Acyclic Graphs (DAGs), and detecting cycles. The focus then shifts to weighted shortest paths, presenting a suite of algorithms tailored to different graph properties: DAG Relaxation for acyclic graphs, Dijkstra's algorithm for graphs with non-negative weights, and the more general Bellman-Ford algorithm for graphs with arbitrary weights, which can also detect negative-weight cycles. The unit concludes with Johnson's algorithm for the All-Pairs Shortest Paths (APSP) problem, which uses a clever reweighting technique to enable the efficient application of Dijkstra's algorithm.
The final unit focuses on a powerful paradigm for designing new algorithms: dynamic programming. Presented through the systematic SRTBOT framework, DP is framed as solving problems recursively by breaking them into a polynomial number of overlapping subproblems and using memoization to avoid redundant computation. Students learn to identify common subproblem patterns (prefixes, suffixes, substrings, integer parameters) and to expand the subproblem state space to "remember" necessary information, tackling a wide range of optimization and combinatorial problems such as Knapsack, Longest Common Subsequence, and game theory scenarios.
The course concludes with a look at computational complexity, introducing the classes P, NP, and the concept of NP-completeness. This provides context for the limits of efficient computation, formalizing the notion of "hard" problems for which no polynomial-time solutions are known. Finally, a capstone lecture connects the course's foundational principles to cutting-edge research in fields like computational geometry, computer graphics, and robotics, illustrating that the material covered is not merely academic but the essential toolkit for innovation across the landscape of computer science.

L1: Introduction

The lecture begins with an introduction from one of the instructors, Jason Ku. He mentions that he will be teaching the course alongside two other faculty members, Eric Demaine and Justin Solomon. He will be leading the first lecture, with the other instructors taking the subsequent two.
Core Concepts of the Course
The primary goal of the course is to equip students with the ability to solve computational problems. However, it goes beyond just finding solutions. Key aspects of the course include:

• Proving Correctness: Students will learn to formally prove that their solutions are correct.
• Arguing Efficiency: A significant focus is placed on analyzing and arguing for the efficiency of an algorithm compared to other possible solutions.
• Communication: The course emphasizes the ability to communicate these complex ideas clearly to others, not just to a computer. This involves more writing than coding.

Defining Problems and Algorithms
A computational problem is formally defined as a binary relation between a set of inputs and a set of outputs. This means for each input, there can be one or more correct outputs. Problems are typically defined by a predicate that can verify if a given output is correct for a given input. The course focuses on general problems with arbitrarily large inputs.
An algorithm is described as a function or a procedure that takes an input and produces a single, correct output that satisfies the problem's definition. It is a fixed-size procedure that can handle inputs of any size.
Example: The Birthday Problem
To illustrate these concepts, the "birthday problem" is introduced: determining if any two students in a classroom share the same birth time. An algorithm is proposed:

1. Maintain a record of birthdays encountered so far.
2. Interview students one by one.
3. For each student, check if their birthday is already in the record.
4. If a match is found, return the pair and stop.
5. If no match is found after checking the entire record, add the student's birthday to the record and move to the next student.
6. If all students are interviewed without finding a match, return that there is no match.

Proving Correctness with Induction
To prove that this algorithm is correct for any number of students, the use of mathematical induction is necessary. The process involves:

• Inductive Hypothesis: "If the first K students contain a match, the algorithm returns a match before interviewing student K+1."
• Base Case: The hypothesis holds true for K=0, as there can be no match among zero students.
• Inductive Step: Assuming the hypothesis is true for K, it is then shown to be true for K+1. If there was a match in the first K students, the algorithm would have already returned a correct answer. If the new match involves the (K+1)th student, the algorithm will find it by checking their birthday against the record of the first K students.

Analyzing Algorithm Efficiency
The efficiency of an algorithm is not measured by the time it takes a specific computer to run it, as this depends on the hardware. Instead, efficiency is measured by counting the number of fundamental operations the algorithm performs. This is where asymptotic analysis comes into play, which evaluates the performance of an algorithm as the input size grows.
Key notations in asymptotic analysis are:

• Big O (O): Represents an upper bound on the running time.
• Omega (Ω): Represents a lower bound.
• Theta (Θ): Represents a tight bound, meaning it is bounded from both above and below.

Common performance categories for algorithms include:

• Constant time (Θ(1)): The running time does not depend on the input size.
• Logarithmic time (Θ(log n)): Very efficient, almost as good as constant time for large inputs.
• Linear time (Θ(n)): The running time grows linearly with the input size.
• Log-linear time (Θ(n log n)): Slightly less efficient than linear time.
• Polynomial time (Θ(n^c)): Generally considered efficient in this course.
• Exponential time (Θ(2^n)): Considered very inefficient.

Model of Computation: Word RAM
To have a standardized way of counting operations, a model of computation called the word RAM is used. This model assumes a computer with:

• Random Access Memory (RAM): Any location in memory can be accessed in constant time.
• CPU: Can hold a small amount of information and perform fundamental operations on it.
• Words: The CPU operates on fixed-size chunks of data called "words" (e.g., 64 bits in modern computers).
• Constant Time Operations: Basic operations like integer arithmetic, logical operations, comparisons, and reading/writing a word from memory are assumed to take a constant amount of time.

Course Overview
The lecture concludes with a brief overview of the course structure. Students will learn two main strategies for solving algorithmic problems:

1. Reducing the problem to a known problem that can be solved with existing algorithms (e.g., using data structures, sorting, or graph searches).
2. Designing a new, recursive algorithm.

The course is divided into three main sections, each corresponding to a quiz:

• Quiz 1: Data structures and sorting.
• Quiz 2: Shortest paths and graph algorithms.
• Quiz 3: Dynamic programming.

L2: Data Structures and Dynamic Arrays

The lecture, led by instructor Erik Demaine, shifts focus from general algorithmic concepts to the specifics of data structures.
1. Interface vs. Data Structure
The lecture begins by drawing a crucial distinction between an interface and a data structure:

• Interface (or API/ADT): This defines what you want to do. It is the specification for the data being stored and the operations that can be performed on that data. It's the "problem" to be solved.
• Data Structure: This defines how you do it. It provides the concrete implementation, including the data representation and the algorithms that execute the specified operations. It is the "solution" to the problem.

The course will focus on two primary interfaces, sets and sequences, and two main data structure tools to implement them: arrays and pointers. This lecture focuses on the sequence interface.
2. The Static Sequence Interface and Static Arrays
A static sequence is an ordered collection of a fixed number of items, n. The interface for a static sequence supports the following operations:

• build(X): Creates a sequence from a given collection of items.
• len(): Returns the number of items, n.
• iter_seq(): Iterates through the items in their specified order.
• get_at(i): Returns the item at index i.
• set_at(i, x): Replaces the item at index i with a new item x.

The most natural data structure to implement this interface is a static array. In the Word RAM model of computation, memory is treated as a large array of fixed-size words (e.g., 64-bit words). A static array is implemented as a consecutive block of memory. This contiguous storage allows for highly efficient access:

• To get the i-th element, the computer calculates its memory location by taking the starting address of the array and adding the offset i.
• This address calculation and memory access is a constant-time operation. Therefore, get_at and set_at both run in Θ(1) (constant) time.
• Building the array (build) and iterating through it takes Θ(n) (linear) time.

A key assumption of the Word RAM model is that the machine's word size (w) must grow with the problem size (n), specifically w must be at least log n. This ensures that a single word is large enough to hold a memory address that can point to any of the n items.
3. The Dynamic Sequence Interface
The lecture then introduces a more flexible interface, the dynamic sequence, where the number of items can change. This interface supports all the static operations plus two new ones:

• insert_at(i, x): Inserts item x at index i, shifting all subsequent items one position to the right.
• delete_at(i): Removes the item at index i, shifting all subsequent items one position to the left.

Special cases of these operations, such as inserting or deleting at the beginning (insert_first, delete_first) or end (insert_last, delete_last), are particularly important because they can sometimes be implemented more efficiently than the general case.
4. Solution 1: Linked Lists
The first data structure considered for implementing a dynamic sequence is the linked list.

• Structure: A linked list consists of nodes, where each node contains an item and a pointer (a memory address) to the next node in the sequence. The entire structure is accessed via a "head" pointer to the first node.

• Performance:

  • Advantage: Operations at the beginning of the list are very fast. insert_first and delete_first only require redirecting a few pointers and take Θ(1) time.
  • Disadvantage: Accessing an element by its index is slow. To perform get_at(i), one must traverse the list from the head, following i pointers. This takes Θ(i) time, which is linear in the worst case.

• Augmentation: By adding a "tail" pointer that always points to the last node, operations like get_last and insert_last can also be made to run in constant time.

Linked lists and static arrays have complementary strengths: linked lists are good for dynamic updates at the ends, while static arrays are good for random access (get_at/set_at).
5. Solution 2: Dynamic Arrays
The final goal is to create a data structure that combines the strengths of both: the dynamic array. This is the data structure that underlies Python's list type.

• Core Idea: The key is to relax the rule that the allocated array's size must be exactly equal to the number of items (n). Instead, a dynamic array maintains an underlying static array whose size is kept roughly proportional to n (i.e., size = Θ(n)).
• Implementation:
  • When adding an item to the end (insert_last), if there is empty space in the underlying array, the operation is simple and takes Θ(1) time.
  • Resizing: When the array becomes full, a new, larger array is allocated, all existing elements are copied over, and the old array is discarded.
    • A bad strategy is to increase the size by a constant amount (e.g., size + 5), as this would lead to frequent, expensive (linear time) resizing operations.
    • A good strategy is to double the size of the array upon overflow.

6. Amortized Analysis
While doubling the array size is a linear-time operation, it happens infrequently. The cost of these expensive operations can be "spread out" over the many cheap, constant-time insertions that preceded them. This leads to the concept of amortized analysis.

• When starting with an empty array and performing n insert_last operations, resizes occur when the number of items hits powers of two (1, 2, 4, 8, ...).
• The total cost of all resizes is the sum of a geometric series, which amounts to Θ(n).
• Since the total cost for n insertions is Θ(n), the average, or amortized, cost per insertion is Θ(1) (constant time).

7. Performance Summary
The lecture concludes with a comparison of the three data structures discussed for the sequence interface:

*With tail pointer augmentation.
Dynamic arrays successfully provide the best of both worlds for random access and for adding/removing elements at the end, making them a highly effective and widely used data structure.

L3: PS 1: Asymptotic Behaviour of Functions

Instructor Jason Ku begins by explaining the purpose of these new Friday problem sessions. They are designed to bridge the gap between the foundational concepts presented in lectures and the practical application of those concepts required in the problem sets. The goal is to demonstrate how instructors approach and solve problems, providing students with a model for their own work. These recorded sessions replace previously recorded recitations, allowing recitations to be a more interactive and unrecorded "safe space" for students.
Problem 1: Asymptotic Order of Growth
This problem requires ordering sets of functions based on their asymptotic growth rate. Functions that are asymptotically equivalent (Θ) are grouped together in a set.
Part A
The first set of functions is ordered using the general principle that logarithmic factors grow slower than polynomial factors, which in turn grow slower than exponential factors. The final ordering presented is:

1. f1 = n^(log n)
2. f5 = n * log(n)
3. f2 = n * log^2(n)
4. f3 = n^2
5. f4 = 2^(2n)

Part B
This part involves functions with factorials and binomial coefficients ("n choose k"). The key strategy is to convert each function into a more familiar form to allow for comparison.

• Key Transformations:
  1. The binomial coefficient n choose k is defined as n! / (k! * (n-k)!).
  2. Stirling's Approximation for n! is introduced as n! ≈ sqrt(2πn) * (n/e)^n. This reveals that n! has a super-exponential growth rate, roughly Θ(n^n).
• Function Simplification:
  1. f2 = n^3 and f5 = n choose 3 are both shown to be Θ(n^3).
  2. f3 = n choose (n/2) is simplified using Stirling's approximation to be Θ(2^n / sqrt(n)).
  3. f1 = 2^n.
  4. f4 = n!.
• Final Ordering:
  1. {f2, f5} (polynomial n^3)
  2. f3 (exponential, but slowed by a polynomial factor)
  3. f1 (pure exponential 2^n)
  4. f4 (super-exponential n!)

Problem 2: Black Box Data Structure Operations
This problem provides a "black box" data structure that supports a sequence interface with insert_first, insert_last, delete_first, and delete_last all in Θ(1) time. The task is to implement new, higher-level operations using only these primitive functions.

• swap_ends(D): An algorithm to swap the first and last items in Θ(1) time.
  • Algorithm:
    1. Delete the first and last items, storing them in temporary variables (e.g., x1, x2).
    2. Insert x2 at the front of the sequence.
    3. Insert x1 at the end of the sequence.
  • Analysis: This involves four Θ(1) operations, so the total running time is Θ(1).
• shift_left(D, k): An algorithm to move the first k items to the end of the sequence in Θ(k) time.
  • Algorithm (Recursive View):
    1. Base Case: If k < 1, do nothing.
    2. Recursive Step: Perform a single shift by deleting the first item and inserting it at the end. Then, make a recursive call to shift the remaining k-1 items.
  • Analysis: The algorithm performs k calls, with each call doing a constant amount of work. This results in a total running time of Θ(k).

Problem 3: A Data Structure with the "Best of Both Worlds"
The challenge is to design a data structure that combines the advantages of dynamic arrays (Θ(1) random access) and linked lists (Θ(1) front/back modifications). The goal is a structure with Θ(1) worst-case lookup and Θ(1) amortized time for insertions and deletions at both ends.

• Approach 1: Circular Dynamic Array
  • Idea: Instead of a standard dynamic array that only has extra space at the end, this modified version maintains a block of data centered within a larger array, leaving empty space at both the beginning and the end.
  • Operations: Insertions and deletions at either end utilize this empty space and are Θ(1).
  • Resizing: When the space on either end runs out, a new, larger array is allocated (e.g., double the size), and all elements are copied over and re-centered. This expensive Θ(n) operation is amortized to Θ(1) because it only occurs after a linear number of cheap operations. Similarly, the array is shrunk if it becomes too empty.
• Approach 2: Two Dynamic Arrays
  • Idea: Use two standard dynamic arrays back-to-back. One stores the first half of the sequence, and the second stores the second half in reverse order.
  • Operations: An insertion to the front of the sequence is an append to the second array. An insertion to the back is an append to the first array. These are Θ(1) amortized.
  • Rebalancing: If one array becomes empty due to repeated deletions, a Θ(n) rebalancing operation is triggered. The remaining array is split in half, and its contents are used to repopulate both arrays. Since this only happens after Θ(n) deletions, its cost is also amortized to Θ(1).

Problem 4: Reordering a Singly Linked List
This is a coding problem where a singly linked list containing 2n nodes must be modified. The task is to reverse the order of the last n nodes in Θ(n) time and with Θ(1) extra space (meaning no new nodes or large data structures can be created).

• High-Level Algorithm:
  1. Find the Midpoint: Traverse the list to locate the n-th node. This node marks the end of the first half.
  2. Reverse the Second Half: Starting from the (n+1)-th node, iterate through the remainder of the list, reversing the next pointers. This requires carefully managing pointers to the previous, current, and next nodes to avoid breaking the chain.
  3. Stitch the Halves Together: After the reversal, connect the next pointer of the n-th node to the new head of the reversed second half (which was the original tail of the list). Set the next pointer of the new tail (the original (n+1)-th node) to None.

Jason Ku then performs a live coding demonstration of this solution in Python, successfully implementing the logic and passing all test cases.

L4: Sets and Sorting

The lecture is delivered by the third instructor, Justin. He begins by revisiting a core theme from the first lectures: the distinction between an interface and a data structure.

• Interface: This is the what. It's a specification of the operations a program should support, without detailing how they are implemented. It defines how a user interacts with the object.
• Data Structure: This is the how. It is the concrete implementation that stores data and provides the algorithms to execute the operations defined in the interface.

This distinction is crucial because a single interface (like a set) can be implemented by many different data structures, each with its own trade-offs in efficiency and memory usage.
2. The Set Interface
The main focus of the lecture is the Set Interface, which is conceptually a container for a collection of items.

• Items and Keys: Each item in the set is an object (x) that contains various pieces of information. One specific piece of that information is designated as the key (k), which is used for searching and ordering. The analogy used is a set of students, where each student is an object and their student ID is the key.
• Core Operations: A set interface should support operations such as:
  • build(A): Creates a set from a collection of items.
  • len(): Returns the number of items in the set.
  • find(k): Searches for and returns the item with the specified key k.
  • insert(x): Adds a new item x to the set.
  • delete(x): Removes an item from the set.
  • find_min() / find_max(): Finds the item with the smallest or largest key.

3. Data Structures for Implementing a Set
Two initial data structures are proposed to implement the set interface, highlighting a key performance trade-off.
Data Structure 1: Unsorted Array

• Implementation: Simply store all items in an array in no particular order.
• Performance:
  • build: Takes Θ(n) time to allocate memory and copy items.
  • find(k): Requires a linear scan of the entire array, taking Θ(n) time in the worst case.
  • find_min(): Also requires a linear scan, taking Θ(n) time.
  • Conclusion: This implementation is simple but inefficient for most query operations.

Data Structure 2: Sorted Array

• Implementation: Store items in an array, but keep them sorted based on their keys.
• Performance:
  • find(k): Can use binary search, which is much more efficient, taking only Θ(log n) time.
  • / : Are extremely fast, taking Θ(1) time by simply looking at the first or last element.
  • The Catch (: The major trade-off is that creating this data structure requires sorting the initial collection of items, which is computationally more expensive than just creating an unsorted list.

This realization shifts the focus of the lecture to the sorting problem: how can we efficiently take an unsorted array and sort it?
4. Sorting Algorithms
The lecture explores three sorting algorithms to understand their efficiency.
Algorithm 1: Permutation Sort (A "Bad" Example)

• Method:
  1. Generate every possible permutation of the input array.
  2. For each permutation, check if it is sorted.
• Analysis: There are n! permutations. Checking if a single permutation is sorted takes Θ(n) time. Therefore, the total runtime is at least Ω(n * n!), making it completely impractical.

Algorithm 2: Selection Sort

• Method:
  1. Find the largest element in the unsorted portion of the array.
  2. Swap it with the element at the end of the unsorted portion.
  3. Shrink the unsorted portion by one and repeat until the entire array is sorted.
• Analysis (Recursive View): The algorithm is presented recursively for easier analysis. To sort an array of size n, you must first sort the subarray of size n-1 and then perform Θ(n) work to find and place the largest element. This leads to the recurrence relation: T(n) = T(n-1) + Θ(n).
• Runtime: This recurrence solves to Θ(n²). This is a significant improvement over permutation sort but is still not optimal.

Algorithm 3: Merge Sort (The "Good" Example)

• Method: This algorithm uses a "divide and conquer" strategy.
  1. Divide: Split the n-element array into two subarrays of n/2 elements each.
  2. Conquer: Recursively call merge sort on the two subarrays until you are left with arrays of size 1 (which are inherently sorted).
  3. Combine (Merge): Merge the two sorted subarrays back into a single, sorted array.
• The Merge Step: The key to this algorithm is the efficient merging process. Using a "two-finger" algorithm, you can merge two sorted subarrays in linear time. You place pointers at the start of each subarray, compare the elements, copy the smaller one to the output array, and advance that pointer. This is repeated until all elements are copied. The merge step takes Θ(n) time.
• Analysis: The runtime is described by the recurrence relation T(n) = 2T(n/2) + Θ(n). Using the substitution method, this is shown to solve to Θ(n log n).

This n log n runtime is a major benchmark for comparison-based sorting algorithms and makes the Sorted Array a highly efficient and practical data structure for implementing the Set Interface.

L5: Hashing

The lecture begins by revisiting the Set Interface, which stores items and allows them to be queried by their intrinsic key. Previous data structures for this interface were:

• Unsorted Array: find operations take Θ(n) time.
• Sorted Array: Requires an Θ(n log n) build time (for sorting), but find operations are much faster at Θ(log n) using binary search.

The central question for the lecture is: Can we make
2. A Lower Bound for Comparison-Based Search
First, a theoretical limit is established. Within the Comparison Model of computation, the answer is no.

• The Comparison Model: This is a restricted model where the only way to gain information about keys is by comparing two of them (e.g., is key1 < key2?). All the sorting algorithms from the previous lecture operated within this model.
• The Decision Tree Argument: Any comparison-based search algorithm can be represented as a binary decision tree.
  • Each internal node represents a comparison.
  • The two branches from a node represent the two possible outcomes (e.g., true/false).
  • The leaves of the tree represent the final outputs of the algorithm.
• Required Outputs: For a correct search algorithm on a set of n items, there must be at least n + 1 possible outputs (one for each of the n items it could return, plus one for "item not found").
• The Lower Bound: The worst-case number of comparisons is the height of the decision tree. The minimum height of a binary tree with n+1 leaves is Ω(log n). Therefore, any search algorithm in the comparison model must take at least

3. Breaking the Barrier: The Direct Access Array
To achieve a search time faster than log n, we must use an operation that is outside the comparison model. The Word RAM model provides such an operation: constant-time random memory access.
This leads to the idea of a Direct Access Array:

• Concept: To store an item with an integer key k, place it in an array at index k.
• Performance: find(k), insert(k), and delete(k) are all Θ(1) operations. This is a massive improvement.
• The Critical Flaw: Space. This approach is only feasible if the keys are small, non-negative integers. If the universe of possible keys (U) is very large (e.g., 9-digit student IDs), then the array would need to be of size U. If U is much larger than the number of items being stored (n), this results in an unacceptable waste of space.

4. The Core Idea of Hashing
Hashing is the solution to the space problem of direct access arrays.

• Concept: Instead of an array of size U, we allocate a smaller array (the hash table) of size m, where m is proportional to n (i.e., m = Θ(n)).
• Hash Function: A hash function, , is used to map a key k from the large universe U to an index in the smaller hash table [0, ..., m-1].
• The New Problem: Collisions. By the pigeonhole principle, since U > m, it is inevitable that multiple keys will map to the same index. This is called a collision.

5. Collision Resolution by Chaining
The lecture focuses on one strategy for handling collisions: Chaining.

• Concept: The hash table is not an array of items, but an array of pointers. Each pointer at index i points to the head of a separate data structure (a "chain," such as a linked list or dynamic array) that stores all the items whose keys hash to i.
• Operation:
  1. To find(k), you first compute the index i = h(k).
  2. You then go to table[i] and perform a linear search on the chain to find the item with key k.
• Performance: The efficiency of this scheme depends entirely on the length of the chains. If the chains are short (ideally constant length), the operations will be fast. If they are long, performance degrades to Θ(n).

6. Universal Hashing: The Power of Randomness
The key to keeping chains short is to use a good hash function.

• The Problem with Deterministic Functions: Any fixed, deterministic hash function (like the simple division method, h(k) = k mod m) is vulnerable. An adversary who knows the function can intentionally choose a set of keys that all hash to the same index, forcing the worst-case Θ(n) behavior.
• The Solution: Randomization. Instead of using one fixed function, we define a family of hash functions and choose one randomly when we initialize the hash table. This makes it impossible for an adversary to reliably choose a bad set of keys, because they don't know which hash function is in use.

This leads to the concept of Universal Hashing.

• Definition: A family of hash functions H is universal if for any two distinct keys k_1 ≠ k_2, the probability that h(k_1) = h(k_2) is at most 1/m, where the probability is taken over the random choice of h from the family H.
• Example Function: The lecture provides an example of a universal hash function family: h_ab(k) = ((ak + b) mod p) mod m, where p is a prime number larger than any key in U, and a and b are integers chosen randomly.

7. Analysis and Dynamic Hashing
Using a universal hash family gives a powerful probabilistic guarantee.

• Expected Chain Length: The expected length of any chain can be proven to be 1 + (n-1)/m.
• Constant Time Performance: If we maintain the table size m to be proportional to the number of items n (i.e., m = Θ(n)), then the expected chain length is a constant (Θ(1)). This means find, insert, and delete all run in expected constant time.
• Dynamic Resizing: To handle a changing number of items n, the hash table can be made dynamic, just like a dynamic array. When n grows too large for the current table size m, a new, larger table is allocated, a new hash function is chosen randomly, and all existing items are re-inserted. This rebuilding process adds an amortized cost, but the operations remain in expected constant time.

L6: PS 2

The session, led by instructor Justin, aims to provide practical examples of how to approach and solve problems similar to those on homework assignments and exams. The focus is on translating problem descriptions into algorithmic tasks and applying the theoretical concepts learned in lectures.
Problem 1: Solving Recurrences with the Master Theorem
This problem focuses on solving recurrence relations, which are fundamental to analyzing the runtime of recursive algorithms. The primary tool used is the Master Theorem, a "sledgehammer" formula for solving recurrences of the form T(n) = aT(n/b) + f(n). Two methods are demonstrated for each part: direct application of the Master Theorem and analysis using a recursion tree.
Review of the Master Theorem
The theorem compares the function f(n) (the work done at each step) to the critical function n^(log_b a).

1. Case 1: If f(n) is polynomially smaller than n^(log_b a), then T(n) = Θ(n^(log_b a)).
2. Case 2: If f(n) is asymptotically equal to n^(log_b a), then T(n) = Θ(n^(log_b a) * log n).
3. Case 3: If f(n) is polynomially larger than n^(log_b a), then T(n) = Θ(f(n)).

Part A: T(n) = 2T(n/2) + O(sqrt(n))

• Master Theorem Application:
  • Here, a=2, b=2, so the critical function is n^(log_2 2) = n^1 = n.
  • The work function is f(n) = O(sqrt(n)) = O(n^0.5).
  • Since n^0.5 is polynomially smaller than n^1, this falls into Case 1.
  • The solution is T(n) = Θ(n).
• Recursion Tree Method:
  • The tree has log_2 n levels.
  • At level l, there are 2^l nodes, each doing sqrt(n/2^l) work.
  • The total work at level l is 2^l * sqrt(n/2^l) = sqrt(n) * (sqrt(2))^l.
  • The total work for the entire algorithm is the sum of a geometric series over all levels. The sum evaluates to Θ(n), confirming the Master Theorem result.

Part B: T(n) = 8T(n/4) + O(n * sqrt(n))

• Master Theorem Application:
  • Here, a=8, b=4, so the critical function is n^(log_4 8) = n^(3/2).
  • The work function is f(n) = O(n * sqrt(n)) = O(n^(3/2)).
  • Since f(n) is asymptotically the same as the critical function, this falls into Case 2 (with k=0).
  • A key detail is noted: because the problem statement gives O(f(n)) and not Θ(f(n)), the final result can only be stated as an upper bound.
  • The solution is T(n) = O(n^(3/2) * log n).
• Recursion Tree Method:
  • The tree has log_4 n levels.
  • At level l, there are 8^l nodes, and the work done at each node simplifies such that the total work per level is constant: Θ(n^(3/2)). This is a characteristic of Case 2.
  • The total work is the work per level multiplied by the number of levels: (log_4 n) * n^(3/2). This matches the Master Theorem result, O(n^(3/2) log n).

Problem 2: The Infinity Stones Search
This problem requires finding an unknown planet with index k in an infinite, ordered set of planets (1, 2, 3, ...). The only allowed operation is to query an oracle on any planet p to learn if k is greater or smaller than p. The goal is an O(log k) runtime.

• Challenge: Standard binary search is not possible because there is no upper bound on the search space. A simple linear scan would take O(k) time, which is too slow.
• Solution (Two-Phase Approach):
  1. Phase 1: Find an Upper Bound. Perform an exponential search to find a range that contains k. Query the planets at indices 2^0, 2^1, 2^2, ... until an index 2^m is found such that k ≤ 2^m. This process takes m steps. Since 2^(m-1) < k, taking the log reveals that m < log k + 1, so this phase runs in O(log k) time.
  2. Phase 2: Binary Search. Once the search is narrowed down to the range [2^(m-1), 2^m], a standard binary search can be performed within this range to find k. This also takes O(log(2^m)) = O(m) = O(log k) time.

The total time is O(log k) + O(log k) = O(log k), which meets the requirement.
Problem 3: Fadobe Image Editor
This problem involves designing a data structure to manage layers in an image editor. It must support several operations with specific runtime constraints, most notably a move_below(x, y) operation in O(log n) time.

• Challenge: The O(log n) requirement for finding and moving an arbitrary layer x suggests a search-efficient structure (like a sorted array), while the need to maintain a specific display order suggests a sequence structure (like a linked list).
• Solution (Hybrid Data Structure):
  1. A doubly-linked list is used to store the images in their correct display order (the sequence). This allows for efficient O(1) removal and insertion of nodes once you have a pointer to them.
  2. A sorted array (or a balanced binary search tree) is used to store the image IDs (the set). This allows for fast O(log n) lookups to find any image by its ID.
  3. The "Glue": The key insight is to have the sorted array store not just the image IDs, but also direct pointers to the corresponding nodes in the doubly-linked list.
• How
  1. Use binary search on the sorted array to find the entries for image IDs x and y. This takes O(log n) time.
  2. Retrieve the pointers to their respective nodes in the linked list.
  3. Use these pointers to perform the necessary rewiring (splicing x out of its current position and inserting it after y) in the linked list. This takes O(1) time.
     The total time is dominated by the search, resulting in an O(log n) runtime.

Problem 4: The Brick-Blowing Wolf
This problem, wrapped in a story, asks for an efficient algorithm to calculate "damage." The core task is: for each element H[i] in an array, count how many elements H[j] (where j > i) are smaller than H[i].

• Part B - A "Special" Case: The problem adds a constraint: the array of houses is "special," meaning it is sorted ascending, except for a single dip. This effectively means the array is composed of two concatenated sorted subarrays, A and B. The goal is to solve the problem in O(n) time.
• Key Observations for the Special Case:
  1. A house in the right subarray B can only ever damage itself, as B is sorted ascending.
  2. A house in the left subarray A can only damage houses in B.
  3. As we iterate through A from left to right, the values A[i] are increasing. This means the number of houses in B that can be damaged is non-decreasing.
• Solution (
  1. Find the "dip" in O(n) time to identify the two subarrays A and B.
  2. Use two pointers: i for A and j for B.
  3. Iterate i from the start to the end of A. For each A[i], advance j through B as long as B[j] < A[i]. The number of elements that A[i] can damage in B is given by the final position of j.
  4. The crucial optimization is that j never resets. Since A[i] is always increasing, the search for the next i can resume from where j left off.
  5. Because both pointers i and j only traverse their respective arrays once, the total runtime is O(n).

L7: Linear Sorting

The lecture begins with a review of the previous session on hashing and its place among implementations of the Set Interface.

• The Problem with Comparison-Based Search: It was proven that in the Comparison Model (where information is only gained by comparing keys), any search algorithm has a lower bound of Ω(log n) time due to the nature of decision trees.
• Beating the Lower Bound: The Word RAM model offers a more powerful operation—random memory access—which allows for the Direct Access Array. This data structure achieves Θ(1) time for find, insert, and delete operations.
• The Space Issue and Hashing: The major drawback of a Direct Access Array is its space requirement, which is proportional to the universe of keys (U). Hashing solves this by mapping the large key space U to a smaller table of size m = Θ(n). By using a universal hash family (choosing a hash function randomly), hashing achieves expected time for its core operations.
• Worst-Case Performance: It's highlighted that the worst-case performance of a hash table is Θ(n), as a bad random choice or a malicious input could cause all items to collide in the same chain. This makes it unsuitable for applications requiring guaranteed worst-case performance.

2. A Lower Bound for Comparison-Based Sorting
The lecture then shifts focus from searching to sorting and asks if the Θ(n log n) runtime of Merge Sort can be improved upon.

• The Decision Tree Argument for Sorting: The same logic used for the search lower bound is applied to sorting.
  • Outputs of a Sorting Algorithm: The output of a sorting algorithm is a specific permutation of the input. For an input of size n, there are n! possible permutations (possible outputs).
  • Leaves of the Tree: A correct comparison-based sorting algorithm must have a decision tree with at least n! leaves to be able to produce any possible permutation.
  • Height of the Tree: The minimum height of a binary tree with n! leaves is log(n!).
  • The Lower Bound: Using Stirling's approximation or other bounding techniques, log(n!) is shown to be Ω(n log n).
• Conclusion: Within the Comparison Model, no sorting algorithm can perform better than Ω(n log n). Therefore, Merge Sort is asymptotically optimal for comparison-based sorting.

3. Sorting in Linear Time: Direct Access Array Sort
To sort faster than n log n, one must step outside the Comparison Model and use integer properties and random access.

• Concept ("Direct Access Array Sort"):
  1. Create a direct access array with a size equal to the universe of keys, U.
  2. For each of the n input items with a unique integer key k, place the item at index k in the array. This takes O(n) time.
  3. Iterate through the direct access array from index 0 to U-1, collecting the items in the order they appear. This takes O(U) time.
• Runtime and Limitation: The total runtime is O(n + U). This is a linear time sort, O(n), if and only if the universe of keys . This is a powerful but highly restrictive condition.

4. Radix Sort: Handling Larger Keys
The lecture then explores how to sort integers from a larger key space, for example, U ≤ n².

• The Core Idea (Tuple Sort): The key is to decompose large numbers into a tuple of smaller "digits." A number k < n² can be represented in base n with two digits, (a, b), where k = a*n + b. Sorting the numbers is now equivalent to sorting these tuples.
• The Importance of Stability: A sorting algorithm is stable if it preserves the relative order of elements that have equal keys. When sorting tuples, the correct approach is:
  1. Sort by the least significant digit first.
  2. Then, sort by the most significant digit using a stable sorting algorithm.
     The stability of the second sort ensures that for items with the same most significant digit, their pre-sorted order (based on the least significant digit) is maintained.

5. Counting Sort: A Linear-Time Stable Sort
To implement Radix Sort, a stable, linear-time sorting subroutine is needed. Counting Sort fits this requirement perfectly.

• Concept: Counting sort is designed for sorting integers within a specific range (e.g., 0 to U-1).
• Algorithm:
  1. Create a direct access array (the "counts" array) of size U.
  2. Instead of storing items directly, each index k of this array will hold a chain (e.g., a dynamic array or linked list) of all items whose key is k.
  3. Iterate through the n input items. For each item with key k, append it to the chain at index k. Appending to the end of the chain is crucial as it preserves the original order, making the algorithm stable.
  4. Iterate through the counts array from 0 to U-1. For each index, read out all the items from its chain in order.
• Runtime: The algorithm takes O(n + U) time and is stable.

6. Radix Sort: The Final Algorithm
Radix Sort combines the tuple sort idea with Counting Sort as its subroutine.

• Algorithm: To sort integers from a universe of size U:
  • Choose a "radix" or base, typically n. Represent each integer as a tuple of d = log_n(U) digits.
  • Iterate d times, from the least significant digit to the most significant.
  • In each iteration, use Counting Sort to stably sort all n items based on their value for the current digit. Since each digit is in the range [0, n-1], the U for Counting Sort is n, and each pass takes O(n+n) = O(n) time.
• Runtime Analysis:
  • The total time is the number of passes (digits) multiplied by the time per pass: O(d * n) = O(n * log_n(U)).
  • This runtime simplifies to linear time ( (i.e., U = n^c for some constant c). In this case, log_n(U) = log_n(n^c) = c, which is a constant, making the runtime O(c * n) = O(n).

Conclusion: Radix Sort provides a way to sort integers in linear time, breaking the n log n barrier by avoiding comparisons and leveraging the integer nature of the keys, but only when the keys are not exponentially larger than the number of items.

L8: PS 3

The session, led by instructor Erik Demaine, focuses on solving more creative and conceptual problems related to hashing and sorting, skipping a more mechanical introductory problem to focus on algorithmic thinking. The general approach for each problem is outlined as:

1. Translate the word problem into a formal algorithmic goal.
2. Brainstorm ideas and strategies.
3. Verify the details and analyze the final solution.

Problem 3.2: Hash Sequence
Goal: Implement a sequence data structure using a set data structure (specifically, a hash table) as a black box. The implementation must meet specific runtime requirements for various sequence operations.

• Brainstorming & Initial Idea: The core challenge is to represent the extrinsic order of a sequence using an intrinsically unordered set. A natural idea is to use the sequence's index as the key for each item stored in the hash table.
  • This works well for get_at(i) and set_at(i), which can be implemented in O(1) expected time by calling the hash table's find(i) operation.
  • insert_at and delete_at are given a generous linear time budget, which allows for a simple (though inefficient) solution: extract all items into an array, perform the operation, and then rebuild the entire hash table from scratch.
• The Problem: This simple indexing scheme fails for insert_first and delete_first, which must be O(1) amortized. Inserting a new item at the "front" would require giving it key 0. However, an item with key 0 already exists. To fix this, all existing items would need to be re-keyed (key 0 becomes 1, 1 becomes 2, etc.), which is a Θ(n) operation.
• The Solution (Floating Index):
  • Instead of fixing the first logical index to key 0, introduce a variable, first, which tracks the key that corresponds to the beginning of the sequence.
  • To implement insert_first(x), simply decrement the first variable (e.g., from 0 to -1) and insert the new item x with this new key. delete_first is the reverse: delete the item with the key first and then increment first.
  • All other index-based operations must be adjusted with this offset. For example, get_at(i) becomes a call to find(first + i).
  • This strategy allows for constant-time updates at both ends of the sequence by simply changing an integer offset, thereby avoiding the need to re-key all n elements.

Problem 3.3: Critter Sort (A Pokémon Parody)
Goal: For n "critters," determine the fastest correct sorting algorithm for four different types of keys. This problem tests the ability to choose between comparison-based sorts (like Merge Sort) and integer-based sorts (like Radix Sort).

• Part A: Integers in
  • The keys are small integers, making Radix Sort a strong candidate. However, Radix Sort requires non-negative integers.
  • Solution: Transform the keys by adding n to each one. This shifts the range to [0, 2n]. Since the universe of keys U is now O(n), Radix Sort can sort them in linear time.
• Part B: Strings of length
  • The strings can be treated as numbers in base 26.
  • Solution: The most efficient method is to map each entire string to a single large integer. The maximum value of this integer is roughly 26^(10 log n), which simplifies to n^c for some constant c. Since the universe of keys is polynomial in n, Radix Sort (using a base of n) can sort these numbers in linear time.
• Part C: Integers in
  • This is a textbook case where the universe U = n^2 is polynomial in n.
  • Solution: Radix Sort runs in linear time.
• Part D: Rational Numbers
  • The keys are not integers, so Radix Sort cannot be directly applied.
  • Solution: A comparison-based sort like Merge Sort can be used. To compare two rationals w_i/f_i and w_j/f_j without using floating-point arithmetic, one can use cross-multiplication: compare the integer products w_i * f_j and w_j * f_i.
  • Solution: To use Radix Sort, the rationals must be converted to integers while preserving their order.
  1. First, determine the minimum possible distance between any two distinct rationals. The difference |w_i/f_i - w_j/f_j| is shown to be at least 1/n^4.
  2. This means if we multiply every rational by n^4 and take the floor, any two distinct rationals will map to distinct integers, preserving their relative order.
  3. The resulting integer keys are in a range of [0, n^6]. Since this universe is polynomial in n, Radix Sort can sort them in linear time.

Problem 3.4: Cube Summing
Goal: Given a set S of n non-negative integers and a target h, find a pair of numbers in S that sum to a value related to h.

• Part A: Find a pair
  • The phrase "linear expected time" is a strong hint for using a hash table.
  • Solution:
    1. Build a hash table containing all the numbers in S. This takes O(n) expected time.
    2. Iterate through S one more time. For each number s_i, calculate the required complement h - s_i.
    3. Use the hash table's find operation to check if this complement exists in S. This check takes O(1) expected time.
    4. The total runtime is O(n) for the build step plus n constant-time lookups, for a total of expected time.
• Part B: Find a pair
  • "Linear worst-case" rules out hashing. The additional information that h is polynomial in n hints at Radix Sort.
  • Solution:
    1. Filter the set S to remove any numbers greater than h, as they cannot be part of a valid solution. This takes O(n).
    2. Sort the filtered set using Radix Sort. This takes O(n) worst-case time because the keys are bounded by h, which is polynomial in n.
    3. Use a two-finger algorithm on the sorted array. Initialize one pointer i at the beginning (smallest element) and another pointer j at the end (largest element).
    4. While i < j:
       • If s_i + s_j > h, the sum is too large. Decrement j to try a smaller sum.
       • If s_i + s_j ≤ h, the sum is a valid candidate. Record it as the best-so-far if it's better than the current best. Then, increment i to try for a larger sum.
    6. This two-finger scan takes O(n) time, making the total runtime worst-case.

Problem 3.5: Po-k-er Hands
Goal: Analyze a card-dealing process where a deck is cut randomly, k cards are dealt, and then sorted to form a "hand."

• Part A: Build a data structure that, after pre-processing, can determine in
  • Key Insight: Because the dealt cards are sorted, what defines a hand is not the sequence of cards, but the frequency of each letter (e.g., three 'A's, one 'B', zero 'C's). This can be represented by a frequency table of 26 integers.
  • Solution:
    1. Pre-computation: We can compute the frequency table for all n possible starting cuts.
    2. Use a sliding window approach: compute the frequency table for the first k cards (O(k) time). Then, slide the window one position at a time by decrementing the count for the character leaving the window and incrementing the count for the character entering. Each slide takes O(1). The total pre-computation time is O(n+k).
    3. Store these 26-element frequency tables in an array.
    4. Query: To compare the hands from cuts i and j, simply compare their pre-computed frequency tables element by element. Since the tables have a constant size (26), this comparison takes time.
• Part B (briefly discussed): To find the most common hand, one can treat each 26-element frequency table as a large integer and sort them using Radix Sort. Once sorted, a single linear scan can find the longest contiguous block of identical hands.

L9: Binary Trees 1

The lecture begins by reviewing the data structures covered so far and their limitations, setting the stage for a more powerful solution: binary trees.

• Sequence Interface Limitations:
  • Data structures like arrays and linked lists are efficient for operations at the ends of a sequence (e.g., insert_last).
  • However, they are inefficient for operations in the middle of a sequence.
    • Linked Lists: Suffer from slow access, taking linear time to reach the middle.
    • Arrays: Suffer from expensive updates, requiring a linear-time shift of elements for any insertion or deletion in the middle.
• Set Interface Limitations:
  • Hash Tables: Are excellent for exact searches (find), insertions, and deletions in expected constant time. However, they are very poor at "inexact" searches like find_previous or find_next (finding the closest keys to a search key that isn't in the set).
  • Sorted Arrays: Excel at both exact and inexact searches (O(log n)) using binary search. However, they are terrible for dynamic operations (insert, delete) because maintaining the sorted, gapless structure requires linear-time shifts.
• The Goal: The lecture introduces the goal of building a single data structure, the binary tree, that can achieve the "best of all worlds": logarithmic time for nearly all sequence and set operations, effectively combining the dynamic nature of linked lists and hash tables with the ordered search capabilities of sorted arrays.

2. What is a Binary Tree?
A rooted binary tree is defined as a collection of nodes connected by pointers.

• Node Structure: Each node x contains:
  • An item.
  • A parent pointer.
  • A left child pointer.
  • A right child pointer.
• Key Invariant: The pointers are bi-directional. For any node x, x.left.parent points back to x.
• Terminology:
  • Root: The unique node with no parent.
  • Leaf: A node with no children.
  • Ancestors/Descendants: Familial terms for nodes "above" or "below" a given node in the tree.
  • Subtree: A node and all of its descendants.
  • Depth: The number of edges on the path from the root down to a node.
  • Height: The number of edges on the longest path from a node down to one of its descendant leaves. The height of the tree (h) is the height of the root.

The primary advantage of a tree structure over a list is its potential for a low height (h). While a list-like tree has h = O(n), a balanced tree can achieve h = O(log n), enabling fast traversal from the root to any node.
3. The In-Order Traversal: An Implicit Sequence
The crucial concept that allows a tree to represent a linear order is the in-order traversal.

• Definition: For any node x, all nodes in its left subtree come before x in the traversal order, and all nodes in its right subtree come after x.
• This property recursively defines a unique, total ordering of all the nodes in the tree.
• Key Point: This order is implicit. It is defined by the tree's structure, not stored in an explicit array. This allows the order to be modified efficiently by changing pointers, rather than shifting elements.

4. Basic Tree Operations (Runtime: O(h))
The lecture introduces several fundamental operations for navigating and manipulating the tree, all of which run in time proportional to the height of the tree, O(h).

• : Finds the first node in the traversal order within that node's subtree.
  • Algorithm: Repeatedly follow left child pointers until you can go no further.
• : Finds the next node in the entire tree's traversal order.
  • Algorithm (Two Cases):
    1. If the node has a right child, the successor is the subtree_first of that right child.
    2. If the node has no right child, walk up the tree using parent pointers until you traverse a left branch for the first time. That parent is the successor.
• : Inserts a new node into the tree immediately after a given node in the traversal order.
  • Algorithm (Two Cases):
    1. If node has no right child, make new_node its right child.
    2. If node has a right child, find the successor of node and make new_node its left child (this spot is guaranteed to be empty).
• : Removes a node from the tree while maintaining the integrity of the tree structure.
  • Algorithm (Two Cases):
    1. If the node is a leaf: Simply detach it from its parent.
    2. If the node is not a leaf: You cannot simply remove it. Instead, swap its item with the item of its predecessor (or successor). Then, recursively call delete on that predecessor/successor node. This process continues until a leaf is deleted, effectively moving the "hole" down the tree until it can be easily removed.

5. Connecting Trees to the Set and Sequence Interfaces
The final part of the lecture connects these tree operations back to the high-level interfaces.

• For the Sequence Interface: The tree's traversal order is used to represent the sequence's specified order.
• For the Set Interface: The tree's traversal order represents the sorted order of the items' keys. This gives rise to the Binary Search Tree (BST) Property:
  • BST Property: For any node x, all keys in its left subtree are less than x.key, and all keys in its right subtree are greater than x.key.
  • : This property allows for an efficient binary search on the tree. Start at the root, compare the search key k to the node's key, and go left if k is smaller or right if k is larger. This takes O(h) time.
  • / The binary search path naturally leads to the location where the key should be. The predecessor and successor operations can then be used to find the nearest keys if the exact key is not found.

Today's Conclusion: All fundamental set and sequence operations can be implemented to run in O(h) time. The next lecture will focus on techniques to guarantee that the tree's height , thus achieving the final goal of logarithmic time performance.

L10: Binary Trees 2

The lecture begins with a recap of the previous session on binary trees.

• Structure: A binary tree consists of nodes, each containing an item and pointers to a parent, left child, and right child.
• Height (h): The height of the tree is the length of the longest path from the root to a leaf. The operations developed last time (successor, insert, delete, etc.) all run in time proportional to the height, O(h).
• In-Order Traversal: Trees implicitly define a linear ordering of their items through the in-order traversal (left subtree, root, right subtree). This is the key to using trees to represent sequences and sorted sets.

2. Binary Trees for Sets and Sequences
The lecture clarifies how binary trees are used to implement the two main interfaces.

• Set Binary Trees (Binary Search Trees - BSTs):
  • The tree's traversal order is maintained to be the sorted order of the item keys.
  • This leads to the Binary Search Tree (BST) Property: for any node, all keys in its left subtree are smaller, and all keys in its right subtree are larger.
  • This property allows for a tree-based binary search (find) in O(h) time.
• Sequence Binary Trees:
  • The tree's traversal order is maintained to be the specified order of the sequence.
  • To perform index-based operations like get_at(i) or insert_at(i), the tree needs additional information.

3. Subtree Augmentation: The Key to Sequences
To make sequence operations efficient, a powerful technique called subtree augmentation is introduced.

• Concept: Store extra, pre-computed information in each node.
• Subtree Property: A property is a "subtree property" if the value for a node can be computed in O(1) time from the values of its children (and the node itself).
• Example: The number of nodes in a node's subtree is a classic subtree property. The size of a node can be calculated as node.size = node.left.size + node.right.size + 1.
• Maintaining Augmentations: When a leaf is added or removed, only the O(h) ancestors of that leaf are affected. We can walk up the tree from the leaf to the root, re-calculating the augmented property at each step. This allows all augmented data to be kept up-to-date in O(h) time per modification.

With the size property augmented on every node, the get_at(i) operation can be implemented efficiently. By comparing the target index i to the size of the left subtree, we can decide whether to go left, right, or stop (if the root is the target) in O(1) time at each step, leading to an overall O(h) runtime.
4. The Problem: Unbalanced Trees
The major unresolved issue is that all operations run in O(h) time. While a "perfect" binary tree has h = O(log n), a degenerate, list-like tree can have h = O(n). The goal is to keep the tree balanced to guarantee that h is always O(log n).
5. Rotations: The Rebalancing Tool
A new tree manipulation tool is introduced: rotations.

• Concept: A rotation is a local O(1) pointer restructuring operation that changes the parent-child relationship between two nodes. A "right rotate" on node y makes its left child x become y's new parent. A "left rotate" is the inverse.
• Crucial Property: Rotations preserve the in-order traversal of the tree. This means we can change the tree's shape (and thus its height) without altering the fundamental order it represents. This is the key to rebalancing.

6. AVL Trees: Height-Balanced Trees
AVL trees are a specific type of self-balancing binary search tree that uses rotations to maintain a strict balance property.

• The Height-Balance Property: For every node in the tree, the heights of its left and right subtrees can differ by at most 1. The difference height(right) - height(left) is called the skew. An AVL tree only allows skews of -1, 0, or +1.
• Height Guarantee: It is proven that any tree satisfying the height-balance property is guaranteed to have a logarithmic height: h ≤ 2 * log(n). The proof involves analyzing the minimum number of nodes N(h) required to form an AVL tree of height h, showing that N(h) grows exponentially with h (similar to Fibonacci numbers), which implies that h must grow logarithmically with N.

7. Maintaining the Height-Balance Property
The final challenge is to show how to maintain the height-balance property after an insertion or deletion.

• The Trigger: An insert or delete operation begins by adding or removing a leaf. This can change the heights of the O(h) ancestor nodes.
• The Fix:
  • After a modification, walk up the tree from the point of change to the root.
  • At each ancestor, update its augmented height. Then, check if its skew has become invalid (i.e., +2 or -2).
  • Find the lowest unbalanced node x. The goal is to perform one or two rotations to fix the balance at x.
• The Rotation Cases: Assume x has a skew of +2 (it is "right-heavy"). Let y be its right child.
  • Case 1 (Right-Right): If y is also right-heavy or balanced (skew +1 or 0), a single left rotation at x is sufficient to restore balance for the entire subtree.
  • Case 2 (Right-Left): If y is left-heavy (skew -1), a single rotation is not enough. This is the "hard case" or "zig-zag" case. The fix is a double rotation: first, a right rotation on y, followed by a left rotation on x. This restores balance.

After performing the appropriate rotation(s) at the lowest unbalanced node, the height of that subtree is restored to what it was before the modification. This remarkable property means that no further fixes are needed higher up the tree. The entire rebalancing process is completed by walking up the ancestor path once, taking O(h) time.
Conclusion
By augmenting nodes with their height and using rotations to fix imbalances, AVL trees guarantee that h remains O(log n). Since all the underlying sequence and set operations were shown to run in O(h) time, this means that AVL trees can perform all of these operations in worst-case time, achieving the "best of all worlds" goal.

L11: PS 4

Instructor Jason Ku begins by contextualizing the material. With the introduction of binary trees, the core set of data structures for implementing the Set and Sequence interfaces is now complete. He presents a performance comparison of these data structures (arrays, linked lists, dynamic arrays, hash tables, and balanced binary trees) by running a test script that measures the actual time taken for various operations. The results visually confirm the theoretical runtimes discussed in class:

• Arrays/Dynamic Arrays: Constant time (Θ(1)) for get_at/set_at.
• Linked Lists: Θ(1) for operations at the ends, but Θ(n) for middle access.
• Hash Tables: Fast expected times for dictionary operations but poor for ordered operations.
• Balanced Binary Trees (AVL Trees): The most versatile, achieving O(log n) for nearly all operations, making them a powerful general-purpose tool.

2. Problem 4-1: Sequence AVL Tree Deletion
This is a mechanical problem designed to test understanding of AVL tree operations on a sequence tree.

• Key Distinction: A sequence tree's traversal order is determined by insertion order, not by the values of the items. It is augmented with heights (for balancing) and subtree sizes (for index-based lookups).
• The Task: delete_at(8) from a given sequence AVL tree.
  1. Find the Node: The process of finding the node at index 8 is demonstrated. Starting at the root, the algorithm uses the augmented subtree sizes to navigate. For example, if the left subtree has 7 nodes, the root is at index 7. Since we are looking for index 8, we proceed to the right subtree, searching for the item at the new relative index 8 - 7 - 1 = 0. This continues until the node at index 8 is found.
  2. Delete and Rebalance: The node (containing the value 7) is deleted. This violates the AVL height-balance property at its parent node.
  3. Fixing Imbalance: The imbalance is a "zig-zag" or "right-left" case, which requires a double rotation to fix: first a right rotation on the child, then a left rotation on the parent.
  4. Propagating the Fix: After the first fix, the imbalance propagates up the tree. The next unbalanced ancestor is fixed with a single right rotation. After this second fix, the entire tree is once again height-balanced.

3. A Brief Note on Binary Heaps
A preview of binary heaps is given, as they will be relevant to an upcoming problem set. A heap is presented as a "black box" that implements a priority queue interface.

• Key Heap Operations and Runtimes:
  • build(X): O(n)
  • delete_max(): O(log n)
• This is contrasted with a Set AVL tree, which would take O(n log n) to build but also O(log n) for delete_max. The heap's linear-time build is its key advantage for certain applications.

4. Problem 4-2: Fick Nury's Revengers
This problem involves finding the log n superheroes with the most "extreme" opinions from a list of n opinions (positive or negative numbers).

• Part A:
  • The goal is to find the log n items with the largest absolute values.
  • Solution: This is a perfect application for the binary heap.
    1. Create an array of the absolute values of the n opinions (O(n) time).
    2. build a max-heap from this array (O(n) time).
    3. Call delete_max log n times to extract the log n largest values (O(log n * log n) time).
    4. The total time is dominated by the linear-time steps, resulting in an O(n) runtime.
• Part B:
  • The space constraint is the main challenge. We cannot build a heap on all n items.
  • Solution:
    1. Create a Set AVL tree to store only the log n most extreme opinions found so far. The tree is keyed on the absolute value of the opinion. The size of this tree is k = log n, so its height is log(k) = log(log n).
    2. Initialize the AVL tree with the first log n items from the input array. This takes O(log n * log(log n)) time.
    3. Iterate through the remaining n - log n items in the input. For each item:
       a. insert it into the small AVL tree.
       b. delete_min from the tree to maintain its size at log n.
    4. Each insert/delete pair takes O(height) = O(log(log n)) time. This is done O(n) times.
    5. The total runtime is O(n * log(log n)).

5. Problem 4-3: SCLR Auction
This problem requires designing a data structure to manage bids in an auction. It must support placing/updating bids and, crucially, retrieving the total revenue from the top k highest bids in O(1) time. Updates must be O(log n).

• Challenge: The data structure needs to be searchable by bidder ID but also ordered by bid amount, and the O(1) query for the sum of the top k bids is very strict.
• Solution (A Composite Data Structure):
  1. Dictionary of Bidders: A Set AVL tree (Bidders_by_ID) is used to map unique bidder_IDs to pointers. This allows for O(log n) lookup of any bidder.
  2. Two Bid Trees: Two more Set AVL trees are used, both keyed on the bid_amount.
     • Top_K: Stores the k bidders with the highest bids.
     • Rest: Stores the other n-k bidders.
  3. Augmented Sum: The Top_K tree is augmented with a total field in each node, storing the sum of all bids in its subtree. This allows the total sum of all bids in the Top_K tree to be retrieved in O(1) by looking at the root's total field. The get_revenue query is now solved.
  4. Update Logic: When a bid is updated or a new bid is placed:
     a. The bidder is found in Bidders_by_ID (O(log n)).
     b. The old bid is removed from its respective tree (Top_K or Rest).
     c. The new bid is inserted into the appropriate tree.
     d. To maintain the invariant that Top_K holds exactly the k highest bids, an item may need to be moved between the Top_K and Rest trees. This involves finding the minimum of Top_K and the maximum of Rest and potentially swapping them.
  5. All these operations involve a constant number of O(log n) tree modifications, so the total update time is O(log n).

6. Problem 4-4: Receiver Roster
This problem involves managing a roster of football players, each of whom has played in a set of games and scored points. The goal is to find the player with the k-th highest performance (average points per game).

• Challenge: This is a complex data organization problem. Performance is a rational number, requiring careful comparison. We need to find by receiver ID, but also rank by performance.
• Solution (Nested and Cross-Linked Data Structures):
  1. Outer Dictionary: A primary Set AVL tree (Receivers_by_ID) maps receiver_ID to a node containing receiver-specific data.
  2. Nested Game Data: For each receiver, their node in the outer dictionary contains a nested Set AVL tree (Games_by_ID) that stores the games they played in, keyed by game_ID.
  3. Augmentations for Performance: Each receiver's node is augmented with total_points and num_games. These values are updated whenever a game is added or removed from their nested game tree.
  4. Performance-Sorted Tree: A separate, top-level Set AVL tree (Receivers_by_Perf) stores all the receivers, but this one is keyed on performance.
     • Since performance is a rational number, comparisons are done via cross-multiplication to avoid floating-point issues.
  5. Cross-Linking: Pointers are used to link between the structures. The Receivers_by_ID tree contains pointers to the corresponding nodes in the Receivers_by_Perf tree, allowing for efficient updates.
  6. Finding the The Receivers_by_Perf tree is augmented with subtree sizes. This turns it into an order-statistic tree, allowing the k-th largest element (the (n-k)-th element in traversal order) to be found in O(log n) time, just like in a sequence AVL tree.

This complex, multi-layered solution demonstrates how different data structures and augmentation techniques can be combined to solve sophisticated query problems.

L12: Binary Heaps

The lecture begins by introducing the priority queue, an interface that is a subset of the more general Set Interface.

• Core Operations: A priority queue stores items with keys (priorities) and is primarily focused on two operations:
  • insert(x): Adds a new item.
  • delete_max(): Removes and returns the item with the highest priority (maximum key).
• Applications: This interface is useful in many real-world scenarios, such as network routers processing high-priority packets, operating systems scheduling processes, or event-driven simulations.

2. Existing Data Structures for Priority Queues
Several data structures already covered in the course could implement a priority queue, each with different performance trade-offs.

The goal is to find a data structure that combines the fast insertion of an unsorted array with the fast deletion of a sorted array, achieving O(log n) for both. While a Set AVL tree already does this, the lecture aims to find a simpler and more space-efficient solution.
3. The Motivation: In-Place Sorting
The primary motivation for developing a new data structure is to create a new, efficient sorting algorithm.

• Priority Queue Sort: A generic sorting algorithm can be built from any priority queue implementation:
  • insert all n items into the priority queue.
  • Call delete_max n times to extract the items in reverse sorted order.
• Connection to Known Algorithms: Applying this framework to existing data structures reveals that it unifies several sorting algorithms:
  • Using an unsorted array yields Selection Sort (O(n^2)).
  • Using a sorted array yields Insertion Sort (O(n^2)).
  • Using a Set AVL tree yields AVL Sort (O(n log n)).
• The Goal: The lecture aims to develop a priority queue implementation that, when used in this sorting framework, results in an O(n log n) sorting algorithm that is also in-place (using only O(1) extra space). This is something neither Merge Sort nor AVL Sort can achieve.

4. Binary Heaps: The Data Structure
The new data structure is the binary heap. It uniquely combines the properties of an array and a tree.

• Structure 1: The Array (Implicit Data Structure): A heap is stored as a single array of items with no explicit pointers. This makes it inherently in-place.
• Structure 2: The Complete Binary Tree (Conceptual View): The array is interpreted as representing a complete binary tree.
  • Complete Binary Tree: A tree where all levels are completely full, except possibly the last level, which is filled from left to right. This structure is crucial because it is always perfectly balanced (h = O(log n)).
  • Mapping Array Indices to Tree Nodes: A simple set of formulas allows navigation of this conceptual tree using only array index arithmetic, eliminating the need for pointers:
    • parent(i) = floor((i-1)/2)
    • left_child(i) = 2i + 1
    • right_child(i) = 2i + 2
• Structure 3: The Max-Heap Property: To make the structure useful as a priority queue, an ordering property is imposed on the keys.
  • Max-Heap Property: For every node i, the key of i is greater than or equal to the keys of both its children.
  • Implication: This property guarantees that the largest element in any subtree is always at the root of that subtree. Consequently, the maximum element in the entire heap is always at the root of the tree, which is array[0].

5. Heap Operations (Runtime: O(log n))
With the heap structure defined, the core priority queue operations are implemented.

• : This is an O(1) operation. Due to the max-heap property, the maximum element is always at the root, array[0].
  1. Place the new item x at the very end of the array (the next available leaf in the complete binary tree).
  2. This new item may violate the max-heap property if its key is larger than its parent's key.
  3. Fix this by repeatedly swapping the item with its parent until it is no longer larger than its parent or it reaches the root. This upward-swapping process is called max_heapify_up.
  4. The path from a leaf to the root has length O(h) = O(log n), so the runtime is O(log n).
  5. The maximum element is at the root (array[0]), but it cannot be easily removed without breaking the complete tree structure. The only element that can be easily removed is the last one.
  6. Swap the root element with the last element in the array.
  7. Remove the last element (which is now the original max element).
  8. The new root (the original last element) is likely small and violates the max-heap property.
  9. Fix this by repeatedly swapping the item with its larger child until it is no longer smaller than its children or it becomes a leaf. This downward-swapping process is called max_heapify_down.
  10. This also takes O(log n) time.

6. Heapsort and Linear-Time Build

• Heapsort: By plugging the binary heap into the priority queue sort framework, we get Heapsort. The n insertions and n deletions each take O(log n) time, resulting in an O(n log n) sorting algorithm that is also in-place. This achieves the primary goal of the lecture.
• in While building a heap by n successive insertions takes O(n log n), a more efficient "bottom-up" build method exists.

1. Start with the array A as a complete binary tree that does not yet satisfy the max-heap property.
2. Iterate through the nodes from the last non-leaf node up to the root.
3. For each node, call max_heapify_down to fix the heap property for the subtree rooted at that node.
4. A careful analysis shows that the total work done is a sum over the heights of the nodes, which surprisingly evaluates to O(n), not O(n log n). This is because most nodes are near the bottom of the tree (leaves) and require little to no work to heapify.

L13: Breadth-First Search

The lecture marks the beginning of the second part of the course, focusing on graph theory.

• Definition of a Graph: A graph G = (V, E) is defined as a pair of two sets:
  • V: A set of vertices (or nodes).
  • E: A set of edges, where each edge connects a pair of vertices.
• Types of Graphs:
  • Undirected Graph: Edges are unordered pairs. An edge {v, w} is the same as {w, v}. It simply represents a connection.
  • Directed Graph: Edges are ordered pairs. An edge (v, w) (from v to w) is distinct from (w, v). It represents a one-way connection.
• Applications: The instructor emphasizes that graphs are a ubiquitous abstraction for modeling networks and relationships in many domains, including computer networks, social networks, road networks, 3D models (triangle meshes), and even political redistricting.

2. Graph Terminology and Properties
Several key terms and properties are defined to build a formal vocabulary for discussing graphs.

• Simple Graphs: The course will primarily focus on simple graphs, which have two properties:
  • No self-loops (an edge from a vertex to itself).
  • No multiple edges between the same pair of vertices.
• Size of a Graph: A simple graph with |V| vertices can have at most O(|V|^2) edges. This relationship is important for analyzing the runtime of graph algorithms.
• Adjacency and Degree:
  • Two vertices are adjacent (or neighbors) if there is an edge between them.
  • For a vertex v, Adj(v) is the set of its neighbors.
  • Degree: The number of neighbors a vertex has. In directed graphs, this is split into:
    • In-degree: Number of incoming edges.
    • Out-degree: Number of outgoing edges.
• Sum of Degrees: A useful identity is that the sum of the degrees of all vertices is equal to 2 * |E| for undirected graphs and |E| for directed graphs (if summing out-degrees). This is because each edge contributes to the degree count of its endpoint(s).

3. Representing Graphs on a Computer
Different data structures can be used to store a graph, each with its own performance characteristics.

• Edge List: A simple list of all the edges in the graph. This is space-efficient but slow for queries like "does edge (v, w) exist?", which would take O(|E|) time.
• Adjacency Matrix: A |V| x |V| matrix where M[i][j] = 1 if an edge exists between vertex i and j, and 0 otherwise.
  • Pros: Very fast O(1) edge existence checks.
  • Cons: Requires O(|V|^2) space, which is inefficient for sparse graphs (where |E| << |V|^2). Iterating over a vertex's neighbors takes O(|V|) time, not proportional to its actual degree.
• Adjacency List: An array of size |V|, where each entry Adj[i] points to a data structure (like a linked list or hash table) containing the neighbors of vertex i.
  • This is the standard representation used in the course.
  • Pros: Space-efficient (O(|V| + |E|)). Iterating over a vertex's neighbors is efficient, taking time proportional to its degree.

4. The Shortest Path Problem
The lecture introduces the canonical problem of finding paths in a graph, specifically the shortest path.

• Path: A sequence of vertices (v_1, v_2, ..., v_k) where each adjacent pair (v_i, v_{i+1}) is an edge in the graph.
• Path Length: The number of edges in a path.
• Shortest Path Distance The minimum length of any path between a source vertex s and a target vertex t.
• Problem Variations:
  1. Single-Pair Reachability: Can s reach t?
  2. Single-Pair Shortest Path: What is the distance δ(s, t)?
  3. Single-Source Shortest Path (SSSP): For a given source s, what is the distance δ(s, v) for every other vertex v in the graph?

The lecture focuses on solving the SSSP problem, as its solution can be used to solve the other two.
5. The Shortest Path Tree and Level Sets

• Shortest Path Tree: Storing all |V| shortest paths explicitly would take O(|V|^2) space. A more efficient representation is the shortest path tree. For each vertex v, we only store its predecessor p(v) on a shortest path from the source s. By following these predecessor pointers backward, any shortest path can be reconstructed in O(|V|) time, while the entire tree only requires O(|V|) space.
• Level Sets A crucial concept for the upcoming algorithm is the level set , which is the set of all vertices whose shortest path distance from the source is exactly i.
  • L_0 contains only the source s.
  • L_1 contains all neighbors of s.
  • L_2 contains all neighbors of vertices in L_1 that haven't been visited yet, and so on.

6. Breadth-First Search (BFS)
Breadth-First Search (BFS) is the algorithm presented for solving the SSSP problem on an unweighted graph (where all edge lengths are assumed to be 1).

• Algorithm Idea: BFS systematically explores the graph layer by layer, computing the level sets L_0, L_1, L_2, ... in order.
  • Initialize L_0 = {s} and the distance δ(s, s) = 0.
  • For i = 1, 2, ...:
    a. The next level set, L_i, is constructed by finding all neighbors of vertices in the previous level set, L_{i-1}.
    b. Crucially, only neighbors that have not yet been visited (i.e., are not in any previous level set L_0, ..., L_{i-1}) are added to L_i.
    c. For each new vertex v added to L_i, set its distance δ(s, v) = i and its predecessor p(v) to be the vertex in L_{i-1} from which it was discovered.
  • The process stops when a level set is empty, meaning all reachable vertices have been found.
• Runtime Analysis:
  • Each vertex is visited (added to a level set) exactly once.
  • When processing a vertex u, the algorithm scans its entire adjacency list Adj(u).
  • The total work is the sum of the sizes of all adjacency lists, which is O(|E|).
  • There is also an initial cost of O(|V|) to initialize data structures (like the distance and predecessor arrays).
  • Therefore, the total runtime of BFS is O(|V| + |E|)

L14: Quiz 1

Instructor Jason Ku begins the session by framing it as a review for the upcoming quiz. He reiterates the core goals of the course:

1. Solve Computational Problems: Develop algorithms to address specific challenges.
2. Prove Correctness: Argue that the proposed solution is correct.
3. Analyze Efficiency: Demonstrate that the solution is efficient.
4. Communicate Ideas: Clearly explain the algorithm, its correctness, and its efficiency.

He categorizes the types of problems seen in the course into three levels:

• Mechanical/Internals: Problems that require understanding the internal workings of a data structure (e.g., how to perform a rotation in an AVL tree).
• Reduction: Problems that can be solved by using a known algorithm or data structure as a "black box," focusing on the API rather than the implementation. This is the most common type of problem.
• Modification: The most challenging problems, which require adapting or modifying a known data structure or algorithm (e.g., adding a new augmentation to a binary tree).

2. General Quiz-Taking Strategies
Ku offers several pieces of advice for tackling the quiz:

• Read the Entire Exam First: Identify the problems you are most confident about and solve those first to maximize points.
• Decouple Correctness and Efficiency: When solving a problem, first focus on finding any correct algorithm, even if it's inefficient. You can often get partial credit for a correct but slow solution. Once correctness is established, then work on optimizing it to meet the required time bounds.
• Avoid Common Pitfalls:
  • Don't compute with real numbers/rationals: All computations should be on integers. Use techniques like cross-multiplication for comparing fractions.
  • Don't overuse Radix Sort: Radix Sort is powerful but only applies to integers within a polynomially bounded range. Using it inappropriately is a common mistake.
  • Augmentations must be subtree properties: When augmenting a binary tree, the new property must be computable in O(1) time from the node's children. Global properties like "index in the full tree" are not valid augmentations.

3. Review of Core Material: The "Standard Library"
The session includes a comprehensive review of the "standard" algorithms and data structures that students are expected to know and be able to use as black boxes. These are summarized in tables.

• Sorting Algorithms: A review of Insertion Sort, Selection Sort, Merge Sort, Heap Sort, AVL Sort, and Radix Sort, highlighting their runtimes and special properties (e.g., in-place, stable, best for certain inputs).
• Sequence Data Structures: A comparison of Linked Lists, Dynamic Arrays, and Sequence AVL Trees, focusing on the trade-offs between them for operations like get_at, insert_at, and insert_first/last.
• Set Data Structures: A comparison of Sorted Arrays, Hash Tables, Direct Access Arrays, and Set AVL Trees. The discussion emphasizes choosing the right tool for the job: Hash Tables for fast expected-time dictionary operations, and AVL Trees for worst-case logarithmic performance and ordered operations like find_next.
• Priority Queues: A brief review of Binary Heaps and their O(n) build time and O(log n) delete_max time.

4. Problem 1: Restaurant Wait List
Goal: Design a data structure to manage a restaurant wait list with the following operations, all in O(1) time (worst-case, expected, or amortized).

• add(name): Adds a customer to the back of the list.
• remove(name): Removes a customer by name from anywhere in the list.
• seat(): Removes the customer at the front of the list.
• Analysis: The problem has a dual nature: it requires maintaining a strict order (a sequence) but also needs fast lookups by name (a set). The O(1) time constraint points away from AVL trees and toward linked lists and hash tables.
• Solution (Hybrid Data Structure):
  1. Sequence: Use a doubly-linked list to store the customers in the order they arrived. A doubly-linked list is crucial because it allows for O(1) removal from the middle, provided you have a direct pointer to the node.
  2. Set: Use a hash table to map each customer's name to a direct pointer to their node in the doubly-linked list.
  3. Operations:
     • add(name): Append a new node to the tail of the linked list. Insert the name and a pointer to this new node into the hash table. Both are O(1) operations.
     • remove(name): Use the hash table to find the pointer to the customer's node in O(1) expected time. Use this pointer to remove the node from the doubly-linked list in O(1) time.
     • seat(): Remove the head of the linked list (O(1)). Get the name of that customer and remove their entry from the hash table (O(1) expected).

5. Problem 2: Rainy Research
Goal: Design a data structure to record rainfall measurements (rainfall r, latitude l, time t) and support two operations:

• record_data(r, l, t): O(log n) worst-case time.
• peak_rainfall(l, t): Returns the maximum rainfall measured at latitude l at or after time t. O(log n) worst-case time.
• Analysis: The queries are organized first by latitude, then filtered by time. This suggests a nested data structure. The worst-case O(log n) time points to AVL trees. The peak_rainfall query is a one-sided range query: finding the maximum value within a range [t, infinity).
• Solution (Nested and Augmented AVL Trees):
  1. Outer Tree: A Set AVL tree that maps each latitude l to another data structure.
  2. Inner Tree: For each latitude, the associated data structure is another Set AVL tree. This inner tree stores the measurements for that latitude, keyed on time . Each node stores the rainfall r as its value.
  3. Augmentation: The key to solving the range query efficiently is to augment the inner (time-keyed) AVL trees. Each node v in an inner tree stores v.max_r, the maximum rainfall value in its entire subtree. This is a valid subtree property.
  4. Algorithm:
     a. Search the outer tree for latitude l to get the correct inner tree (O(log n)).
     b. Perform a modified search on the inner tree for time t. As you traverse the tree:
     i. If the current node's time is < t, the peak must be in the right subtree. Recurse right.
     ii. If the current node's time is ≥ t, the peak could be this node, or something in its left subtree, or something in its right subtree. The maximum of anything in the right subtree is already pre-computed as node.right.max_r. We can take the maximum of this value, the current node's rainfall, and the result of a recursive call on the left subtree.
     c. This modified search only ever makes one recursive call down the tree at each step, ensuring an O(log n) runtime for the query.

L15: Depth-First Search

The lecture begins with a recap of fundamental graph concepts and the BFS algorithm from the previous session.

• Graph Basics: A graph is a set of vertices V and edges E. Key concepts like directed vs. undirected graphs, simple graphs, neighbors, and degree are reviewed. The standard representation is an adjacency list.
• Linear Time: The phrase "linear time" for a graph algorithm is clarified to mean a runtime of O(|V| + |E|).
• BFS Review: Breadth-First Search explores a graph layer by layer, starting from a source node s. It computes level sets, where L_i contains all nodes at a shortest path distance of i from s. BFS is an algorithm for solving the Single-Source Shortest Path (SSSP) problem on unweighted graphs.

2. Depth-First Search (DFS) for Reachability
The lecture introduces a new graph traversal algorithm, Depth-First Search (DFS), and motivates it with the reachability problem: which vertices are reachable from a given source s?

• BFS vs. DFS:
  • BFS (Breadth): Explores all nodes at distance k before exploring any nodes at distance k+1. It expands outward in concentric circles.
  • DFS (Depth): Explores as far as possible along a single path before backtracking. It follows a path to its end, then backs up to the last choice point and explores another path.
• The DFS Algorithm (Recursive):
  • Define a recursive function visit(u).
  • Mark u as visited by setting its predecessor, p(u).
  • For each neighbor v of u:
    • If v has not been visited (p(v) is null), then set p(v) = u and recursively call visit(v).
  • The initial call is visit(s).
• Correctness and Runtime:
  • Correctness: An inductive proof shows that DFS correctly visits all vertices reachable from the source s and correctly sets their parent pointers, forming a valid path tree.
  • Runtime: The algorithm visits each reachable vertex and traverses each edge originating from a reachable vertex exactly once. Therefore, its runtime is O(|V_R| + |E_R|), where V_R and E_R are the vertices and edges in the reachable part of the graph.

3. Full DFS and Connected Components
The basic DFS algorithm only finds vertices reachable from a single source. To analyze an entire graph, especially a disconnected one, a "full" DFS is needed.

• Connected Components (Undirected Graphs): A connected component is a subgraph where every vertex is reachable from every other vertex.
• Full DFS Algorithm:
  1. Initialize all vertices as "unvisited."
  2. Iterate through every vertex v in the entire graph G.
  3. If v is unvisited, it means v belongs to a new, undiscovered connected component. Start a standard DFS from v to find all vertices in that component.
• Runtime: Although there is an outer loop over all vertices, each vertex and each edge is still only processed once across all the inner DFS calls. Therefore, the runtime of the full DFS is O(|V| + |E|).

4. Topological Sort for Directed Acyclic Graphs (DAGs)
The lecture shifts to a key application of DFS on a specific type of directed graph: the Directed Acyclic Graph (DAG). A DAG is a directed graph with no cycles.

• Topological Order: A linear ordering of the vertices of a DAG such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This is useful for scheduling tasks with dependencies.
• Finishing Order: The key insight is to use the order in which the recursive DFS calls finish. When a call to visit(u) returns (after all its descendants have been explored), u is considered "finished."
• The Algorithm:
  • Run a full DFS on the DAG.
  • As each visit(u) call finishes, add u to the front of a list.
  • The resulting list is a reverse finishing order, which is proven to be a valid topological sort.
• Proof Sketch: The proof considers any edge (u, v).
  • Case 1: If u is visited before v during DFS, then v will become a descendant of u in the DFS tree. The call to visit(v) must finish before the call to visit(u) can finish. Therefore, v will appear after u in the finishing order, and thus before u in the reverse finishing order, which is correct.
  • Case 2: v cannot be visited before u. If it were, since there is an edge (u, v), the DFS from v would eventually explore u unless u was already visited. But this would imply a path from v to u, and combined with the edge (u, v), this would form a cycle, contradicting the fact that the graph is a DAG.

5. Cycle Detection
The final application of DFS is cycle detection in a directed graph. The algorithm for topological sort provides a direct way to detect cycles.

• Key Theorem: A directed graph has a cycle if and only if its DFS forest has a back edge. A back edge is an edge (u, v) where v is an ancestor of u in the DFS tree.
• Algorithm:
  1. Modify the DFS algorithm to maintain the state of each vertex: unvisited, visiting (in the current recursion stack), or finished.
  2. When exploring from a vertex u, if a neighbor v is encountered that is in the "visiting" state, a back edge has been found, and thus a cycle exists.
  3. The cycle itself can be reconstructed by following the parent pointers from u back up to v.
• This modified DFS can detect and report a cycle, or (if no cycles are found) produce a topological sort, all in O(|V| + |E|) time.

L16: Weighted Shortest Paths

The lecture begins with a review of the graph algorithms covered so far, all of which operate on unweighted graphs where path length is simply the number of edges.

• Breadth-First Search (BFS): Solves the single-source shortest path (SSSP) problem in O(|V| + |E|) time.
• Depth-First Search (DFS): Can solve single-source reachability. A "full DFS" (looping over all vertices) can find connected components and perform a topological sort on a DAG, all in O(|V| + |E|) time.

2. Introduction to Weighted Shortest Paths
The core of the lecture is the generalization of the shortest path problem to weighted graphs.

• Weighted Graph: A graph where each edge e has an associated integer weight, w(e). These weights can be positive, negative, or zero.
• Path Weight: The weight of a path is the sum of the weights of its constituent edges.
• Shortest Path Distance The minimum weight among all possible paths from a source vertex s to a target vertex t.

3. The Problem of Negative Weight Cycles
A major complication arises with weighted graphs that is not present in unweighted graphs: negative weight cycles.

• Definition: A cycle whose edges sum to a negative value.
• The Problem: If a path from s to t can reach a negative weight cycle, it can traverse that cycle an infinite number of times, decreasing its total weight with each traversal. In this case, there is no finite minimum weight path.
• Convention: If a vertex v is reachable from s via a path that includes a negative weight cycle, its shortest path distance δ(s, v) is defined as -∞.
• For the current lecture, the focus will be on graphs or situations where this is not an issue.

4. A Roadmap for Weighted SSSP Algorithms
The lecture provides a roadmap for the next few sessions, outlining different algorithms for different types of weighted graphs.

1. Positive Integer Weights (BFS Reduction): If all edge weights are small, positive integers, we can transform the weighted graph into a larger unweighted graph (by replacing an edge of weight k with k-1 new vertices and k new edges of weight 1) and solve it with BFS in linear time.
2. Directed Acyclic Graphs (DAGs) (Today's Topic): For DAGs, SSSP can be solved in O(|V| + |E|) time, even with negative edge weights, because DAGs have no cycles by definition.
3. General Graphs with Negative Weights (Bellman-Ford Algorithm): For general graphs that may contain negative weight cycles, this algorithm can solve SSSP or detect the presence of such cycles. It runs in O(|V| * |E|).
4. General Graphs with Non-Negative Weights (Dijkstra's Algorithm): If all edge weights are guaranteed to be non-negative, this more efficient algorithm can solve SSSP in O(|E| log |V|) time.

5. The Concept of Relaxation
The core mechanic behind most weighted shortest path algorithms is relaxation.

• Distance Estimates: The algorithms maintain a distance estimate, d(s, v), for each vertex v, which is always an upper bound on the true shortest path distance δ(s, v). Initially, d(s, s) = 0 and d(s, v) = ∞ for all other vertices.
• Triangle Inequality: The shortest path distances must satisfy the triangle inequality: δ(s, v) ≤ δ(s, u) + w(u, v) for any edge (u, v).
• Relaxing an Edge: The algorithm repeatedly finds an edge (u, v) where the current estimates violate this property, i.e., d(s, v) > d(s, u) + w(u, v).
• The "relaxation" step is to improve the estimate for v by setting d(s, v) = d(s, u) + w(u, v). This is "safe" because it maintains the invariant that d(s, v) is the weight of some real path from s to v.

6. SSSP on a DAG in Linear Time
The main algorithm presented is for solving the SSSP problem on a Directed Acyclic Graph (DAG).

• Key Idea: A DAG has a topological sort, which is a linear ordering of its vertices such that for every edge (u, v), u comes before v in the ordering. This ordering provides a specific, structured way to process the vertices.
• The Algorithm (DAG Relaxation):
  • Initialize distance estimates: d(s, s) = 0 and all others to ∞.
  • Compute a topological sort of the DAG's vertices. This takes O(|V| + |E|) time using DFS.
  • Iterate through the vertices u in topological order.
  • For each vertex u, iterate through all of its outgoing neighbors v.
  • For each edge (u, v), perform the relaxation step: if d(s, v) > d(s, u) + w(u, v), then update d(s, v) = d(s, u) + w(u, v).
• Correctness and Runtime:
  • Correctness: The algorithm is correct because by processing vertices in topological order, whenever we consider an edge (u, v), the shortest path to u has already been finalized. Any shortest path to v must come from a predecessor u that appears earlier in the topological sort. By relaxing all incoming edges to v from these finalized predecessors, we are guaranteed to find the shortest path to v.
  • Runtime: The topological sort takes O(|V| + |E|). The main loop iterates through each vertex once and each edge once. Therefore, the total runtime is O(|V| + |E|).

The lecture concludes by noting that the parent pointers for the shortest path tree can be reconstructed from the final distance estimates in linear time, so future algorithms will focus only on computing the distances.

L17: PS 5

The session, led by instructor Justin Solomon, covers several graph theory problems related to Breadth-First Search (BFS) and Depth-First Search (DFS). The problems are presented as word problems, emphasizing the key skill of translating a narrative into a formal algorithmic task.
Problem 1: Radius of a Graph
Goal: This problem involves computing the "radius" of a connected, undirected graph G.

• Definitions:
  • Eccentricity For a vertex v, this is the shortest path distance to the vertex farthest away from it. ε(v) = max_{w ∈ V} δ(v, w).
  • Radius The minimum eccentricity over all vertices in the graph. R(G) = min_{v ∈ V} ε(v). This is analogous to finding the "center" of the graph.
• Part A: Compute the exact radius in
  • Algorithm: A straightforward "don't think, just do it" approach works here.
    • Initialize a variable min_eccentricity = ∞.
    • For each vertex v in V:
      a. Run a Breadth-First Search (BFS) starting from v to compute the shortest path distances δ(v, w) to all other vertices w. This takes O(|V| + |E|) time.
      b. Find the maximum of these distances to get ε(v).
      c. Update min_eccentricity = min(min_eccentricity, ε(v)).
  • Runtime Analysis: The outer loop runs |V| times, and the inner BFS takes O(|V| + |E|). The total time is O(|V| * (|V| + |E|)). Since the graph is connected, |E| ≥ |V|-1, which means |V| = O(|E|). Therefore, |V| + |E| = O(|E|). The total runtime simplifies to O(|V| * |E|).
• Part B: Compute an approximation
  • Algorithm:
    • Pick an arbitrary vertex u from the graph.
    • Compute the eccentricity of that vertex, ε(u), by running a single BFS from u. This takes O(|V| + |E|) = O(|E|) time.
    • Return R* = ε(u).
  • Proof of Approximation:
    • Lower Bound This is true by definition. The radius R(G) is the minimum eccentricity, so the eccentricity of any single vertex u must be greater than or equal to the minimum.
    • Upper Bound This is proven using the triangle inequality. Let u_0 be the true "center" vertex whose eccentricity is R(G). Let u be the arbitrary vertex we picked.
      • R* = ε(u) = max_w δ(u, w).
      • By the triangle inequality, δ(u, w) ≤ δ(u, u_0) + δ(u_0, w).
      • Since u_0 is the center, both δ(u, u_0) and δ(u_0, w) are at most R(G).
      • Therefore, δ(u, w) ≤ R(G) + R(G) = 2 * R(G). Taking the max over w gives R* ≤ 2 * R(G).

Problem 2: Internet Investigation
Goal: Given r routers, some of which are "entry points," and wires of varying lengths connecting them, find the sum of the latencies for all routers. The latency of a router is its shortest path distance to any entry point. The total length of all wires is at most 100r. The algorithm should run in O(r) time.

• Challenge: A naive approach would be to run BFS from every router to every entry point, which would be too slow. The varying wire lengths suggest a weighted graph, but BFS only works on unweighted graphs.
• Solution (Graph Transformation and Supernode):
  1. Transform to Unweighted Graph: The key is to convert the weighted graph into a larger unweighted graph. Replace each wire of length l with a chain of l-1 new "dummy" vertices and l new edges of weight 1.
     • Size Analysis: The total number of routers is r. The number of new dummy vertices is bounded by the total wire length, 100r. So, the total number of vertices in the new graph is |V'| = O(r). The number of new edges is also O(r).
  2. Introduce a Supernode: To avoid running BFS from every router, create a new "supernode" S. Add a directed edge of length 1 from S to every single "entry point" router.
  3. Run a Single BFS: Now, run a single-source shortest path (using BFS) from the supernode S to all other nodes in the transformed graph. This takes O(|V'| + |E'|) = O(r) time.
  4. Calculate Latencies: The shortest path distance from the supernode to any router i, δ(S, i), is equal to the router's true latency plus 1 (for the extra edge from S).
  5. The total latency is the sum of (δ(S, i) - 1) over all routers i.

Problem 3: Potry Harter's Labyrinth
Goal: Given a labyrinth of n rooms connected by doors (some "enchanted," some not), find the minimum number of enchanted doors that must be opened to visit every room. Every room has at most 4 doors.

• Challenge: This problem seems complex, potentially involving pathfinding, but the details suggest a simpler approach. The cost is associated only with opening an enchanted door for the first time; subsequent travel through it, and all travel through non-enchanted doors, is free.
• Solution (Connected Components):
  1. Model the "Free" Travel: The core insight is that all rooms connected by non-enchanted doors form a single "super-room" or region. Once one room in this region is entered, all others can be visited for free.
  2. Construct a Graph: Create a graph G where vertices are rooms and edges represent only the non-enchanted doors.
  3. Find Connected Components: Run a full BFS or DFS on G to find its connected components. Each component is a set of rooms that are mutually reachable without cost. The runtime is O(n) because the graph degree is bounded by a constant (4), so |E| = O(n).
  4. The Final Step: To connect k components into a single connected area (allowing all rooms to be visited), you need to open k-1 enchanted doors, forming a spanning tree on the components.
  5. The answer is simply the (number of components) - 1.

Problem 4: Purity Atlantic Itinerary
Goal: Given c cities and f flights, find the flight itinerary that visits a home city H and three other specific cities (A, B, C) with the minimum number of connections.

• Challenge: This seems like it could involve a factorial number of possibilities (permutations of A, B, C).
• Solution (Fixed Parameter and Pre-computation):
  1. Constant Number of Permutations: The key is that the number of cities to visit is a fixed constant (3). There are only 3! = 6 possible orderings in which to visit A, B, and C.
  2. Pre-compute Pairwise Distances: The problem requires finding the number of connections between the four key cities (H, A, B, C). There are a constant number of pairs (4 choose 2 * 2 directions = 12).
  3. Run BFS from each of the four cities to find the shortest path distances to all other cities. This takes 4 * O(c + f) = O(c + f) time.
  4. Check All Permutations: Iterate through the 6 possible permutations. For each permutation (e.g., H -> A -> B -> C -> H), sum the pre-computed shortest path distances for each leg of the journey.
  5. The minimum sum over all 6 permutations is the answer. The total runtime is dominated by the initial BFS runs, making it O(c + f).

Problem 5: Pocket Cube
Goal: Analyze the "state graph" of a 2x2x2 Rubik's cube (a pocket cube).

• State Graph: Vertices are the millions of possible configurations of the cube. Edges represent a single valid move (a 90-degree turn of one of the three available faces).
• Analysis:
  • Number of Configurations: Bounded by 7! * 3^7 (7 movable corner pieces, each with 3 possible orientations). This is less than 12 million.
  • Degree: Every state has a degree of 6 (3 faces can be turned in 2 directions).
  • BFS Exploration: A plot generated by running BFS from the solved state shows the number of configurations at each distance. The farthest reachable state is 14 moves away (the "diameter" of this component of the state graph).
  • Bidirectional Search: To find the shortest path from a start state S to a target state T more quickly, one can use bidirectional search. Run BFS simultaneously from S forward and from T backward. The search stops when the two "frontiers" meet. This significantly reduces the number of states explored, as the number of states at distance k grows exponentially. Instead of one search of depth d, you do two searches of depth d/2.

L18: Bellman-Ford

The lecture begins with a recap of weighted shortest paths and a roadmap for the upcoming algorithms.

• Last Lecture: Covered Single-Source Shortest Paths (SSSP) on Directed Acyclic Graphs (DAGs), which was solved in linear time (O(|V|+|E|)) using DAG Relaxation.
• Today's Topic: The Bellman-Ford Algorithm, which is a more general SSSP algorithm. It can handle graphs with cycles and negative edge weights.
• Goal of Bellman-Ford:
  1. Compute the correct finite shortest path weights for all reachable vertices.
  2. Identify vertices whose shortest path weight is -∞ (due to being reachable via a negative weight cycle).
  3. Optionally, return a negative weight cycle if one exists.
• Future Lectures: Will cover Dijkstra's Algorithm, which is more efficient than Bellman-Ford but requires all edge weights to be non-negative.

2. Simple Shortest Paths
A key preliminary concept is established: if a shortest path has a finite weight, there must exist a simple shortest path (one that does not repeat vertices).

• Proof Sketch: If every shortest path from s to v contained a cycle, consider one such path. Since the total path weight is finite, the cycle's weight cannot be negative (otherwise, traversing it repeatedly would lead to a -∞ path weight). If the cycle's weight is zero or positive, it can be removed from the path to create a new path that is either shorter or of equal length, but with fewer edges. This process can be repeated until a simple path is obtained.
• Implication: A simple path in a graph with |V| vertices can have at most |V|-1 edges. This is a crucial observation, as it bounds the "search space" for finite shortest paths.

3. k-Edge Distances and Witnesses
This observation motivates a new definition: the k-edge distance, denoted δ_k(s, v).

• Definition: δ_k(s, v) is the weight of the shortest path from s to v that uses at most .
• Connection to SSSP: For any vertex v with a finite shortest path, its true shortest path distance δ(s, v) is equal to δ_{|V|-1}(s, v). This is because we only need to consider simple paths.

This leads to the concept of a witness to a negative weight cycle.

• Definition: A vertex v is a witness if δ_{|V|}(s, v) < δ_{|V|-1}(s, v).
• Meaning: If the shortest path to v can be made shorter by allowing one more edge beyond the simple path limit of |V|-1, it implies that the shortest |V|-edge path must contain a cycle, and for the path to be shorter, that cycle must have a negative weight.
• Key Claim: It is proven that if δ(s, v) = -∞, then v must be reachable from a witness. This is a powerful result because it means we can find all -∞ vertices by first finding all witnesses and then finding all vertices reachable from them.

4. Bellman-Ford via Graph Duplication
The lecture presents a modified version of the Bellman-Ford algorithm that is easier to analyze. The core idea is to transform the original graph G into a new, larger graph G' that has a special structure.

• The Transformation (Graph Duplication):
  • Create |V| copies (or "levels") of the vertex set, indexed from 0 to |V|-1. A vertex v in level k is denoted v_k.
  • For every edge (u, v) with weight w in the original graph G, add a directed edge from u_k to v_{k+1} in G' for all levels k from 0 to |V|-2. This edge also has weight w. These are the "cross-level" edges.
  • For every vertex v, add a zero-weight edge from v_k to v_{k+1} for all levels k. These are the "stay-in-place" edges.
• Properties of
  • G' is a DAG. All edges go from a lower level k to a higher level k+1, so no cycles can exist.
  • The shortest path from the source s_0 to any vertex v_k in G' has a weight exactly equal to the k-edge shortest path distance δ_k(s, v) in the original graph G.

5. The Bellman-Ford Algorithm
With this transformation, the SSSP problem on a general graph is reduced to an SSSP problem on a DAG, which we already know how to solve.

• The Algorithm:
  • Construct Build the duplicated graph as described above. The size of G' is |V'| = O(|V|^2) and |E'| = O(|V|*|E|).
  • Run DAG Relaxation: Run the SSSP algorithm for DAGs (from the previous lecture) on G' with source s_0. This computes δ(s_0, v_k) for all v and k. This step takes time linear in the size of G', i.e., O(|V'| + |E'|) = O(|V|^2 + |V|*|E|).
  • Find Finite Distances: For each vertex v in the original graph, its final shortest path distance is δ_{|V|-1}(s, v), which is simply the value δ(s_0, v_{|V|-1}) computed in the previous step.
  • Identify Witnesses: For each vertex v, check if it's a witness by comparing δ(s_0, v_{|V|}) and δ(s_0, v_{|V|-1}).
  • Propagate -∞: For every identified witness u, perform a graph traversal (like BFS or DFS) from u in the original graph G to find all reachable vertices. Set the distance for all these reachable vertices to -∞.
• Runtime Analysis:
  • The dominant step is running DAG relaxation on the large graph G', which takes O(|V|^2 + |V|*|E|).
  • Since for any connected graph |V| = O(|E|). If we first find the connected component of the source and restrict the problem to that, |V|^2 is dominated by |V|*|E|.
  • Therefore, the final runtime is O(|V|*|E|).

This algorithm successfully solves the SSSP problem for any directed graph, correctly identifying finite path weights, detecting negative weight cycles, and handling -∞ distances.

L19: Dijkstra

The lecture begins with a review of the algorithms for Single-Source Shortest Paths (SSSP) on weighted graphs covered so far:

• BFS Reduction: For graphs with small, positive integer weights, the problem can be transformed into an unweighted one and solved with BFS in linear time (O(|V|+|E|)).
• DAG Relaxation: For Directed Acyclic Graphs (DAGs), SSSP can be solved in linear time, even with negative weights, by processing vertices in topological order.
• Bellman-Ford: The most general algorithm, capable of handling any graph, including those with negative weight cycles. It can compute finite shortest paths, identify vertices reachable via negative weight cycles (distance -∞), and detect such cycles. Its runtime is O(|V|*|E|).

2. Motivation for Dijkstra's Algorithm
The O(|V|*|E|) runtime of Bellman-Ford can be slow, especially for dense graphs (where |E| ≈ |V|^2, making the runtime O(|V|^3)). The lecture introduces a new, more efficient algorithm, Dijkstra's algorithm, for the common and important special case where all edge weights are non-negative.

• Goal: Achieve a near-linear runtime, specifically O(|E| + |V| log |V|).

3. Core Ideas and Observations
Dijkstra's algorithm is presented as a generalization of Breadth-First Search (BFS). BFS explores the graph in layers of increasing unweighted distance (number of edges). Dijkstra aims to do the same for weighted distance.

• Observation 1: Monotonicity with Non-Negative Weights: If all edge weights are non-negative, then distances along any shortest path are guaranteed to be non-decreasing. That is, if a shortest path from s to v goes through u, then δ(s, u) ≤ δ(s, v). This property is crucial because it means that once we have found the shortest path to a vertex, we never need to worry about a longer path leading to a shorter-weighted path later on. This is not true if negative edge weights are allowed.
• Observation 2: Connection to DAG Relaxation: If we were somehow given the vertices in increasing order of their true shortest path distance from s, we could process them in that order and run a DAG-like relaxation process to find all shortest paths in linear time. The challenge is that we don't know this ordering in advance.

Dijkstra's algorithm combines these ideas: it will discover the correct ordering of vertices "on the fly" by always processing the "closest" unexplored vertex next.
4. The Changeable Priority Queue
To efficiently find the "closest" unexplored vertex at each step, Dijkstra's algorithm uses a special data structure called a changeable priority queue.

• Interface: This is a priority queue that supports three main operations:
  1. build(X): Build the queue from a collection of items.
  2. delete_min(): Extract the item with the minimum key.
  3. decrease_key(id, new_key): Find an item by its unique id and decrease its priority (key) to a new, smaller value.
• Implementation: A changeable priority queue can be implemented by combining a standard priority queue (like a binary heap) with a dictionary (like a hash table or direct access array) that maps item IDs to their locations within the priority queue. This allows for efficient decrease_key operations.

5. Dijkstra's Algorithm
The algorithm proceeds as follows:

1. Initialization:
   • Initialize distance estimates d(s, v) = ∞ for all vertices v, and d(s, s) = 0.
   • Build a changeable priority queue containing all vertices. The priority (key) of each vertex v is its current distance estimate d(s, v). The ID is the vertex label itself.
2. Main Loop: While the priority queue is not empty:
   • Extract the vertex u with the minimum distance estimate from the queue by calling delete_min(). The algorithm has now "finalized" the shortest path to u.
   • For each outgoing neighbor v of u:
     • Perform a relaxation step: If a shorter path to v has been found by going through u (i.e., if d(s, v) > d(s, u) + w(u, v)), then:
       • Update the distance estimate: d(s, v) = d(s, u) + w(u, v).
       • Update the priority queue by calling decrease_key(v, d(s, v)).

6. Correctness of Dijkstra's Algorithm
The correctness of the algorithm hinges on proving that whenever a vertex v is extracted from the priority queue, its distance estimate d(s, v) is equal to its true shortest path distance δ(s, v).

• Proof by Induction: The proof is inductive on the number of vertices extracted from the queue.
  • Base Case: The first vertex extracted is s, and its distance d(s, s) = 0 is correct.
  • Inductive Step: Assume the claim holds for the first k-1 vertices. Let v be the k-th vertex extracted. Consider the true shortest path from s to v. Let (x, y) be the first edge on this path where x has already been extracted from the queue but y has not.
    • By the inductive hypothesis, d(s, x) = δ(s, x).
    • After x was processed, the edge (x, y) was relaxed, so d(s, y) ≤ d(s, x) + w(x, y) = δ(s, y).
    • Because relaxation is "safe," we also know d(s, y) ≥ δ(s, y). Therefore, d(s, y) = δ(s, y).
    • Since v was chosen as the minimum from the queue, and y is still in the queue, d(s, v) ≤ d(s, y).
    • Due to non-negative weights, δ(s, y) ≤ δ(s, v).
    • Combining these inequalities (δ(s, v) ≤ d(s, v) ≤ d(s, y) = δ(s, y) ≤ δ(s, v)) forces all terms to be equal, proving that d(s, v) = δ(s, v).

7. Runtime Analysis
The total runtime of Dijkstra's algorithm depends on the performance of the changeable priority queue used. The algorithm performs |V| delete_min operations and at most |E| decrease_key operations.

In practice and for the purposes of the course, the binary heap implementation is standard, giving a runtime of O(|E| log |V|). For dense graphs, the simple unsorted array implementation can actually be faster.

L20: PS 7

The session, led by instructor Justin Solomon, covers a series of graph theory problems. The problems focus on applying and modifying shortest path algorithms like Breadth-First Search (BFS) and Dijkstra's algorithm to solve non-standard problems.
Problem 1: Dijkstra's Algorithm Walkthrough
Goal: This is a mechanical problem designed to ensure a solid understanding of the step-by-step execution of Dijkstra's algorithm.

• Part A: Run Dijkstra's from a source
  • Setup: A directed, weighted graph is provided. Dijkstra's algorithm finds the single-source shortest paths from s.
  • Process: The algorithm is executed step-by-step.
    1. Initialize all distances to ∞, except dist(s) = 0. All vertices are in a priority queue.
    2. Iteration 1: Extract s (distance 0). Relax its outgoing edges, updating distances to neighbors a (dist 8) and c (dist 7).
    3. Iteration 2: Extract c (min distance 7). Relax its edge to d, updating dist(d) to 11.
    4. Iteration 3: Extract a (min distance 8). Relax its edge to d, updating dist(d) from 11 down to 8.
    5. This process continues, always extracting the unvisited vertex with the minimum current distance estimate and relaxing its outgoing edges, until all reachable vertices are visited.
• Part B: What happens if an edge weight becomes negative?
  • Scenario: The weight of edge (g, c) is changed from 0 to -6.
  • Analysis: Dijkstra's algorithm proceeds as before until it extracts vertex g (with distance 12). When it relaxes the edge (g, c), it computes a new path to c with weight 12 + (-6) = 6. This is shorter than the "finalized" distance of 7 that was found for c much earlier in the algorithm.
  • Conclusion: This demonstrates why Dijkstra's algorithm fails with negative edge weights. Its core assumption is that once a vertex is extracted from the priority queue, its shortest path is found and will never need to be updated. A negative edge can violate this assumption by providing a "shortcut" back to an already-finalized vertex.

Problem 2: Weighted Radius
Goal: Compute the weighted radius of a directed graph with no negative weight cycles.

• Definitions: This problem is a weighted version of a problem from a previous session.
  1. Weighted Eccentricity The maximum shortest path distance from u to any other vertex v.
  2. Weighted Radius The minimum weighted eccentricity over all vertices u.
• Algorithm (Direct Approach):
  1. All-Pairs Shortest Paths: The problem requires distances between all pairs of vertices. Since there are no negative weight cycles, Johnson's algorithm is a suitable choice. For a graph of size |V|, this takes O(|V|*|E| + |V|^2 log |V|). Given that |E| = O(|V|^2), this simplifies to O(|V|^3). The problem provides a generous O(|V|^3) time budget, making this step feasible.
  2. Compute Eccentricities: With all pairwise distances pre-computed, iterate through each vertex u. For each u, find the maximum distance δ(u, v) over all v. This takes O(|V|^2) time.
  3. Find the Radius: Find the minimum of all the computed eccentricities. This takes O(|V|) time.
• Conclusion: The total runtime is dominated by Johnson's algorithm, resulting in an O(|V|^3) solution. This problem highlights that sometimes the most direct translation of the definition into an algorithm is sufficient if the time constraints allow.

Problem 3: Atniss Keverdeen's Escape
Goal: In a labyrinth (a graph), find the shortest path from a source s to a target t that maximizes the minimum distance to any "sensor" vertex. The graph has a degree bound of 4.

• Challenge: This is not a standard shortest path problem. The "cost" of a path is not its length, but how close it gets to a sensor.
• Solution (Binary Search on the Answer):
  1. Solve a Simpler "Decision" Problem: First, consider how to answer the question: "Does there exist a path from s to t that stays at least a distance k away from all sensors?"
     • To solve this, first compute the shortest distance from every junction to its nearest sensor. This can be done efficiently by adding a "super-source" node with zero-weight edges to all sensor nodes and running a single Dijkstra from the super-source. This takes O(n log n).
     • Create a subgraph G_k containing only the vertices whose distance to the nearest sensor is greater than k.
     • Run BFS/DFS on G_k to check for reachability from s to t. This takes O(n).
  2. Binary Search for the Optimal The decision problem has a monotonic property: if a path exists for distance k, a path also exists for any distance smaller than k. This allows for binary search.
     • We want to find the largest k for which the answer to the decision problem is "yes."
     • The possible values for k are the distances themselves. Sort all the n vertex-to-sensor distances in O(n log n) time.
     • Perform a binary search on the indices of this sorted array. This will take log n iterations.
     • Each iteration runs the O(n) decision problem.
  3. Final Runtime: The total runtime is O(n log n) for the initial Dijkstra and sort, plus O(n log n) for the binary search (log n calls to an O(n) subroutine), resulting in an O(n log n) solution.

Problem 4: Okepon Shipping
Goal: Design a data structure to handle shipping routes. Each route connects two cities, has a maximum weight capacity, and a cost. The final problem is to find the minimum cost to ship the heaviest possible server from a source s to a target t.

• Part A (Digression): The Bottleneck Path Property:
  1. Bottleneck: The bottleneck of a path is the minimum weight capacity of any edge along that path.
  2. b(s, t): The maximum possible bottleneck over all paths from s to t.
  3. Property to Prove: b(s, t) is related to the bottlenecks of paths to t's immediate predecessors. This property is analogous to the relaxation property in Dijkstra's algorithm, but with max and min operations instead of + and min.
     • b(s, t) = max_{v → t} min(b(s, v), w(v, t))
• Part B (The Algorithm):
  1. Find the Maximum Shippable Weight (w* The first step is to find the heaviest server that can be shipped. This is exactly the maximum bottleneck path problem b(s, t). The property from Part A suggests that this can be solved using a Dijkstra-like algorithm.
     • Run Dijkstra, but replace the relaxation step dist(v) = min(dist(v), dist(u) + w(u, v)) with the bottleneck update b(v) = max(b(v), min(b(u), w(u, v))). This finds the maximum bottleneck path in the same runtime as Dijkstra.
  2. Find the Minimum Cost for that Weight: Once the maximum weight w* is known:
     • Create a new graph containing only the routes (edges) with a weight capacity of at least w*.
     • In this new graph, the edge weights are now the costs of the routes.
     • Run a standard Dijkstra's algorithm on this graph to find the minimum cost path from s to t.

This two-phase approach first identifies the maximum possible flow (bottleneck) and then finds the cheapest way to achieve that flow.

L21: APSP and Johnson

The lecture begins with a review of the SSSP algorithms covered so far, emphasizing their runtimes and the types of graphs they apply to.

The key takeaway is the performance gap between algorithms for graphs with non-negative weights (Dijkstra, near-linear) and general graphs that might have negative weights (Bellman-Ford, O(|V|*|E|), which is slow).
2. The All-Pairs Shortest Paths (APSP) Problem
The lecture introduces a new, more comprehensive problem.

• Goal: Given a weighted, directed graph G, compute the shortest path distance δ(u, v) for every pair of vertices (u, v).
• Constraint: The algorithm should abort if the graph contains a negative weight cycle, as this would make some distances -∞.
• Output Size: The output is a |V| x |V| matrix of distances, so any algorithm must take at least Ω(|V|^2) time.

3. A Naive Solution: Repeated SSSP
A simple, brute-force approach to solving APSP is to run an SSSP algorithm from every vertex.

• Using Bellman-Ford: Running Bellman-Ford |V| times gives a total runtime of O(|V|^2 * |E|). For dense graphs (|E| ≈ |V|^2), this is O(|V|^4).
• Using Dijkstra: If all weights are non-negative, running Dijkstra |V| times gives a total runtime of O(|V|*|E| + |V|^2 log |V|). This is significantly better than repeated Bellman-Ford.

The central question of the lecture is: Can we solve APSP on graphs with negative weights as efficiently as we can on graphs with only non-negative weights? The goal is to avoid the slow O(|V|^2 * |E|) runtime and get closer to the O(|V|*|E| + |V|^2 log |V|) runtime of repeated Dijkstra.
4. The Core Idea: Reweighting
The key idea behind Johnson's Algorithm is to transform the original graph G (which may have negative edge weights) into a new graph G' with the same vertices and edges, but with new, non-negative edge weights w', such that the shortest paths are preserved.

• If this reweighting is possible, we can then run Dijkstra from every vertex on the new graph G' to solve the APSP problem efficiently.

5. A Powerful Reweighting Technique
A specific reweighting technique is introduced that preserves shortest paths.

• Vertex Potentials: Assign an integer "potential" h(v) to every vertex v.
• Reweighting Formula: The new weight w'(u, v) for an edge (u, v) is defined as: w'(u, v) = w(u, v) + h(u) - h(v).
• Proof of Preservation: It is proven that this transformation preserves shortest paths. The weight of any path from s to t in the new graph is equal to the original path weight plus a constant term h(s) - h(t). Since this constant is the same for all paths between s and t, a path that was shortest in the original graph will remain shortest in the reweighted graph.

6. Finding the Right Potentials
The challenge is to find a set of potentials h(v) such that all the new edge weights w'(u, v) are non-negative.

• The Condition: We need w'(u, v) = w(u, v) + h(u) - h(v) ≥ 0.
• Rearranging: This is equivalent to h(v) ≤ h(u) + w(u, v).
• Connection to Triangle Inequality: This inequality looks exactly like the triangle inequality for shortest paths. If we could set the potentials h(v) to be the shortest path distances from some source, δ(s, v), then this condition would be satisfied for all edges.

7. Johnson's Algorithm
This insight leads to the full algorithm.

1. Create a Super-Source: Since we don't have a single source that can necessarily reach all vertices, create a new "super-source" vertex s. Add a zero-weight directed edge from s to every other vertex in the graph. Let this new graph be G_s.
2. Run Bellman-Ford Once: Run the Bellman-Ford SSSP algorithm from the super-source s on the graph G_s.
   • This takes O(|V|*|E|) time.
   • Cycle Detection: If Bellman-Ford detects a negative weight cycle (by finding a vertex v where δ(s, v) = -∞), then the original graph G must also have had a negative weight cycle (since s has no incoming edges). In this case, the algorithm aborts as required.
   • Compute Potentials: If there are no negative weight cycles, the shortest path distances δ(s, v) are now known for all v. These will be our potentials: set h(v) = δ(s, v).
3. Reweight the Graph: Create the new graph G' by applying the reweighting formula to every edge in the original graph G using the potentials h(v) computed in the previous step. All edge weights in G' are now guaranteed to be non-negative.
4. Run Dijkstra Now that G' has non-negative weights, run Dijkstra's algorithm from every vertex u on G' to compute all-pairs shortest path distances δ'(u, v). This takes O(|V| * (|E| + |V| log |V|)) time.
5. Convert Distances Back: The distances δ'(u, v) computed in G' are not the same as the original distances. Use the path weight transformation formula to convert them back: δ(u, v) = δ'(u, v) - h(u) + h(v). This takes O(|V|^2) time.

Conclusion: Johnson's algorithm successfully solves the all-pairs shortest paths problem for graphs with negative weights (but no negative weight cycles) with a total runtime of O(|V|*|E| + |V|^2 log |V|). This is a significant improvement over running Bellman-Ford |V| times, effectively matching the efficiency of running Dijkstra on a graph that had non-negative weights to begin with.

L22: Quiz 2

Instructor Jason Ku begins by outlining the scope of the upcoming quiz.

• Main Focus: The six lectures on graph theory, covering both unweighted and weighted graph algorithms.
• Quiz 1 Material: Concepts from Quiz 1 (data structures, asymptotics) are still fair game as they are foundational, but they will not be the primary focus.
• Key Graph Problems Covered:
  • Unweighted: Graph Reachability (BFS/DFS), Connected Components (Full BFS/DFS), Topological Sort (DFS), Cycle Detection.
  • Weighted: Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP) using algorithms like DAG Relaxation, BFS (for special cases), Dijkstra, and Bellman-Ford.

2. General Problem-Solving Strategies for Graph Problems
Ku emphasizes a structured approach to solving graph problems, especially word problems.

1. Modeling: The first and most critical step is to translate the word problem into a formal, abstract graph problem.
   • Explicitly define the graph: What are the vertices? What are the edges? Are they weighted? Directed?
   • State the problem to be solved on that graph (e.g., "This corresponds to finding the SSSP from vertex p in the constructed graph G.").
2. Graph Transformation: Often, the initial graph model needs to be modified to fit a known algorithm. Common "tricks" include:
   • Graph Duplication / State Expansion: Create multiple copies of vertices to store state information (e.g., (vertex, state) becomes a new vertex).
   • Adding an Auxiliary Vertex (Supernode): Add a new source or sink node with edges to multiple other nodes to solve multi-source or multi-sink problems with a single SSSP run.
   • Preprocessing/Filtering: Remove or modify vertices/edges that don't satisfy certain conditions to simplify the problem (e.g., removing edges to create a DAG).
3. Correctness and Runtime Analysis:
   • Correctness: The main argument is linking the solution on the transformed graph back to the original word problem. The correctness of the underlying algorithms (like BFS, Dijkstra) can usually be assumed.
   • Runtime: Analyze the size (|V'| and |E'|) of the transformed graph and apply the known runtime of the chosen algorithm to that new size. Forgetting to account for the increased size of the graph is a common mistake.

Problem 1: Counting Blobs
Goal: Given an N x M grid of black and white pixels, count the number of "blobs" (connected components of white pixels) in linear time (O(N*M)).

• Modeling:
  1. Vertices: Each white pixel in the grid.
  2. Edges: An undirected edge exists between two vertices if their corresponding pixels share a side in the grid.
• Abstract Problem: The number of blobs is equivalent to the number of connected components in this constructed graph.
• Algorithm:
  1. Construct the graph by iterating through the N x M grid. This takes O(N*M) time. The resulting graph has |V| ≤ N*M and |E| ≤ 4*N*M, so its size is linear.
  2. Run a Full BFS or Full DFS to count the connected components.
• Runtime: The algorithm runs in time linear in the size of the constructed graph, which is O(|V| + |E|) = O(N*M).

Problem 2: Tree Plus One Edge
Goal: Given a connected, undirected graph with positive edge weights and the special property that |E| = |V|, find the shortest path from s to t in O(|V|) time.

• Analysis: A connected graph with |V|-1 edges is a tree. Therefore, a connected graph with |V| edges is a tree plus one extra edge, which means it contains exactly one cycle.
• Challenge: Standard Dijkstra's algorithm would be too slow (O(|V| log |V|)). We must exploit the unique structure of the graph.
• Algorithm:
  1. Find the Cycle: Run an unweighted BFS/DFS from any vertex to build a spanning tree. The single edge from the original graph that is not in this spanning tree is the "extra" edge that closes the cycle.
  2. Identify the Two Paths: A shortest path from s to t can either avoid the cycle or traverse it one of two ways. The algorithm identifies the "split point" on the cycle closest to s and the two edges leading away from it onto the cycle.
  3. Compare Paths: The shortest path from s to t must be one of two possibilities: the path that goes one way around the cycle, or the path that goes the other way.
  4. Run two separate unweighted BFS/DFS traversals (which is sufficient for finding paths in a tree) on the two trees formed by removing each of the two cycle edges in turn. Calculate the weighted path length for each and return the minimum.
• Runtime: Each step (finding the cycle, finding paths in the resulting trees) takes time linear in the size of the graph, O(|V| + |E|) = O(|V|).

Problem 3: Donut Danger
Goal: Find the shortest path from a power plant P to home H in a city, with the constraint that the path must never come within a driving distance k of any donut shop.

• Challenge: This is a shortest path problem with "forbidden" regions. A naive approach of running Dijkstra from every donut shop to find all forbidden vertices would be too slow (O(d * n log n), where d is the number of donut shops).
• Solution (Supernode and Filtering):
  1. Find All Forbidden Vertices Efficiently: To find all vertices within distance k of any donut shop in a single run, create a super-source node . Add a zero-weight directed edge from S to every donut shop location.
  2. Run a single Dijkstra's algorithm from S. The shortest path distance δ(S, v) for any location v will now be the distance to its nearest donut shop. This takes O(n log n).
  3. Filter the Graph: Create a new subgraph G' that contains only the "safe" vertices—those whose distance from the super-source S is greater than k.
  4. Find the Final Path: Run a standard Dijkstra's algorithm on the filtered subgraph G' from P to H to find the shortest safe path.
• Runtime: The algorithm is dominated by the two Dijkstra runs, giving a total runtime of O(n log n).

Problem 4: Long Shortest Paths
Goal: In a directed graph with arbitrary edge weights, find the minimum weight of any path from s to t that contains at least .

• Analysis: A path with ≥ |V| edges must contain a cycle. If the graph contains a reachable negative weight cycle, the answer is -∞. Otherwise, any cycles on a shortest path must be zero-weight cycles. This structure suggests the "layered graph" approach used in Bellman-Ford.
• Solution (Graph Duplication / State Expansion):
  1. Construct a Layered Graph: Create a new graph G' with |V|+1 layers, indexed 0 to |V|. Each layer contains a copy of all the vertices from the original graph. A vertex u in layer i is denoted u_i.
  2. For every edge (u, v) with weight w in the original graph, add a directed edge from u_i to v_{i+1} in G' for all layers i from 0 to |V|-1. This edge also has weight w.
  3. No "Stay-in-Place" Edges: Unlike the Bellman-Ford construction, do not add the zero-weight u_i -> u_{i+1} edges. This ensures that any path of length k in G' corresponds to a path using exactly k edges in the original graph.
  4. Solving the Problem: The shortest path from s_0 to any t_i in this new DAG G' gives the shortest path from s to t using exactly i edges.
  5. The problem asks for a path of at least |V| edges. This can be solved by modifying the final layer (|V|) of the duplicated graph. On this final layer, add copies of all the original graph edges (e.g., (u_{|V|}, v_{|V|})). Now, a path can "enter" this final layer after |V| steps and continue traveling.
  6. The shortest path from s_0 to t_{|V|} in this final modified graph will be the answer. Since the graph up to layer |V|-1 is a DAG, we can compute distances efficiently up to that point and then use those as a starting point for a final SSSP run (like Bellman-Ford) on the last layer.
• Runtime: The construction and subsequent shortest path calculations on the duplicated graph lead to a final runtime of O(|V|^3).

L23: Dynamic Programming 1

The lecture introduces a new unit focused on algorithmic design, shifting from using and analyzing existing algorithms to creating new ones from scratch. The central paradigm for this unit is dynamic programming (DP).

• What is Dynamic Programming? DP is a powerful and general technique for designing polynomial-time algorithms. It is a specific type of recursive algorithm design that is particularly effective for optimization problems.
• The Power of Recursion: All algorithms that solve problems of arbitrary size (n) with a constant amount of code must be recursive in some sense (either through explicit recursion or loops). Recursion is a natural fit for proving correctness via induction and for structuring the relationships between subproblems.

2. SRTBOT: A Framework for Recursive Algorithms
A six-step framework called SRTBOT is introduced as a systematic way to design and describe recursive algorithms.

1. S - Subproblems: Define the set of subproblems that need to be solved. The goal is to have a polynomial number of them.
2. R - Relate: Establish a recursive relationship (a recurrence) that shows how to solve a larger subproblem using the solutions to one or more smaller subproblems.
3. T - Topological Order: Define a valid ordering in which to solve the subproblems to ensure that when solving a problem, the solutions to its required subproblems have already been computed. This guarantees the recursion is acyclic and terminates.
4. B - Base Cases: Specify the smallest subproblems that can be solved directly, without recursion.
5. O - Original Problem: Show how to solve the original problem using the defined subproblems (often, the original problem is just one of the subproblems).
6. T - Time: Analyze the overall running time of the algorithm.

Merge sort is presented as a familiar example fitting the SRTBOT framework.
3. The Problem with Naive Recursion: Fibonacci Numbers
The Fibonacci sequence is used as a toy problem to illustrate a critical flaw in naive recursive algorithms.

• Naive Recursive Algorithm: A function fib(n) is defined that simply calls fib(n-1) + fib(n-2).
• Analysis: This approach is extremely inefficient. The recursion tree shows that the same subproblems (e.g., fib(n-2)) are computed over and over again. The runtime T(n) = T(n-1) + T(n-2) + O(1) grows exponentially, just like the Fibonacci numbers themselves.

4. Memoization: The Core Idea of Dynamic Programming
The solution to the inefficiency of naive recursion is memoization. This is the key idea that elevates a simple recursive algorithm into a dynamic programming solution.

• Concept: Remember and reuse solutions to subproblems.
• Implementation: Use a dictionary or array (the "memo") to store the solution to each subproblem as it is computed.
• Modified Algorithm: Before computing a subproblem, check if its solution is already in the memo.
  • If it is, return the stored value immediately.
  • If not, compute the solution recursively, and before returning, store it in the memo.
• Runtime Analysis with Memoization: With memoization, each unique subproblem is solved at most once. The total running time is therefore:
  Total Time ≈ (Number of Subproblems) * (Non-recursive work per subproblem)
• Fibonacci with Memoization:
  • Number of subproblems: O(n) (from fib(1) to fib(n)).
  • Non-recursive work: O(1) (a single addition).
  • Total time: O(n). This is a dramatic improvement from exponential to linear time. (A small note is made that for very large n, the time for n-bit addition must be considered, making the runtime closer to O(n^2 / w)).

5. Bottom-Up DP vs. Top-Down (Memoized) DP
Two equivalent ways of implementing a DP solution are presented:

1. Top-Down with Memoization (as described above): A recursive function that checks a memo table. It starts with the original problem and recursively breaks it down.
2. Bottom-Up DP: An iterative approach that uses the topological order.
   • Algorithm:
     1. Create a table to store the solutions.
     2. Initialize the base cases in the table.
     3. Use a for loop that iterates through the subproblems in their topological order.
     4. Inside the loop, use the recurrence relation to fill in the table entry for the current subproblem, using values that have already been computed.
   • This approach avoids recursion overhead and is often more efficient in practice.

6. Revisiting DAG Shortest Paths as a DP
The SSSP on a DAG problem is reframed as a dynamic program, demonstrating its connection to the DP paradigm.

• S - Subproblems: The shortest path distance δ(s, v) for each vertex v.
• R - Relate: The shortest path to v is the minimum of (δ(s, u) + w(u, v)) over all incoming neighbors u.
• T - Topological Order: The topological sort of the DAG itself.
• B - Base Case: δ(s, s) = 0.
• T - Time: O(|V| + |E|).

It's noted that a memoized recursive implementation of this DP is essentially a Depth-First Search on the (reversed) subproblem graph.
7. New Problem: The Bowling Game
A new problem is introduced to demonstrate how to design a DP from scratch.

• Problem: Given n bowling pins in a line, each with a value v_i. You can knock over a single pin i for v_i points, or an adjacent pair (i, i+1) for v_i * v_{i+1} points. Knocked-over pins are removed. Find the maximum possible score.
• Subproblem Design Strategy: A general heuristic for problems on sequences is to define subproblems based on prefixes, suffixes, or substrings. Prefixes and suffixes lead to a linear number of subproblems (O(n)), while substrings lead to a quadratic number (O(n^2)).
• DP Solution for Bowling:
  1. S - Subproblems: B(i) = the maximum score obtainable from the suffix of pins starting at index i.
  2. O - Original Problem: The goal is to find B(0).
  3. R - Relate: To find the max score for the suffix starting at i, B(i), consider the first pin in that suffix (pin i). There are three choices for what to do with it:
     • Skip pin The score is then the max score for the rest of the pins, which is B(i+1).
     • Hit only pin The score is v_i + B(i+1).
     • Hit pins The score is v_i * v_{i+1} + B(i+2).
       The recurrence is the maximum of these three options: B(i) = max( B(i+1), v_i + B(i+1), v_i*v_{i+1} + B(i+2) ).
  4. T - Topological Order: Solve for i in decreasing order, from n down to 0.
  5. B - Base Case: B(n) = 0 (no pins left, no score).
  6. T - Time: There are O(n) subproblems. The non-recursive work for each is O(1) (a few additions, a multiplication, and a max of three numbers). The total time is O(n).

L24: Dynamic Programming 2

The lecture begins with a review of the dynamic programming (DP) paradigm, presented as a general framework for designing polynomial-time algorithms from scratch.

• SRTBOT Framework: The six-step framework for designing recursive algorithms is reiterated:
  • S - Subproblems: Define a set of smaller, related problems.
  • R - Relate: Formulate a recurrence relation to solve a subproblem using solutions to smaller subproblems.
  • T - Topological Order: Determine an acyclic order to solve the subproblems.
  • B - Base Cases: Define the smallest, non-recursive subproblems.
  • O - Original Problem: Show how the original problem is solved by the subproblems.
  • T - Time: Analyze the overall runtime.
• Key DP Heuristics:
  • Subproblem Design: For problems on sequences, a good starting point is to define subproblems based on prefixes, suffixes, or substrings.
  • Recurrence Relation: To formulate the recurrence, identify a "question" about the solution. The recurrence then becomes a max or min over all possible answers to that question (a "local brute force").

2. Problem 1: Longest Common Subsequence (LCS)
Goal: Given two sequences, A and B, find the longest sequence L that is a subsequence of both.

• Subproblem Design for Multiple Inputs: When a problem has multiple input sequences, a common strategy is to take the product of the subproblem spaces for each input.
• DP Solution:
  1. S - Subproblems: L(i, j) = the length of the LCS of the suffix of A starting at i (A[i:]) and the suffix of B starting at j (B[j:]). This creates O(|A| * |B|) subproblems.
  2. R - Relate: Consider the first characters of the suffixes, A[i] and B[j].
     • If The characters match. We can greedily include this character in our LCS. The length is 1 + L(i+1, j+1).
     • If The characters don't match. The LCS cannot start with both. We must discard at least one of them. We don't know which choice leads to a better solution, so we try both and take the maximum: max( L(i+1, j), L(i, j+1) ).
  3. T - Topological Order: Solve for i and j in decreasing order (from the end of the strings to the beginning).
  4. B - Base Cases: If either i or j is past the end of its string, the LCS is of length 0.
  5. O - Original Problem: The answer is L(0, 0).
  6. T - Time: O(|A| * |B|) subproblems, each taking O(1) non-recursive work. Total time is O(|A| * |B|).
• Recovering the Solution: The lecture demonstrates how to use parent pointers in the DP table to reconstruct the actual LCS string, not just its length. By tracing back the decisions made at each step (e.g., did we take the diagonal, right, or down path?), we can identify the characters that form the LCS.

3. Problem 2: Longest Increasing Subsequence (LIS)
Goal: Given a single sequence A of numbers, find the longest subsequence that is strictly increasing.

• First Attempt (Fails): A natural first attempt is to define the subproblem L(i) as the LIS of the suffix A[i:]. However, this fails. When formulating the recurrence, we need to decide whether to include A[i]. If we do, we need to find the LIS of the remaining suffix A[i+1:] where all elements are greater than . The subproblem L(i+1) doesn't have this constraint, so the simple definition is not powerful enough.
• The Fix: Subproblem Constraint/Expansion: The solution is to strengthen the subproblem definition by adding a constraint.
• DP Solution:
  1. S - Subproblems: L(i) = the length of the LIS of the suffix A[i:] that starts with .
  2. O - Original Problem: This new subproblem L(0) doesn't solve the original problem, because the true LIS might not start with A[0]. The solution is to find max(L(i)) over all possible starting positions i.
  3. R - Relate: To find L(i), we know A[i] is the first element. What is the second? We don't know, so we "guess" (brute-force) all possibilities. The recurrence is L(i) = 1 + max(L(j)) over all j > i such that A[j] > A[i]. (If no such j exists, the max is 0).
  4. T - Topological Order: Solve for i in decreasing order (from n-1 down to 0).
  5. B - Base Case: The LIS of an empty suffix is of length 0.
  6. T - Time: There are O(n) subproblems. The non-recursive work for each subproblem L(i) involves a loop over O(n) other indices j. The total time is O(n^2).
• Connection to Shortest Paths: It's shown that both LCS and LIS can be viewed as finding the longest path in a specially constructed Directed Acyclic Graph (DAG) where vertices are subproblems and edges represent dependencies.

4. Problem 3: Alternating Coin Game
Goal: Two players take turns picking a coin from either the left or right end of a line of coins. Find the maximum total value the first player can guarantee for themselves, assuming the second player also plays optimally.

• Challenge: The optimal strategy depends on whose turn it is. A simple subproblem definition max_value(i, j) is insufficient because it doesn't encode this crucial piece of state.
• The Fix: Subproblem Expansion: Expand the state space to include the current player.
• DP Solution:
  1. S - Subproblems: X(i, j, p) = max value player 1 can get from the substring of coins [i, j], given that it is player p's turn (p can be "me" or "you"). This gives O(n^2) subproblems.
  2. R - Relate:
     • If it's my turn I want to maximize my outcome. I have two choices: take coin i or take coin j.
       • Take i: My score is v[i] + X(i+1, j, "you").
       • Take j: My score is v[j] + X(i, j-1, "you").
       • My recurrence is the max of these two options.
     • If it's your turn You will play optimally to maximize your score, which is equivalent to minimizing my score (it's a zero-sum game). You have two choices:
       • Take i: My future score will be X(i+1, j, "me").
       • Take j: My future score will be X(i, j-1, "me").
       • Your recurrence (from my perspective) is the min of these two outcomes.
  3. T - Topological Order: Solve for substrings in increasing order of length (j-i).
  4. T - Time: O(n^2) subproblems, O(1) work per subproblem. Total time is O(n^2).

L25: PS 8

Instructor Justin Solomon begins by reviewing the core concepts of dynamic programming (DP), framing it as a problem-solving approach rather than a single specific algorithm.

• The Core Idea: DP is based on solving problems recursively. Its key advantage comes from memoization: remembering and reusing the solutions to subproblems that are encountered multiple times.
• SRTBOT Framework: The six-step SRTBOT framework for designing DP solutions is revisited as a structured way to approach problems:
  • S - Subproblems: Define the smaller pieces of the problem.
  • R - Relate: Formulate a recurrence relation.
  • T - Topological Order: Determine an acyclic order to solve subproblems.
  • B - Base Cases: Define the smallest, non-recursive problems.
  • O - Original Problem: State how the final answer is derived from the subproblems.
  • T - Time: Analyze the runtime.
• Top-Down vs. Bottom-Up: Two equivalent implementation strategies are mentioned:
  • Top-Down (Memoization): A recursive function with a cache (the "memo").
  • Bottom-Up: An iterative approach using loops to fill a DP table in topological order.

2. Problem 1: Tim the Beaver's Happiness
Goal: Tim the Beaver has n days until an exam. On day i, the temperature is t_i. Tim can either go outside (happiness increases by t_i) or stay inside (happiness is unchanged). The constraint is that Tim can never go outside for more than two consecutive days. The task is to find a plan that maximizes Tim's total happiness.

• Subproblems: A natural choice is to use suffixes. x(i) = the maximum happiness Tim can achieve from day i to day n, assuming he is allowed to go outside on day i.
• Recurrence Relation: On day i, Tim has three main strategic choices:
  • Stay in on day Happiness gain is 0. The subproblem for the remaining days is x(i+1). Total happiness: x(i+1).
  • Go out on day Happiness gain is t_i. The subproblem for the remaining days starts on day i+2, which is x(i+2). Total happiness: t_i + x(i+2).
  • Go out on day Happiness gain is t_i + t_{i+1}. Tim must stay in on day i+2, so the next independent subproblem starts on day i+3. Total happiness: t_i + t_{i+1} + x(i+3).
  • The recurrence x(i) is the maximum of these three options.
• Topological Order & Base Cases: The subproblems are solved for i in decreasing order (from n down to 1). The base cases are x(n+1) = x(n+2) = 0 (no more days, no more happiness).
• Runtime: There are O(n) subproblems, and each takes O(1) non-recursive work to compute. The total runtime is O(n).
• Reconstructing the Solution: To find the actual plan (not just the max happiness value), one can store which of the three choices led to the maximum value at each step i. By backtracking from i=1, the full plan can be reconstructed.

3. Problem 2: Menix Edit Distance
Goal: Find the minimum number of "expensive" operations (adding or deleting a line) to transform file A into file B. "Cheap" operations (swapping adjacent lines) are also allowed and are free, but only if the swap is "useful" (i.e., it helps create a match).

• Subproblems: This is a classic edit distance problem on two sequences. The subproblems are defined on suffixes of the files. x(i, j) = the minimum cost to transform the suffix A[i:] into the suffix B[j:].
• Recurrence Relation: To compute x(i, j), consider the first lines of the suffixes, A[i] and B[j]. There are several cases for the first operation:
  • Match: If A[i] == B[j], the best strategy is to match them. The cost is 0, and we solve the subproblem on the remaining suffixes: x(i+1, j+1).
  • Delete The cost is 1 (for the deletion), and we must now transform the rest of A (A[i+1:]) into the current suffix of B (B[j:]). Total cost: 1 + x(i+1, j).
  • Insert To make A match B, we can insert B[j] at the beginning of A. The cost is 1 (for the insertion), and we must still transform the original A[i:] into the rest of B (B[j+1:]). Total cost: 1 + x(i, j+1).
  • Swap: If A[i] == B[j+1] and A[i+1] == B[j], we can perform a free swap. The cost is 0, and we solve the subproblem on the remaining suffixes: x(i+2, j+2).
  • The recurrence x(i, j) is the minimum of all applicable cases.
• Runtime: There are O(n^2) subproblems. The non-recursive work for each is O(k) because comparing two lines (strings of length k) takes O(k) time. The total runtime is O(k * n^2).

4. Problem 3: Saggy Mimsin's Blocks
Goal: Given n types of rectangular blocks, find the tallest possible tower that can be built by stacking them. A block can only be placed on another if its base is strictly smaller in both dimensions than the block below it. Blocks can be rotated.

• Analysis & Preprocessing:
  • Observation 1 (Block Orientations): Any rectangular block w x h x l has three distinct orientations when placed in a tower (one for each dimension serving as the "height").
  • Observation 2 (No Duplicates): Because of the strict containment rule, no two blocks with the exact same base dimensions can be used in the same tower.
  • Strategy:
    1. Create an expanded list of 3n potential "block-orientations" from the original n block types.
    2. Sort this list of 3n blocks lexicographically by their base dimensions. This is a crucial step that imposes an order on the problem.
• DP Formulation (Longest Increasing Subsequence variant):
  • This problem can now be modeled as finding the "tallest" path in a DAG, which is a variation of the Longest Increasing Subsequence (LIS) problem.
  • Subproblems: x(i) = the maximum height of a tower whose top block is the i-th block from our sorted list.
  • Recurrence Relation: x(i) = height(block_i) + max(x(j)) over all j < i such that block_i can be legally placed on top of block_j.
  • Runtime: O(n) subproblems (or O(3n)). Each subproblem requires a loop over O(n) previous subproblems. The total runtime is O(n^2).

5. Problem 4: Princess Plum's Mushrooms
Goal: In an n x n grid with mushrooms and trees, find the number of "quick" paths from (1,1) to (n,n) that collect the maximum possible number of mushrooms. A quick path is one that takes exactly 2n-2 steps.

• Analysis: A path from (1,1) to (n,n) requires n-1 steps down and n-1 steps right, for a total of 2n-2 steps. A "quick" path therefore has no slack; it can only move down or right.
• Two-Phase DP Solution: This problem requires two pieces of information: the max number of mushrooms, and the count of paths achieving that max. This is solved with two separate but related DPs.
  1. DP 1: Compute Max Mushrooms:
     • Subproblems: k(i, j) = max mushrooms on a quick path from (1,1) to (i,j).
     • Recurrence: k(i, j) = mushroom_at(i,j) + max(k(i-1, j), k(i, j-1)). If (i,j) has a tree, k(i,j) = -∞.
  2. DP 2: Count the Paths:
     • Subproblems: x(i, j) = number of quick paths from (1,1) to (i,j) that collect exactly k(i, j) mushrooms.
     • Recurrence: x(i, j) is the sum of x(i-1, j) (if the path from above is optimal) and x(i, j-1) (if the path from the left is optimal). A path is "optimal" if, for example, k(i-1, j) + mushroom_at(i,j) == k(i,j).
• Runtime: Both DP tables are n x n. Each entry takes O(1) to compute. The total runtime for both phases is O(n^2).

L25: Dynamic Programming 3

The lecture begins by contextualizing the ongoing unit on dynamic programming (DP), a powerful and general paradigm for algorithm design. The instructor, Erik Demaine, briefly touches on the history of the term "dynamic programming," noting it was coined by Richard Bellman in the 1950s.

• Review of SRTBOT Framework: The six-step framework for designing DP solutions is quickly reviewed:
  1. S - Subproblems: Define the smaller, related problems.
  2. R - Relate: Formulate a recurrence relation.
  3. T - Topological Order: Determine an acyclic order to solve subproblems.
  4. B - Base Cases: Define the smallest, non-recursive problems.
  5. O - Original Problem: State how the final answer is derived from the subproblems.
  6. T - Time: Analyze the runtime.
• Focus of the Lecture: The main theme is subproblem constraints and expansion. This involves starting with a simple subproblem definition (e.g., prefixes, suffixes) and then adding more parameters or constraints to it to "remember" extra information or state needed to formulate a valid recurrence.

2. SSSP as a Dynamic Program
The lecture reframes two Single-Source Shortest Path (SSSP) algorithms as dynamic programs to illustrate the power of the DP framework.
SSSP on a DAG

• S - Subproblems: The shortest path distance δ(s, v) for each vertex v.
• R - Relate: δ(s, v) = min( δ(s, u) + w(u, v) ) over all incoming neighbors u of v.
• T - Topological Order: The topological sort of the DAG itself.
• Connection: The "DAG Relaxation" algorithm previously seen is effectively a bottom-up implementation of this DP. A memoized recursive version would implicitly perform a DFS on the subproblem graph.

Bellman-Ford

• Subproblem Expansion: The standard SSSP subproblem is not sufficient for graphs with cycles. The subproblem is expanded to include a constraint on the number of edges.
• S - Subproblems: δ_k(s, v) = the weight of the shortest path from s to v using at most
• R - Relate: δ_k(s, v) is the minimum of two options:
  1. The shortest path using at most k-1 edges: δ_{k-1}(s, v).
  2. The shortest path using at most k-1 edges to an incoming neighbor u, plus the edge (u,v): δ_{k-1}(s, u) + w(u, v).
• Analysis: This expansion introduces the parameter k and makes the subproblem dependency graph acyclic (a subproblem for k depends only on subproblems for k-1), allowing the DP to work. The runtime is O(|V|*|E|).

3. All-Pairs Shortest Paths (Floyd-Warshall)
A new O(|V|^3) algorithm for APSP is introduced as another example of non-obvious subproblem expansion.

• Challenge: Repeatedly running Bellman-Ford gives O(|V|^2*|E|). Johnson's algorithm is better for sparse graphs. Floyd-Warshall is simple and competitive for dense graphs.
• S - Subproblems (The Trick): d(u, v, k) = the weight of the shortest path from u to v using only intermediate vertices from the set {1, 2, ..., k}.
• R - Relate: To compute d(u, v, k), consider the shortest path from u to v using intermediate vertices from {1, ..., k}. There are two cases for this path:
  1. It does not go through vertex k. The path's length is then d(u, v, k-1).
  2. It does go through vertex k. The path can be broken into a path from u to k and a path from k to v, both using only intermediate vertices from {1, ..., k-1}. The length is d(u, k, k-1) + d(k, v, k-1).
• The recurrence is the minimum of these two cases.
• Analysis: There are O(|V|^3) subproblems, and each takes O(1) non-recursive work. The total runtime is O(|V|^3).

4. Problem 1: Arithmetic Parenthesization
Goal: Given an arithmetic expression with numbers and operators (+, *), find a parenthesization that maximizes its value. The numbers can be negative.

• Subproblem Design: The input is a sequence, so a natural choice for subproblems is substrings. The "question" to ask is: what is the last operation to be performed?
• Challenge: If negative numbers are involved, maximizing a product A*B doesn't necessarily mean maximizing A and B individually (e.g., (-10) * (-10) is better than 5 * 5).
• The Fix: Subproblem Expansion: To handle this, we need to know both the maximum and minimum possible values for any sub-expression.
• DP Solution:
  1. S - Subproblems: X(i, j, opt) = the optimal value (where opt is either min or max) for the substring of the expression from index i to j.
  2. R - Relate: To compute X(i, j, opt), we guess the last operator k within the substring (i, j).
     • X(i, j, opt) = opt_{k, opt_L, opt_R} ( X(i, k, opt_L) star_k X(k, j, opt_R) )
     • We must try all possible splits k and all four combinations for the left and right sub-optimizations (min-min, min-max, max-min, max-max) to find the true overall optimum.
  3. T - Time: O(n^2) subproblems. Each takes O(n) work (to iterate over the split point k). Total time is O(n^3).

5. Problem 2: Piano/Guitar Fingering
Goal: Given a sequence of musical notes, assign a finger (1-5) to each note to minimize the total "difficulty." The difficulty is defined by a function d(note1, finger1, note2, finger2) which penalizes awkward transitions.

• Challenge: A simple subproblem min_difficulty(suffix_i) is not enough, because to calculate the difficulty of the transition from note i-1 to note i, we need to know which finger was used for note i-1. This information is not available in the simple subproblem definition.
• The Fix: Subproblem Expansion: Expand the subproblem to "remember" the finger used for the first note of the suffix.
• DP Solution:
  1. S - Subproblems: X(i, f) = the minimum difficulty to play the suffix of notes notes[i:], given that the first note (notes[i]) must be played with finger .
  2. R - Relate: To compute X(i, f), we need to decide which finger f' to use for the next note, notes[i+1]. We don't know the best choice, so we try them all.
     • X(i, f) = min_{f' in {1..5}} ( d(notes[i], f, notes[i+1], f') + X(i+1, f') )
  3. O - Original Problem: The final answer is min_{f in {1..5}} ( X(0, f) ), as we can start the piece with any finger.
  4. T - Time: There are O(n * F) subproblems, where F is the number of fingers (a constant, 5). Each subproblem takes O(F) work (to iterate over the choice of f'). Total time is O(n * F^2) = O(n).

The lecture concludes by showing how this DP framework can be generalized to more complex musical instruments like guitar (where you choose both a finger and a string) and even to video games like Rock Band, demonstrating the power of subproblem expansion to capture additional state.

L26: Dynamic Programming 4

The lecture, led by Erik Demaine, is the final installment in the four-part series on dynamic programming (DP). It focuses on a specific type of DP where the subproblems are defined by integers.

• SRTBOT Framework Review: The lecture begins with a quick recap of the SRTBOT framework for designing DP solutions:
  • S - Subproblems: Define the smaller problems. The key heuristics are revisited:
    • For sequences: Use prefixes, suffixes, or substrings.
    • For multiple sequences: Take the product of their subproblem spaces.
    • For integers: Use smaller integers as subproblems.
  • R - Relate: Formulate the recurrence relation, often by "guessing" a feature of the optimal solution and using local brute force.
  • T - Topological Order: Ensure the subproblem dependencies are acyclic.
  • B - Base Cases: Define the smallest, non-recursive problems.
  • O - Original Problem: State how the final answer is derived from the subproblems.
  • T - Time: Analyze the runtime, typically as (number of subproblems) * (work per subproblem).

2. Problem 1: Rod Cutting
Goal: Given a rod of integer length L and a table of values v(l) for selling a piece of length l, find a partition of the rod into smaller integer-length pieces that maximizes the total value.

• Subproblem Design: The input is an integer L and a value array. The key insight is to define the subproblems based on the length of the rod.
• DP Solution:
  1. S - Subproblems: X(l) = the maximum value obtainable from a rod of length l. We will solve this for all l from 0 to L.
  2. R - Relate: To find X(l), we must make a first cut. We don't know the optimal size p for the first piece to cut off, so we "guess" it by trying all possibilities.
     • X(l) = max_{1 ≤ p ≤ l} ( v(p) + X(l - p) )
     • We get the value v(p) for the first piece, and the remaining rod of length l-p can be optimally partitioned, which is given by the subproblem X(l-p).
  3. T - Topological Order: Solve for l in increasing order, from 0 to L.
  4. B - Base Case: X(0) = 0 (a rod of length 0 has no value).
  5. O - Original Problem: The answer is X(L).
  6. T - Time:
     • Number of subproblems: O(L).
     • Work per subproblem X(l): An O(l) loop to find the maximum.
     • Total time: O(L^2).

3. Polynomial vs. Pseudo-Polynomial Time
This section introduces a crucial distinction in runtime analysis.

• Polynomial Time: An algorithm's runtime is polynomial if it is bounded by a polynomial in the size of the input, measured in machine words.
• Rod Cutting Analysis: The input to the rod cutting problem is the integer L and a value array of size L. The total input size is O(L) words. The O(L^2) runtime is a polynomial in the input size L. Therefore, the rod cutting DP is a polynomial-time algorithm.

4. Problem 2: Subset Sum
Goal: Given a multiset A of n positive integers and a target integer T, determine if there exists a subset of A whose elements sum to exactly T.

• Subproblem Design: The input involves both a sequence (A) and an integer (T). A common strategy is to take the product of their subproblem spaces.
• DP Solution:
  • S - Subproblems: X(i, t) = a boolean value indicating whether it is possible to form a sum of t using only elements from the suffix of A starting at index i (A[i:]). We solve this for 0 ≤ i ≤ n and 0 ≤ t ≤ T.
  • R - Relate: To determine X(i, t), we consider the first element of the suffix, A[i]. There are two choices ("guesses"):
    • Don't include We must then be able to form the sum t using the rest of the suffix. This is given by the subproblem X(i+1, t).
    • Include We must then be able to form the remaining sum t - A[i] using the rest of the suffix. This is given by the subproblem X(i+1, t - A[i]).
    • The recurrence is the logical OR of these two possibilities: X(i, t) = X(i+1, t) OR X(i+1, t - A[i]).
  • T - Topological Order: Solve for i in decreasing order (from n down to 0). The order of t doesn't matter for correctness.
  • B - Base Case: X(n, t) (using an empty set of numbers). This is True if t=0 and False otherwise.
  • O - Original Problem: The answer is X(0, T).
  • T - Time: O(n * T) subproblems, O(1) work per subproblem. Total time is O(n * T).
• Pseudo-Polynomial Analysis: Is O(n * T) polynomial?
  • Input Size: The input is n integers for the set and one integer T. The total input size is O(n) words (assuming T and the elements of A fit in single words).
  • Analysis: The runtime O(n * T) is not polynomial in the input size n. The value of the integer T can be exponentially large relative to n (e.g., T = 2^n). If T is large, this algorithm is very slow.
  • Pseudo-Polynomial Time: This runtime is called pseudo-polynomial. An algorithm is pseudo-polynomial if its runtime is a polynomial in both the input size (n) and the numeric values of the integers in the input (T). These algorithms are efficient only when the numbers themselves are small (i.e., polynomially bounded in n).

5. Review of All DP Examples
The lecture concludes with a comprehensive review of all the DP examples covered in the four-lecture series, categorizing them by the key techniques used. This provides a high-level map of the DP landscape.

• Subproblem Structure:
  • Prefix/Suffix: Bowling, LCS, LIS, Rod Cutting, Floyd-Warshall (on vertices).
  • Substring: Alternating Coin Game, Parenthesization.
  • Multiple Sequences (Product): LCS, Subset Sum.
  • Integers: Fibonacci, Rod Cutting, Subset Sum, Bellman-Ford.
  • Vertices (Graphs): DAG SSSP, Bellman-Ford, Floyd-Warshall.
• Subproblem Expansion/Constraints:
  • Expansion by Constant Factor: Alternating Coin Game (player turn), Parenthesization (min/max).
  • Expansion by State: Piano Fingering (finger used).
  • Expansion by Bellman-Ford (number of edges).
  • Constraint (No Expansion): LIS (must start with A[i]).
• Recurrence Branching Factor:
  • Constant: Fibonacci, Bowling, LCS, Coin Game, Floyd-Warshall, Subset Sum.
  • : DAG SSSP, Bellman-Ford.
  • : LIS, Parenthesization, Rod Cutting.
• Combination Logic: Most were min/max (optimization), but Fibonacci used +, LCS and Subset Sum used OR (decision), and Parenthesization used the problem's own operators (+, *).

This systematic review ties all the examples together, showing how a few core principles (subproblem definition, relation formulation, expansion) can be applied in various combinations to solve a wide range of complex problems.

L27: Complexity

The lecture shifts focus from algorithms (finding efficient solutions to problems) to computational complexity (proving that problems are inherently difficult and that efficient algorithms likely do not exist).

• Polynomial vs. Exponential Time: The central theme is the distinction between polynomial time (O(n^c)), which is considered "good" or "efficient," and exponential time (O(2^(n^c))), which is considered "bad" or "intractable."

2. Complexity Classes: P, EXP, and R
Several fundamental complexity classes are defined to categorize problems based on their difficulty.

• P (Polynomial Time): The set of all decision problems that can be solved in polynomial time by a standard, deterministic computer. This class represents "efficiently solvable" problems and contains nearly all the problems studied in 6.006 so far (e.g., negative weight cycle detection via Bellman-Ford).
• EXP (Exponential Time): The set of problems solvable in exponential time. P is a strict subset of EXP (P ⊂ EXP), meaning there are problems (like generalized N-by-N Chess) that are known to be solvable in exponential time but provably not in polynomial time.
• R (Recursive): The set of all problems that can be solved in any finite amount of time. This class represents all computable or decidable problems. EXP is a subset of R.

3. Uncomputable Problems and the Halting Problem
The lecture makes a striking claim: most problems are not just hard, but are fundamentally unsolvable.

• The Halting Problem: A classic example of an uncomputable problem is the Halting Problem: "Given an arbitrary computer program and an input, will the program ever terminate (halt)?" It is proven that no general algorithm can exist to solve this for all possible programs.
• Proof: Most Problems are Uncomputable: A counting argument is used to show this.
  • Computer Programs: Any program can be represented as a finite string of bits, which can be mapped to a natural number. The set of all possible programs is therefore countably infinite.
  • Decision Problems: A decision problem is a function that maps every possible input (also a finite bit string) to a "yes" or "no" answer. This can be represented as an infinite string of bits. The set of all possible decision problems is uncountably infinite, equivalent in size to the set of real numbers.
  • Conclusion: Since there are "more" problems than there are programs, there are not enough programs to solve every problem. Most decision problems have no corresponding algorithm at all.

4. The Class NP: "Lucky" Algorithms and Verification
The most famous complexity class, NP, is introduced. It lies between P and EXP.

• Definition 1: Non-deterministic Polynomial Time: NP is the set of decision problems solvable in polynomial time by a non-deterministic (or "lucky") computer.
  • A lucky algorithm can make "guesses" at decision points (e.g., in a maze, guess whether to go left or right).
  • The model guarantees that if there is any sequence of guesses that leads to a "yes" answer, the algorithm will magically make that exact sequence of guesses.
  • Example (Tetris): The problem "Can you survive a given sequence of n Tetris pieces?" is in NP. A lucky algorithm can guess the optimal placement for each piece. If a survival strategy exists, the algorithm will find it in polynomial time.
• Definition 2: Polynomial-Time Verification: An equivalent definition is that NP is the set of problems for which a "yes" answer can be verified in polynomial time.
  • This requires a certificate (or "proof").
  • A polynomial-time verifier algorithm takes the original problem input and a certificate.
  • Example (Tetris): A certificate would be the complete sequence of moves (rotations and placements) for all pieces. The verifier would simply simulate the game using these moves and check if the player survives. This simulation is fast (polynomial time).

5. P vs. NP and NP-Hardness

• The P vs. NP Problem: It is known that P ⊆ NP. The biggest open question in computer science is whether P = NP. The strong consensus is that P ≠ NP, which implies that there are problems that are easy to verify but hard to solve. This is a million-dollar prize problem.
• Reductions: A key tool for relating the difficulty of problems is a polynomial-time reduction. A problem A reduces to a problem B if an efficient algorithm for B can be used to build an efficient algorithm for A. This implies that B is "at least as hard as" A.
• NP-Hardness: A problem is NP-hard if every problem in NP can be reduced to it. This means it is at least as hard as the hardest problems in NP.
• NP-Completeness: A problem is NP-complete if it is both in NP and NP-hard. These are the "hardest" problems within NP. Tetris is an example of an NP-complete problem.

6. The Landscape of NP-Completeness and Examples

• Implication: If P ≠ NP, then no NP-complete problem can be solved in polynomial time. Therefore, proving a problem is NP-complete is strong evidence that no efficient algorithm for it exists.
• Proving NP-Hardness: To prove a new problem X is NP-hard, one does not need to reduce all of NP to it. It is sufficient to reduce a known NP-hard problem (like 3-Partition) to X.
• Examples of Reductions: The lecture provides visual and conceptual sketches of reductions from the 3-Partition problem (a known NP-complete problem) to:
  • Jigsaw Puzzles: Showing that solving general jigsaw puzzles is NP-hard.
  • Tetris: A clever construction shows how surviving a specific Tetris game is equivalent to solving an instance of 3-Partition.
• List of NP-Complete Problems: A wide range of famous and practical problems are listed as NP-complete, including:
  • Subset Sum
  • LCS for n sequences
  • Longest Simple Path / Traveling Salesman Problem
  • 3-Coloring
  • Clique
  • 3D Shortest Paths with Obstacles
  • Boolean Satisfiability (SAT)
  • Minesweeper, Sudoku, and many other games and puzzles.

L28: PS 9

Instructor Justin Solomon begins by framing the session as a continuation of dynamic programming, focusing on problems where the runtime depends not just on the number of items (n) but also on the magnitude of the numbers involved.

• Pseudo-Polynomial Time: This concept is highlighted as a key theme. A pseudo-polynomial runtime is polynomial in the input size and the numeric values of the input. Such algorithms are efficient only when the numbers themselves are relatively small.
• SRTBOT Framework: The session continues to use the six-step SRTBOT framework (Subproblems, Relate, Topological Order, Base Cases, Original Problem, Time) to structure the solutions.
• Implementation Note: Two ways to translate a DP solution into code are revisited:
  • Top-Down (Memoization): A recursive approach with a cache.
  • Bottom-Up: An iterative approach that fills a DP table in topological order.

2. Problem 1: Coin-Crafting (Knapsack Problem)
Goal: A thief has n identical coins and can craft any of n unique objects. Object i has a price p_i and requires k_i coins to make. The thief wants to choose a set of objects to craft to maximize total revenue, given the constraint of having only n coins.

• Analysis: This is a classic 0/1 Knapsack problem. The two key parameters that define the state are which objects have been considered and how many coins have been spent.
• DP Solution:
  1. S - Subproblems: X(i, j) = the maximum revenue obtainable using at most i coins and considering only the first j objects.
  2. R - Relate: To compute X(i, j), we consider the j-th object. There are two choices:
     • Don't craft object The revenue is the same as if we only considered the first j-1 objects with i coins: X(i, j-1).
     • Craft object This is only an option if i ≥ k_j (we have enough coins). The revenue is p_j plus the maximum revenue from the first j-1 objects using the remaining i - k_j coins: p_j + X(i - k_j, j-1).
     • The recurrence X(i, j) is the maximum of these two options.
  3. T - Topological Order: Solve for j from 1 to n (outer loop) and for i from 1 to n (inner loop).
  4. B - Base Cases: X(i, 0) = 0 (no objects, no revenue) and X(0, j) = 0 (no coins, no revenue).
  5. O - Original Problem: The final answer is X(n, n).
  6. T - Time: There are O(n^2) subproblems (since the number of coins and objects are both n), each taking O(1) work. The total time is O(n^2).

3. Problem 2: Tim the Beaver's Career Fair (Unbounded Knapsack)
Goal: Tim the Beaver visits a career fair with n booths. Booth i gives swag with coolness c_i and weight w_i, and has a wait time of t_i. Tim can visit any booth multiple times. He has k total minutes and a bag that can hold a total weight of b. He can also spend h minutes to go home, empty his bag, and return. Find the maximum total coolness Tim can collect.

• Analysis: This is an unbounded knapsack problem with an extra "go home" action. The state is defined by the time remaining and the current weight in the bag.
• DP Solution:
  1. S - Subproblems: X(i, j) = the maximum coolness obtainable with i minutes remaining and j weight capacity left in the bag.
  2. R - Relate: From state (i, j), Tim has n+1 possible actions:
     • Go home: Cost is h minutes. New state is (i-h, b). Coolness is X(i-h, b).
     • Visit booth Cost is t_m + 1 minutes and w_m weight. New state is (i - (t_m+1), j - w_m). Coolness is c_m + X(i - (t_m+1), j - w_m). This action is only possible if time and weight are sufficient.
     • Give up: Coolness is 0.
     • The recurrence X(i, j) is the maximum over all these possible actions.
  3. T - Topological Order: Solve for i (time) from 0 to k and j (weight) from 0 to b.
  4. O - Original Problem: The answer is X(k, b).
  5. T - Time: O(k*b) subproblems. Each subproblem involves a loop over n booths. Total time is O(n*b*k). This is a pseudo-polynomial time algorithm.

4. Problem 3: Protein Parsing
Goal: Given a DNA string S and a dictionary P of "marker" substrings, find a partition of S into smaller substrings that maximizes the number of substrings that are in P.

• Challenge: A naive DP X(i) = max value for suffix S[i:] is too slow. The recurrence X(i) = max(1 + X(i + |m|)) over all markers m in P that match at S[i:] would require O(|P|*k) work per subproblem, leading to a total time of O(|S|*|P|*k).
• Solution (Preprocessing with Hashing): The bottleneck is repeatedly checking for matches against the dictionary P. This can be optimized.
  1. Preprocessing 1 (Hash the Dictionary): Insert all markers from P into a hash set. This takes O(k*|P|) time.
  2. Preprocessing 2 (Find All Matches): Create a boolean table M(i, j) which is true if the substring S[i:j] is in the hashed dictionary. This can be filled by iterating through all O(|S|*k) substrings of S of length at most k, hashing them, and checking the hash set. This takes O(|S|*k^2).
  3. DP on Preprocessed Data:
     • Subproblems: X(i) = max value for the suffix S[i:].
     • Recurrence: X(i) = max_{1 ≤ l ≤ k} ( M(i, i+l) + X(i+l) ). M(i, i+l) is 1 if the substring is a marker, 0 otherwise.
     • Runtime: The DP part now takes O(|S|*k). The total runtime is dominated by the preprocessing steps: O(k*|P| + k^2*|S|).

5. Problem 4: Lazy Egg Drop
Goal: In a building with n floors, you have k identical eggs. Find an optimal strategy for dropping eggs to determine the critical floor (the lowest floor from which an egg breaks) that minimizes the total height dropped in the worst case.

• Analysis: This is a minimax problem. You (min) choose which floor to drop from. The adversary/nature (max) decides whether the egg breaks or not, forcing you into the more costly subproblem.
• DP Solution:
  1. S - Subproblems: X(i, j, e) = the minimum total drop height required to solve the problem, given that the critical floor is known to be in the range [i, j] and you have e eggs remaining.
  2. R - Relate (Minimax Recurrence):
     • You choose a floor f between i and j to drop from. This costs h_f (height of floor f).
     • Nature then reveals one of two outcomes:
       • Egg breaks: The new range is [i, f-1], and you have e-1 eggs. The cost is X(i, f-1, e-1).
       • Egg survives: The new range is [f+1, j], and you have e eggs. The cost is X(f+1, j, e).
     • Since you must prepare for the worst case, the cost for picking floor f is h_f + max( cost_if_breaks, cost_if_survives ).
     • You get to pick the best f, so the recurrence is X(i, j, e) = min_{f in [i,j]} ( h_f + max(...) ).
  3. T - Time:
     • Number of subproblems: O(n^2 * k).
     • Work per subproblem: O(n) (to iterate over the choice of f).
     • Total time: O(n^3 * k).

The session concludes by setting up a fifth problem but running out of time to solve it in detail.

L29: Quiz 3

Instructor Jason Ku begins by outlining the scope and focus of the upcoming quiz.

• Main Focus: Dynamic programming (DP), covering the material from lectures 15-18 and problem sets 7-8.
• Cumulative Material: While the quiz is on DP, foundational concepts from Quiz 1 (data structures, asymptotics) and Quiz 2 (graphs) are still fair game and may be needed to solve problems.
• Core of DP: The central idea is solving problems recursively and using memoization to avoid recomputing overlapping subproblems, turning what would be an exponential recursion tree into an efficient traversal of a Directed Acyclic Graph (DAG) of subproblem dependencies.

2. The SRTBOT Framework Review
The six-step SRTBOT framework for designing and presenting DP solutions is reviewed in detail.

1. S - Subproblems: Define what each subproblem computes and how it is parameterized. This is the most crucial step. Common strategies include using prefixes, suffixes, or substrings for sequence inputs, and multiplying subproblem spaces for multiple inputs. Subproblems can also be expanded with extra parameters to "remember" state.
2. R - Relate: Write a precise mathematical recurrence relation showing how to solve a subproblem using the solutions to smaller ones. The general strategy is to identify a "question" about the solution and use local brute force (e.g., a max, min, or OR) over all possible answers.
3. T - Topological Order: Argue that the subproblem dependencies are acyclic, usually by showing that some parameter consistently increases or decreases.
4. B - Base Cases: Define the smallest subproblems that can be solved non-recursively. This is essential for the recursion to terminate.
5. O - Original Problem: State how the final answer is derived from the subproblems. This may also involve using parent pointers to reconstruct the actual solution (e.g., the sequence of choices) and not just the optimal value.
6. T - Time: Analyze the runtime, typically calculated as (Number of Subproblems) * (Non-recursive work per subproblem).

3. Problem 1: Lottery Winnings
Goal: Given a list of lottery payouts for the next n days, find the maximum winnings possible with the constraint that you can play at most twice in any seven-day period.

• Challenge: A simple subproblem X(i) = max winnings for days i to n is insufficient. The decision on day i depends on when the lottery was last played (e.g., on day i-1, i-2, etc.), but this information is not part of the state.
• Solution (Subproblem Expansion):
  1. S - Subproblems: Expand the subproblem to remember the "cool-down" period. X(i, j) = the maximum winnings for days i to n, assuming we just played on day and the next day we are allowed to play is i+j. The parameter j only needs to range from 1 to 6 (or a slightly larger constant).
  2. R - Relate: To compute X(i, j), we know we get the payout L_i. We then need to decide the next day to play, say i+k. This k must be at least j. The key insight is that it is never optimal for k to be very large (e.g., > 12), because one could always add an intermediate play without violating the constraint. Thus, the choice for k is over a constant number of days.
     • X(i, j) = L_i + max_{k=j..O(1)} ( X(i+k, new_cooldown) ). The new_cooldown depends on how close i and i+k are.
  4. Analysis: There are O(n) subproblems (since j is constant). Each takes O(1) work (the max is over a constant number of choices). The total time is O(n).

4. Problem 2: DNA Ancestry (LCS Variant)
Goal: Given three DNA sequences of length n (Alice, Bob, Charlie), determine if Charlie's DNA can be partitioned into two equal-length subsequences, one of which is a subsequence of Alice's DNA and the other a subsequence of Bob's.

• Analysis: This problem is a complex variation of Longest Common Subsequence (LCS) on three strings with an exact length constraint.
• Solution (Subproblem Expansion):
  1. S - Subproblems: The state needs to track our position in all three strings, plus how many characters we still need to match for Alice and Bob. X(i, j, k_a, k_b) = a boolean indicating if it's possible to partition the suffix of Charlie's DNA C[i+j:] such that k_a characters match a subsequence in A[i:] and k_b characters match a subsequence in B[j:].
     • The length of the suffix of Charlie's DNA is implicitly k_a + k_b. This avoids needing a fifth parameter.
  3. R - Relate: To compute X(i, j, k_a, k_b), we consider the first characters A[i], B[j], and C[current]. There are four main choices:
     • Match C[current] with A[i]: This is possible if A[i] == C[current]. Recurse on X(i+1, j, k_a-1, k_b).
     • Match C[current] with B[j]: Possible if B[j] == C[current]. Recurse on X(i, j+1, k_a, k_b-1).
     • Skip A[i] (don't use it in a match): Recurse on X(i+1, j, k_a, k_b).
     • Skip B[j]: Recurse on X(i, j+1, k_a, k_b).
     • The recurrence is the logical OR of the outcomes of these choices.
  5. O - Original Problem: X(0, 0, n/2, n/2).
  6. T - Time: The number of subproblems is O(n * n * (n/2) * (n/2)) = O(n^4). Each subproblem takes O(1) work. The total time is O(n^4).

5. Problem 3: Tapas (0/1 Knapsack with a Twist)
Goal: Given n tapas plates, each with a volume, calorie count, and a sweetness label (0 or 1), find the maximum total volume of food one can eat without exceeding k calories, while eating exactly s sweet plates. Each plate can be chosen at most once.

• Analysis: This is a 0/1 Knapsack problem with an additional "side constraint" on the number of sweet plates. This requires expanding the subproblem state. The runtime is pseudo-polynomial.
• DP Solution:
  1. S - Subproblems: X(i, j, s') = the maximum volume obtainable considering only plates i through n, with a remaining calorie budget of j, and needing to eat exactly s' more sweet plates.
  2. R - Relate: For plate i, we have two choices:
     • Don't eat plate The max volume is given by the subproblem on the remaining plates: X(i+1, j, s').
     • Eat plate This is possible if its calories c_i ≤ j and its sweetness s_i ≤ s'. The volume is v_i + X(i+1, j-c_i, s'-s_i).
     • The recurrence X(i, j, s') is the maximum of these two options.
  4. B - Base Cases:
     • If i > n (no more plates) and s' == 0 (sweet plate constraint met), the max volume is 0.
     • If i > n and s' > 0 (sweet plate constraint failed), the max volume is -∞ (an invalid state).
  6. O - Original Problem: The answer is X(1, k, s).
  7. T - Time: Number of subproblems is O(n * k * s). Each takes O(1) work. Total time is O(n*k*s). This is a pseudo-polynomial runtime because of the dependence on the numeric values k and s.

L30: Course Review

The lecture, led by instructor Jason Ku, serves as a high-level review of the entire course and a look forward to more advanced topics. It begins by recapping the three primary goals of 6.006:

1. Solve Computational Problems: Develop algorithms to find solutions.
2. Argue Correctness: Prove that the algorithms work correctly for all valid inputs. This is framed as an application of the principles learned in discrete mathematics (6.042).
3. Argue Efficiency ("Goodness"): Analyze the performance of algorithms, especially how they scale with input size. This relies on the course's model of computation and asymptotic analysis.
4. Communication: A fourth, overarching goal is emphasized: the ability to clearly communicate these algorithms and arguments to other humans, not just to a computer.

2. The Big Picture: A Map of the Course Content
The material covered in the course is broken down into three main units, corresponding to the three quizzes.
Unit 1: Foundations and Data Structures (Quiz 1)

• Core Idea: Developed a set of "black box" tools for storing and finding items in a collection.
• Key Concepts:
  • Sequence Interface: For maintaining an extrinsic (user-defined) order. Implemented by arrays, linked lists, dynamic arrays, and sequence AVL trees.
  • Set Interface: For finding items based on their intrinsic value (key). Implemented by sorted arrays, hash tables, and set AVL trees (BSTs).
  • Sorting: A fundamental problem whose solutions (like Merge Sort and Radix Sort) often rely on or enable the creation of efficient data structures.

Unit 2: Graph Algorithms (Quiz 2)

• Core Idea: Moved from simple collections to data with explicit relationships, modeled as graphs (vertices and edges). Graphs are a powerful tool for modeling a vast range of real-world systems.
• Key Concepts:
  • Graph Traversal: BFS and DFS for exploring graphs.
  • Unweighted Shortest Paths: Solved with BFS.
  • Weighted Shortest Paths: A major focus, with a suite of algorithms for different graph types:
    • DAG Relaxation (for DAGs)
    • Dijkstra's Algorithm (for non-negative weights)
    • Bellman-Ford (for general weights, can detect negative cycles)
    • Johnson's Algorithm (for All-Pairs Shortest Paths, using reweighting to enable Dijkstra)

Unit 3: Algorithmic Design (Quiz 3)

• Core Idea: Shifted from using existing algorithms to designing new ones from scratch using a systematic, recursive framework.
• Key Concept: Dynamic Programming:
  • Framed as an application of graph theory where the graph of subproblem dependencies is implicitly constructed.
  • The goal is to define subproblems and a recursive relation between them, ensuring the dependency graph is a DAG to allow for efficient computation via memoization or a bottom-up approach.

3. A Look Ahead: 6.046 (Design and Analysis of Algorithms)
The lecture positions the next course in the theory sequence, 6.046, as a natural continuation of 6.006. While 6.006 focuses on using and understanding a core set of algorithms, 6.046 delves deeper into the design and, more significantly, the analysis of new and more complex algorithms.

• More Advanced Topics:
  • Data Structures: Amortized analysis is formalized with potential functions (e.g., for Union-Find).
  • Graph Algorithms: More advanced problems like Minimum Spanning Trees and Network Flows are covered.
  • Algorithm Design Paradigms: Deeper dives into greedy algorithms and more complex dynamic programming and divide-and-conquer strategies.
  • Complexity and Reductions: Formal tools for proving that problems are NP-hard.

4. Beyond the 6.006 Framework: New Paradigms
The final part of the lecture explores topics beyond the standard 6.006/6.046 curriculum, where the fundamental assumptions of the course are relaxed or changed.

• Randomized Algorithms: Instead of deterministic correctness and efficiency, algorithms can be:
  • Las Vegas: Always correct, but only probably efficient (like hashing).
  • Monte Carlo: Always efficient, but only probably correct.
• Numerical and Continuous Algorithms: Dealing with problems on real numbers, which cannot be perfectly represented on a computer. This involves approximation and paying for precision with computation time.
• Approximation Algorithms: For NP-hard optimization problems, where finding the exact optimal solution is intractable, these algorithms find a solution that is provably close (e.g., within a constant factor) to the optimum in polynomial time.
• Changing the Model of Computation: Exploring what becomes possible with different, more powerful, or more realistic models of computation.
  • Cache Models: More accurately model the hierarchy of memory (registers, caches, RAM, disk) where access times are not uniform.
  • Quantum Computing: Leverages principles like superposition and entanglement to potentially solve certain problems (like factoring) exponentially faster than classical computers.
  • Parallel and Distributed Computing: Explores how to speed up computation by using multiple processors, either sharing memory (multicore) or communicating over a network (distributed).

The lecture concludes by framing 6.006 as a foundational course that provides the essential tools and thinking patterns for tackling a wide array of problems in computer science and beyond.

L31: Algorithms, next steps…

The final lecture begins with instructor Jason Ku reflecting on the broader context of the course and its connection to real-world innovation.

• A Personal Journey: Ku shares his personal story, starting not as a computer scientist but as a mechanical engineer with a passion for origami. He realized that his intuitive design process for complex origami models was, in fact, algorithmic. This led him to collaborate with Professor Demaine and transition into computer science.
• The Vision of Programmable Matter: The ultimate dream is to apply the principles of reconfigurable software to the physical world. Just as a phone can run countless apps, a physical object could one day be "reprogrammed" to reconfigure its own matter, transforming from one device to another. This futuristic vision is rooted in the algorithmic study of reconfigurable structures, like origami.
• Introduction to Instructor Research: The rest of the lecture is dedicated to showcasing how each of the three instructors applies the principles of 6.006 and beyond in their own research, starting with Professor Demaine.

Part 1 by Erik Demaine: Computational Geometry, Folding, and Data Structures
Professor Demaine presents a whirlwind tour of his research, demonstrating the deep connection between algorithms, geometry, and art.

• Computational Origami (6.849): This field explores two fundamental questions:
  • Origami Design: Given a target 3D shape, can you design a crease pattern to fold it? This is often algorithmically tractable.
  • Foldability: Given a crease pattern, can it be folded flat? This is often proven to be NP-hard.
• Universality and Origamizer: A key result is that any 3D shape can be folded from a large enough square of paper. Modern tools like the "Origamizer" software implement algorithms that turn 3D models (like the Stanford bunny) into efficient, foldable crease patterns, enabling a new form of manufacturing with materials like steel.
• Maze Folding: A concrete example of an algorithmic approach where a complex problem (folding a 3D maze) is solved by designing small, reusable "gadgets" (crease patterns for different types of junctions) and composing them.
• The Fold-and-Cut Problem: A classic problem in computational geometry is demonstrated live. By folding a piece of paper flat and making a single straight cut, complex shapes like a swan or the MIT logo can be created. Algorithms exist to generate the necessary folding patterns for any desired set of cuts.
• Self-Assembly (A Different Model of Computation): Demaine introduces a completely different computational model based on DNA tiles that self-assemble based on "glues." This geometric model of computation can be programmed to perform tasks like building a binary counter or even creating a "replicator" that can photocopy 3D objects.
• Advanced Data Structures (6.851): Demaine briefly touches upon research in data structures that goes beyond the O(log n) bounds of AVL trees for the dynamic ordered set problem. He mentions advanced structures like van Emde Boas trees (O(log w)) and Fusion Trees (O(log n / log w)), which offer superior performance in different regimes of the Word RAM model.

Part 2 by Justin Solomon: Applied Geometry in Graphics and Beyond
Professor Solomon discusses his research, which applies geometric and algorithmic principles to practical problems in computer graphics, machine learning, and even public policy.

• Geometric Algorithms (6.837, 6.838): Solomon's courses focus on geometry from a computational perspective.
• Shortest Paths on Surfaces: He presents a key example showing the limits of standard graph algorithms. Running Dijkstra's algorithm on the edges of a triangle mesh will not find the true shortest path (geodesic distance), because the true path can cut across the faces of the triangles. This requires more advanced and specialized geometric algorithms.
• Computer Graphics and Data Structures: The performance demands of modern computer graphics are immense. The naive ray casting algorithm (runtime: pixels * objects) is too slow for complex scenes like the 69,000-triangle Stanford bunny. The solution is to use spatial data structures (like k-d trees or bounding volume hierarchies) to quickly prune the search space, achieving near O(log n) performance per ray.
• Political Redistricting: A highly relevant application of graph theory. A state can be modeled as a graph where vertices are precincts and edges represent adjacency. A voting district is a connected subgraph.
  • The Computational Challenge: The number of possible valid districting plans is astronomically large (quintillions for a state like Iowa).
  • Research Focus: Rather than finding one "best" plan (an ill-defined and NP-hard problem), the research focuses on analyzing proposed plans by comparing them to a large, randomly generated ensemble of other valid plans.
  • A Hard Problem: Solomon notes a key theoretical result: the seemingly simple task of uniformly sampling a random, valid districting plan is itself a computationally hard problem, casting doubt on the statistical validity of some analysis methods.

Conclusion and Farewell
The lecture concludes with all three instructors sharing a final message. They emphasize that the principles of algorithms, data structures, and computational thinking are not just academic exercises but are truly foundational, appearing in every corner of computer science and beyond. They thank the students for taking the course and wish them well.