Course: Foundations of Computer Science, CS 101, University of Michigan Difficulty: Intermediate to Advanced Prerequisites: Basic proof techniques, familiarity with Big-O notation, introductory graph theory. If you have not covered recursion and induction, review those first.
This set of notes covers the algorithm design and graph theory material tested on the CS 101 midterm. The topics span three major paradigms: divide and conquer, dynamic programming, and greedy algorithms, each applied to classical problems you will see on the exam. You should already be comfortable with asymptotic notation and basic recursion. If you have not yet studied formal languages or decidability, those are covered in a separate companion document.
The midterm tests your ability to recognise which algorithmic paradigm fits a given problem, write or trace pseudocode for key algorithms (MergeSort, closest pair, LCS, edit distance, Floyd-Warshall, knapsack, Kruskal's), and analyse their time and space complexity. Expect at least one proof-style question involving correctness of a greedy or DP approach.
Divide and conquer
An algorithm design strategy that splits a problem into smaller sub-problems, solves each recursively, and combines the results. Think of it as breaking one hard job into several easier ones, then stitching the answers together.
Dynamic programming (DP)
A technique for solving problems with overlapping sub-problems by storing (memoising) intermediate results in a table so each sub-problem is solved only once. In simple terms, it trades memory for speed by never re-doing work.
Greedy algorithm
An approach that builds a solution step by step, always choosing the locally optimal option at each stage. It works only when a problem has the greedy-choice property and optimal substructure.
Longest common subsequence (LCS)
The longest sequence of characters that appears, in order but not necessarily contiguously, in both of two strings. For example, the LCS of "ABCDE" and "ACE" is "ACE" (length 3).
Edit distance (Levenshtein distance)
The minimum number of insertions, deletions, and substitutions needed to transform one string into another. Each operation can carry a different cost (c_i, c_d, c_s).
Floyd-Warshall algorithm
A DP algorithm that computes shortest paths between all pairs of vertices in a weighted graph. Runs in O(V^3) time and O(V^2) space.
Knapsack problem
Given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight stays within a capacity and the total value is maximised. The 0/1 variant forbids taking fractions of items.
Kruskal's algorithm
A greedy algorithm for finding the minimum spanning tree (MST) of a connected, weighted graph. It sorts edges by weight, then adds each edge that does not create a cycle.
Minimum spanning tree (MST)
A subset of edges in a connected, weighted graph that connects all vertices with the minimum possible total edge weight, forming a tree (no cycles).
MergeSort
A divide-and-conquer sorting algorithm. It splits the array in half, recursively sorts each half, then merges the sorted halves. Runs in O(n log n) time.
Closest pair of points
The problem of finding the two points in a set whose Euclidean distance is smallest. The divide-and-conquer solution runs in O(n log n).
Split the array at the midpoint: m = floor(n/2)
Recursively sort the left half A[1..m] and the right half A[m+1..n]
Merge the two sorted halves with a linear-time merge subroutine
Time complexity: O(n log n) in all cases
Space complexity: O(n) for the auxiliary merge array
The merge subroutine compares the fronts of two sorted arrays and appends the smaller element to the output, then appends whatever remains
Input: A set of n >= 2 points in the plane
Divide: Find the median x-coordinate m. Split the points into L (x <= m) and R (x > m)
Conquer: Recursively find the closest pair in L (distance delta_L) and in R (distance delta_R). Set delta = min(delta_L, delta_R)
Combine: The tricky part. Look at points within a vertical strip of width 2*delta centred on the median. Sort those strip points by y-coordinate. For each point in the strip, compare it only to the next 7 points in y-order (a constant). This is what keeps the combine step linear
Overall time: O(n log n)
The constant 7 comes from a geometric packing argument: at most 8 points can fit in a delta x 2*delta rectangle without any two being closer than delta
Problem: Given two strings S1[1..N] and S2[1..M], find the length of their longest common subsequence
Build an (N+1) x (M+1) table. Base cases: table(i, 0) = 0 and table(0, j) = 0
Recurrence:
If S1[i] = S2[j]: table(i, j) = table(i-1, j-1) + 1
Else: table(i, j) = max(table(i-1, j), table(i, j-1))
To recover the actual subsequence, backtrack through the table from table(N, M)
Time: O(N * M). Space: O(N * M), reducible to O(min(N, M)) if only the length is needed
Problem: Find the minimum cost to transform string A into string B using insertions (cost c_i), deletions (cost c_d), and substitutions (cost c_s)
Build an (n+1) x (m+1) table M where n = |A| and m = |B|
Base cases: M[i][0] = i * c_d (delete everything from A). M[0][j] = j * c_i (insert everything into empty string)
Recurrence: For each cell M[i][j]:
If A[i] = B[j]: M[i][j] = M[i-1][j-1] (no cost, characters match)
Else: M[i][j] = min(M[i-1][j-1] + c_s, M[i][j-1] + c_i, M[i-1][j] + c_d)
Time: O(n * m). Space: O(n * m)
Problem: Given a weighted directed graph G = (V, E), compute the shortest path between every pair of vertices
Initialise d^0(i, j) = weight(i, j) if an edge exists, infinity if not, 0 if i = j
Recurrence: d^k(i, j) = min(d^(k-1)(i, j), d^(k-1)(i, k) + d^(k-1)(k, j))
Iterate k from 1 to |V|. After all iterations, d^|V|(i, j) is the shortest path from i to j
Time: O(V^3). Space: O(V^2) if you keep only two layers of the table (or overwrite in place)
Problem: Given n items with weights and values, and a knapsack of capacity C, maximise total value without exceeding capacity
Bottom-up approach: Build a table where each entry represents the best value achievable using a subset of the first i items with capacity c
Recurrence: For item i with weight w_i and value v_i:
If w_i > c: skip item i (carry forward the row above)
Else: max(value without item i, v_i + value with remaining capacity c - w_i)
Time: O(n * C). Space: O(n * C), reducible to O(C) with a single-row trick
This is pseudo-polynomial: the running time depends on the numeric value of C, not the number of bits needed to represent it
Input: A connected, weighted, undirected graph G = (V, E)
Steps:
Start with an empty edge set S
Sort all edges by weight (ascending)
For each edge e in sorted order: if adding e to S does not create a cycle, add it. Otherwise skip it
Stop when S contains |V| - 1 edges
Cycle detection is typically handled with a Union-Find (disjoint set) data structure, giving near-constant time per operation
Time: O(E log E) for the sort, which dominates
The smallest-weight edge in the entire graph must be in any MST
In any cycle C of G, the largest-weight edge in C cannot be in any MST
If all edge weights are distinct, the MST is unique
The cut property: for any cut of the graph, the lightest edge crossing the cut belongs to the MST
Removing an edge from the MST partitions the vertices into two components. Any edge reconnecting those components with lower weight would contradict the MST, so no such edge exists
LCS recurrence
L(S1[1..N], S2[1..M]) =
0, if N = 0 or M = 0
L(S1[1..N-1], S2[1..M-1]) + 1, if S1[N] = S2[M]
max(L(S1[1..N-1], S2[1..M]), L(S1[1..N], S2[1..M-1])), if S1[N] != S2[M]
Edit distance recurrence
ED(i, j) =
M(i, j-1) + c_i (insertion)
M(i-1, j) + c_d (deletion)
M(i-1, j-1) + c_s, if A[i] != B[j] (substitution)
M(i-1, j-1), if A[i] = B[j] (free match)
Take the minimum of the applicable options.
Floyd-Warshall recurrence
d^k(i, j) = min(d^(k-1)(i, j), d^(k-1)(i, k) + d^(k-1)(k, j))
Shortest path sub-path property
If p is a shortest path from u to v, and p' is a sub-path of p from u to w, then p' is a shortest path from u to w. This is the foundation of all shortest-path DP.
Knapsack recurrence
K(i, c) = max(K(i-1, c), v_i + K(i-1, c - w_i)) when w_i <= c, otherwise K(i, c) = K(i-1, c)
MergeSort is the basis of most library sorting implementations (e.g. Python's Timsort is a hybrid that includes merge sort). Stable sorting matters when you need to preserve the relative order of equal elements, such as sorting transactions first by date, then by amount.
Edit distance powers spell-checkers, DNA sequence alignment in bioinformatics, and diff tools that show you what changed between two versions of a file.
Floyd-Warshall is used in network routing protocols to compute shortest paths between all routers. It is practical when the graph is dense and you need every pair, not just one source.
Kruskal's MST appears in network design: laying cable or fibre to connect offices at minimum total cost, or in clustering (remove the heaviest edges from the MST to partition data points into groups).
Knapsack models any resource-allocation problem with a budget constraint: loading cargo, selecting projects with limited funding, or choosing which features to build in a sprint.
Students often think the closest pair can only be found by checking every pair of points. It cannot be done faster than O(n log n), but it absolutely can be done that fast with divide and conquer, not the brute-force O(n^2).
A common error is confusing "subsequence" with "substring." A subsequence does not need to be contiguous. "ACE" is a subsequence of "ABCDE" but not a substring.
Students sometimes assume Floyd-Warshall works only on graphs with positive weights. It handles negative weights, but not negative-weight cycles (those make shortest paths undefined).
With knapsack, students mix up the 0/1 variant (each item taken or not) with the fractional variant (which is solvable greedily). The greedy approach does not work for 0/1 knapsack.
In Kruskal's, students forget that the algorithm requires a connected graph to produce a spanning tree. On a disconnected graph it produces a minimum spanning forest instead.
⚠️ Be able to fill in a partially completed DP table for LCS or edit distance. This is a classic exam format.
⚠️ Know the MST properties cold. "The smallest-weight edge must be in the MST" and "the heaviest edge in any cycle cannot be in the MST" are true/false staples.
⚠️ Be ready to trace Floyd-Warshall on a small graph (4 to 5 vertices). You will likely be asked to fill in the d^k matrix for a specific k.
⚠️ Understand why knapsack is pseudo-polynomial, not polynomial. If the exam asks "is knapsack in P?" the answer is: not the 0/1 version (it is NP-hard), but the DP runs in O(nC), which is polynomial in the value of C, not in the input size.
⚠️ Know the shortest-path sub-path property and be able to state it precisely. It underpins every shortest-path algorithm covered in this course.
True or False: MergeSort is an in-place sorting algorithm. (False, it requires O(n) auxiliary space.)
True or False: The LCS of two strings must be a contiguous substring of both. (False, it is a subsequence.)
Fill in the blank: Floyd-Warshall runs in O(___) time. (V^3.)
True or False: In Kruskal's algorithm, you add the next lightest edge even if it creates a cycle. (False, you skip edges that create cycles.)
True or False: The 0/1 knapsack problem can be solved optimally with a greedy algorithm. (False, greedy works for fractional knapsack only.)
Q: Given strings S1 = "ABCBDAB" and S2 = "BDCAB", what is the length of the LCS?
A: 4. One possible LCS is "BCAB."
Q: You run Floyd-Warshall on a graph and discover that d(v, v) < 0 for some vertex v after the algorithm finishes. What does this mean?
A: The graph contains a negative-weight cycle reachable from v. The shortest-path problem is not well-defined in this case.
Q: Why does the closest-pair algorithm only check 7 neighbours in the strip, rather than all strip points?
A: A packing argument shows that at most 8 points can lie in a delta x 2*delta rectangle without any pair being closer than delta. So each point needs to be compared against at most 7 others, keeping the combine step O(n).
Q: Describe a scenario where a greedy algorithm fails for the 0/1 knapsack problem.
A: Suppose the knapsack has capacity 10. Item A has weight 6 and value 8. Item B has weight 5 and value 5. Item C has weight 5 and value 5. Greedy by value-to-weight ratio picks A first (ratio 1.33), then cannot fit B or C. Total value: 8. But picking B + C gives total weight 10 and total value 10, which is better.
Q: State two properties of minimum spanning trees that are commonly tested.
A: (1) The lightest edge in the entire graph is always in the MST. (2) The heaviest edge in any cycle is never in the MST.
Dynamic programming and greedy algorithms reappear throughout the decidability and computability half of the course: reductions often involve constructing new machines that simulate or transform existing ones, which is structurally similar to building DP tables from sub-problems. The formal notion of "optimal substructure" connects directly to the sub-path property of shortest paths, which also underpins the correctness proofs for Dijkstra's algorithm (not on this midterm, but covered later). MST properties connect to the broader study of graph theory and network flow, which typically follows in the second half of the course.
MergeSort, merge sort, divide and conquer sorting, O(n log n) sort, closest pair of points, closest pair algorithm, LCS, longest common subsequence, edit distance, Levenshtein distance, string matching, sequence alignment, Floyd-Warshall, all-pairs shortest paths, APSP, shortest path DP, knapsack problem, 0/1 knapsack, pseudo-polynomial, Kruskal's algorithm, MST, minimum spanning tree, greedy MST, cut property, cycle property, Union-Find, disjoint set, CS 101, Foundations of Computer Science, UMich, midterm review, algorithm design paradigms