Algorithms and Analysis

A short textbook for COMP 550 Midterm 1 · Arrays, Graphs, and Greedy Algorithms · UNC Fall 2026

Download as PDF

Preface

This book covers the first three chapters of COMP 550: algorithms on arrays, the essential graph algorithms, and greedy algorithms with their correctness proofs. It is written to be read from front to back in two or three sittings. Each chapter introduces a small number of algorithms, states precisely what they compute, proves that they are correct, and analyzes how long they take. Worked examples show the algorithms running on concrete inputs, and every chapter ends with exercises whose solutions are hidden until you click. The problem-set problems from the course are included as worked examples in the chapters where they belong, because the exam reuses them.

About the exam

Midterm 1 is on Tuesday, September 22, in class. It lasts 65 minutes, is closed book with no electronics, and has assigned seating; bring your One Card. There are five problems worth five points each, and only writing inside the answer boxes is graded.

Problem 1 consists of five one-point questions in which you run an algorithm by hand on a small input and write the output with no explanation: what Two Sum returns, the distance array from BFS, the post array from DFS, which edges are back edges, and so on. Problems 2 through 5 each ask you to describe an algorithm with a given running time, explain why it is correct, and analyze its running time. At least two of these four are copied word for word from the problem sets; on the practice midterm, Problem 2 was PS 1.4 and Problem 3 was PS 2.3, and the remaining two were close variants of problem-set problems.

How solutions are written

Every problem in this course is posed as an input, a goal, and a target running time, and every solution has three parts. The algorithm is given in a sentence or two of English followed by short pseudocode that calls known algorithms by name. The correctness argument explains why the output is always what the problem asks for; this book uses four styles of argument, each introduced where it is first needed: the loop invariant (Chapter 2), the two-directional argument "anything returned is valid, and if a solution exists one is returned" (Chapter 2 and Chapter 4), case analysis on the order in which a search visits vertices (Chapter 4), and the exchange argument (Chapter 5). The running time is almost always the number of iterations multiplied by the cost of one iteration, plus the cost of any sorting or searching the algorithm calls; for graph algorithms the standard sentence is that each adjacency list is scanned at most once, so the total is O(m + n).

How to read this book

Read Chapters 1 and 2 first and trace the array algorithms by hand on small inputs. Chapters 3 and 4 cover graphs; draw a few small directed graphs of your own and run BFS and DFS on them until the bookkeeping is automatic. Chapter 5 is the greedy chapter, where the single most important idea is the exchange argument. Chapter 6 works the practice midterm, Chapter 7 is a second practice exam in the same format, and Chapter 8 is a one-page summary for the night before.

Blue boxes contain definitions and theorems to know by heart. Orange boxes describe mistakes that are easy to make and cost points. Green boxes connect a topic to how it is tested.

Ch 11. Optimization problems and the greedy idea

Most of the problems in this course are optimization problems: among a finite set of candidate solutions, find the best one. Two words recur in every such problem and deserve precise definitions.

For example, if the problem is to attend as many events as possible from a schedule, a feasible solution is any set of events no two of which overlap in time, and an optimal solution is a feasible set of maximum size. An algorithm for an optimization problem is correct if ALG is always optimal.

1.1 A first look at greedy algorithms

A greedy algorithm constructs a solution one decision at a time, choosing at each step the option that looks best by some simple rule, and never revisiting a decision. Greedy algorithms are attractive because they are simple and fast. The difficulty is that a rule which sounds sensible can be wrong, and the only way to know is to prove it right or to exhibit an input on which it fails. Consider the following schedule of five events.

The largest set of pairwise compatible events has three members, namely events 2, 3, and 5. Suppose we try to find such a set greedily by repeatedly adding an event that does not conflict with those already chosen. Four rules suggest themselves.

Rule A: always add the shortest remaining event. This fails on the three events [1,10], [9,12], [11,20]. The shortest is [9,12], but it overlaps both of the others, so the rule chooses one event while two are possible.

Rule B: always add the event that starts earliest. This fails whenever one long event starts first and overlaps two short events that follow it: the rule takes the long event and gets one, while the two short events give two.

Rule C: always add the event that conflicts with the fewest remaining events. This rule is more subtle, and it takes eleven events to break it: [1,3], three copies of [2,5], [4,7], [6,9], [8,11], three copies of [10,13], and [12,14]. The event [6,9] conflicts with only two others, so the rule chooses it first; after that at most two more events fit, for a total of three. But the four events [1,3], [4,7], [8,11], [12,14] are pairwise compatible.

Rule D: always add the event that ends earliest. This rule is correct. The proof is the subject of Section 5.5, and it is a model for every correctness proof in Chapter 5.

Two lessons carry forward. First, a greedy algorithm is a claim that needs a proof. Second, when a greedy rule is wrong, a small counterexample is the cleanest way to say so, and you should be able to produce ones like Rules A and C on demand.

1.2 A preview of the knapsack problem

Suppose you have five dollars and three items for sale: the first is worth 5 and costs 2, the second is worth 2 and costs 1, and the third is worth 7 and costs 3. A feasible purchase costs at most 5, and the optimal one is the first and third items, worth 12. It is worth noticing that the second item has the best value per dollar of the three and yet does not appear in the optimal purchase. When items must be bought whole, the rule "best value per dollar first" can fail; this version of the problem is solved by dynamic programming in a later chapter and is not on this exam. When items may be bought in fractions, the same rule is correct, and that version is Section 5.6.

Exercises

Ch 22. Algorithms on arrays

This chapter introduces five short algorithms on arrays. They are useful in their own right, but their main purpose is to establish how algorithms are described, how their running time is measured, and how their correctness is argued. The habits formed here are used in every later chapter.

2.1 Notation

An array A of length n has elements A[1], A[2], …, A[n]. The notation A[i:j] denotes the subarray consisting of A[i] through A[j]. Loops are written in the form for i = 2, ..., n:. When an algorithm needs to remember which numbers from 1 to n it has already encountered, it uses an array B = [0]*n of n zeros and sets B[k] = 1 upon seeing k; this replaces the hash tables that are not permitted in this course.

2.2 Maximum of an array, and the measurement of running time

Given an array A of n distinct positive integers, we wish to return the largest. The natural algorithm keeps a running maximum.

Max-in-Array(A):
  m = A[1]
  for i = 2, ..., n:
    m = max(m, A[i])
  return m

The running time of an algorithm is the number of primitive operations it performs in the worst case over inputs of size n, where a primitive operation is an assignment, a comparison, an arithmetic operation, an array access, or a procedure call. Counting exactly for Max-in-Array gives an expression like 4n − 1. Such exact counts are never the object of interest. What matters is the rate of growth as n becomes large, and this is captured by asymptotic notation.

Nearly every running-time analysis in this course has the same form: the number of iterations of the main loop multiplied by the cost of one iteration, plus the cost of any sorting or searching performed beforehand. For Max-in-Array there are at most n iterations of constant cost, so the running time is O(n).

Correctness is argued by a loop invariant, a statement that is true after every iteration. Here the invariant is that after iteration i, m equals the maximum of A[1:i]. It holds after the first iteration, since m is then max(A[1], A[2]); and if it holds before iteration i, then the assignment m = max(m, A[i]) makes it hold after. When the loop ends with i = n, the invariant says m = max(A[1:n]), which is what we wanted.

2.3 Two Sum and the two-pointer technique

Let A be an array of n distinct integers sorted in increasing order, and let t be a target. We wish to find indices i < j with A[i] + A[j] = t, or report that no such pair exists. For instance, with A = [1, 3, 4, 5, 7, 10, 11] and t = 10, the answer is (2, 5), because 3 + 7 = 10.

Examining every pair takes O(n²) time. The sorted order permits something much better. Place one pointer at each end of the array. If the two elements sum to less than t, the left pointer must move right, since every sum involving the current left element is too small; if they sum to more than t, the right pointer must move left, by the symmetric argument.

Two-Sum(A, t):
  i, j = 1, n
  while i < j:
    if A[i] + A[j] = t: return (i, j)
    if A[i] + A[j] < t: i += 1
    else:               j -= 1
  return nothing

Running time. Each iteration moves one pointer one step toward the other. The pointers begin n − 1 apart, so there are at most n iterations, each of constant cost, and the running time is O(n).

Correctness. There are two things to show. If the algorithm returns a pair, that pair sums to t, because the algorithm returns only upon finding such a pair. Conversely, if a solution exists, the algorithm finds one. The reason is that a solution, if one exists, always lies within A[i:j]. This is true initially, when the range is the whole array. When A[i] + A[j] > t, the index j cannot belong to any solution with an index at or after i, because the array is sorted and every such sum is at least A[i] + A[j]; so the algorithm may discard j without losing the solution. The case A[i] + A[j] < t is symmetric. Since the range always contains a solution and shrinks by one each iteration, the loop must find the solution before the range becomes empty.

2.4 Binary search

Given a sorted array A and a target t, we wish to find an index m with A[m] = t or report that none exists. A linear scan takes O(n) time. Because A is sorted, comparing t with the middle element tells us which half of the array could contain t, and repeating this halves the range each time.

Binary-Search(A, t):
  i, j = 1, n
  while i <= j:
    m = (i + j) / 2        # rounded down
    if A[m] = t: return m
    if A[m] < t: i = m + 1
    else:        j = m - 1
  return nothing

The length of the range j − i + 1 is halved at each iteration, so after about log₂ n iterations the range is empty; each iteration costs O(1), and the running time is O(log n). Correctness follows the same pattern as Two-Sum: if t is present it always lies within A[i:j], because when A[m] < t nothing at or before m can equal t, and symmetrically when A[m] > t.

2.5 Selection sort

Selection sort builds the sorted array from left to right. In round i it finds the smallest element among positions i through n and swaps it into position i.

Selection-Sort(A):
  for i = 1, ..., n:
    m = i
    for j = i+1, ..., n:
      if A[j] < A[m]: m = j
    swap A[i], A[m]

On the input [3, 1, 4, 2] the array becomes [1, 3, 4, 2] after the first round, [1, 2, 4, 3] after the second, and [1, 2, 3, 4] after the third. The invariant is that after round i the first i positions hold the i smallest elements in sorted order. There are n rounds, each scanning up to n elements, so the running time is O(n²).

2.6 Merge sort

Merge sort is an example of divide and conquer: split the array into two halves, sort each half recursively, and combine the two sorted halves. Combining, or merging, is done with two pointers, one at the front of each half; at each step the smaller of the two front elements is moved to the output.

Merge-Sort(A):
  if n = 1: return A
  L = Merge-Sort(A[1 : n/2])
  R = Merge-Sort(A[n/2 + 1 : n])
  return merge(L, R)

For example, [4, 8, 1, 3, 2, 6, 5, 7] is split into [4, 8, 1, 3] and [2, 6, 5, 7], which sort recursively to [1, 3, 4, 8] and [2, 5, 6, 7], and merging produces [1, 2, 3, 4, 5, 6, 7, 8]. Merging two halves of total length n takes O(n) time, since each step moves one element. If T(n) denotes the running time on n elements, then T(n) = 2T(n/2) + O(n), and the solution of this recurrence is O(n log n). Solving recurrences is not part of this course; it suffices to know that merge sort runs in O(n log n) time.

2.7 The container problem

Let A be an array of n positive integers, thought of as the heights of vertical bars at positions 1 through n. Choosing two bars i < j forms a container that holds (j − i) · min(A[i], A[j]) units of water. We wish to find the pair holding the most water in O(n) time. (This problem is PS 1.4 and appeared as Problem 2 of the practice midterm.)

Two pointers again suffice, this time with a different rule for which pointer to move.

ALG(A):
  i, j = 1, n
  best = (1, n)
  while i < j:
    if area(i, j) > area(best): best = (i, j)
    if A[i] <= A[j]: i += 1
    else:            j -= 1
  return best

Correctness. Suppose A[i] ≤ A[j] at some iteration. Any pair (i, j′) with j′ < j is narrower than (i, j) and no taller, since its height is at most A[i]; hence no such pair holds more water than (i, j). Therefore the best container using bar i has already been examined, and moving i to the right cannot lose the optimum. The case A[j] < A[i] is symmetric. Since the optimal pair is never discarded before being examined, it is recorded in best. Running time. The pointers meet after at most n steps of constant cost, so O(n).

2.8 Worked problems from Problem Set 1

ALG(A):
  B = [0]*n
  for i = 1, ..., n+1:
    if B[A[i]] = 1: return A[i]
    B[A[i]] = 1

ALG(A):
  i, j, k = 1, n, n
  B = [0]*n
  while i <= j:
    if A[i]^2 >= A[j]^2: B[k] = A[i]^2; i += 1
    else:                B[k] = A[j]^2; j -= 1
    k -= 1
  return B

ALG(A, B):
  sort A
  C = []
  for b in B:
    if Binary-Search(A, b) succeeds: add b to C
  return C

ALG(A):
  sort A
  diff = ∞
  for i = 2, ..., n:
    diff = min(diff, A[i] - A[i-1])
  return diff

Exercises

Ch 33. Graphs and breadth-first search

A graph is a set of vertices together with a set of edges joining pairs of them. Graphs model road networks, social networks, course prerequisites, and much else, and the algorithms of this chapter and the next are the basic tools for working with them.

3.1 Representing graphs

Throughout, a graph has n vertices labelled 1 through n and m edges. In an undirected graph an edge is an unordered pair {u, v}; in a directed graph an edge is an ordered pair (u, v), drawn as an arrow from u to v. In a directed graph the out-neighbors of u are the vertices v with (u, v) an edge, and the out-degree of u is the number of them.

There are two standard ways to store a graph in memory. An adjacency matrix is an n × n table with G[u][v] = 1 when (u, v) is an edge and 0 otherwise. Testing whether a given pair is an edge takes O(1) time, but listing the out-neighbors of u takes O(n) time regardless of how many there are, and the matrix occupies n² cells even for a sparse graph. An adjacency list stores, for each vertex u, the list G[u] of its out-neighbors. For example, G = [[2, 3, 4], [1], [4, 2], []] describes a directed graph in which 1 has edges to 2, 3, and 4; vertex 2 has an edge to 1; vertex 3 has edges to 4 and 2; and vertex 4 has no outgoing edges. Listing the out-neighbors of u takes O(out-deg(u)) time, and testing whether (u, v) is an edge means scanning G[u], which also takes O(out-deg(u)) time.

3.2 Breadth-first search

The distance from a vertex s to a vertex v is the smallest number of edges on any path from s to v, or ∞ if no path exists. Breadth-first search, or BFS, computes the distance from a given start vertex s to every vertex. It does so by exploring the graph in layers: first the vertices at distance 1 from s, then those at distance 2, and so on. A first-in, first-out queue produces exactly this order.

BFS(G, s):
  d = [∞]*n; d[s] = 0
  Q = queue containing s
  while Q is not empty:
    u = dequeue from Q
    for v in G[u]:
      if d[v] = ∞:
        d[v] = d[u] + 1
        add v to Q
  return d

A vertex is added to the queue the first time it is seen, and its distance is set at that moment to one more than the distance of the vertex from which it was seen. Because the queue processes vertices in order of increasing distance, the first vertex to see v is always one at minimum distance, and so d[v] is set correctly. When tracing BFS by hand, scan each adjacency list in the order written, and when two vertices could be processed in either order, take the one with the smaller label; this convention makes the result of every trace unique.

Running time. Each vertex enters the queue at most once, and processing a vertex u consists of one scan of G[u]. Summing over all vertices, the scans cost O(m) and the dequeues cost O(n), for a total of O(m + n). One could instead bound each iteration by O(n) and conclude O(n²); this is correct but loses the credit that the sharper analysis earns.

3.3 Recovering shortest paths

BFS as written reports distances but not the paths that achieve them. To recover paths, record for each vertex the vertex from which it was first seen: when d[v] is set from u, also set p[v] = u. The array p is called the parent array, and the edges (p[v], v) form the BFS tree. The shortest path from s to any reachable v is obtained by starting at v, repeatedly moving to p[v] until s is reached, and reversing the resulting list. Since each step decreases the distance by one, the walk back takes at most n steps.

In the graph above, BFS from s = 1 gives d = [0, 1, 2, 2] and p = [–, 1, 2, 2]. The path to vertex 4 is recovered as 4, p[4] = 2, p[2] = 1, which reversed is 1, 2, 4.

3.4 Worked problems from Problem Set 2

ALG(G):
  diam = 0
  for each vertex u:
    d = BFS(G, u)
    diam = max(diam, max(d))
  return diam

ALG(G):
  c = [0]*n; k = 1
  for u = 1, ..., n:
    if c[u] = 0:
      run BFS(G, u), setting c[v] = k for every vertex v it reaches
      k += 1
  return c

ALG(G):
  c = [∞]*n; c[1] = 0
  Q = queue containing 1
  while Q is not empty:
    u = dequeue from Q
    for v in G[u]:
      if c[v] = ∞:         c[v] = 1 - c[u]; add v to Q
      else if c[v] = c[u]: return nothing
  return c

Exercises

Ch 44. Depth-first search and its applications

Depth-first search explores a graph by following edges as far as possible before backing up. A single depth-first search, suitably instrumented with timestamps, answers three questions about a directed graph: whether it contains a cycle, how to order its vertices so that every edge points forward, and how each edge relates to the search tree. These applications are the subject of this chapter.

4.1 The algorithm and its timestamps

The heart of depth-first search is the recursive procedure Explore, which visits a vertex and then recursively explores each of its unvisited out-neighbors in order. A global counter t, starting at 1, stamps each vertex twice: with its pre value when it is first visited, and with its post value when Explore finishes with it. The procedure DFS calls Explore from each vertex in label order that has not yet been visited, so that every vertex is stamped even when the graph is not connected.

Explore(G, u):
  pre[u] = t; t += 1
  for v in G[u]:
    if pre[v] = ∞:
      Explore(G, v)
  post[u] = t; t += 1

DFS(G):
  pre, post, t = [∞]*n, [∞]*n, 1
  for u = 1, ..., n:
    if pre[u] = ∞:
      Explore(G, u)
  return pre, post

Each adjacency list is scanned exactly once, during the single call to Explore on its vertex, so DFS runs in O(m + n) time.

Example. Let G = [[2, 3], [3, 4], [], [1, 3]]. Explore(1) stamps pre[1] = 1 and, finding 2 unvisited, calls Explore(2), which stamps pre[2] = 2. The first out-neighbor of 2 is 3, so Explore(3) stamps pre[3] = 3; vertex 3 has no out-neighbors, so post[3] = 4. Returning to 2, the next out-neighbor 4 is unvisited, so Explore(4) stamps pre[4] = 5; both out-neighbors of 4 have been visited, so post[4] = 6. Returning to 2 gives post[2] = 7, and returning to 1, whose remaining out-neighbor 3 is visited, gives post[1] = 8. Thus pre = [1, 2, 3, 5] and post = [8, 7, 4, 6].

4.2 Classification of edges

The edges along which Explore is called, here (1,2), (2,3), and (2,4), form the DFS tree (or forest). Every other edge falls into one of three classes according to where its head lies relative to its tail in that tree.

In the example, (1,3) is a forward edge, (4,1) is a back edge, and (4,3) is a cross edge. The classification can be read directly from the timestamps, without drawing the tree. Because Explore(v) begins after Explore(u) begins and ends before it ends whenever v is a descendant of u, the interval [pre[v], post[v]] is nested inside [pre[u], post[u]] for tree and forward edges; for a back edge the nesting is reversed; and for a cross edge the interval of v lies entirely before that of u.

The fourth conceivable pattern, in which u finishes before v begins, cannot occur for an edge (u, v), since Explore(u) would have visited v. Tree and forward edges share a pattern; they are distinguished by whether Explore(v) was actually called from u, which is evident in a hand trace.

4.3 Detecting cycles

Proof. If (u, v) is a back edge, then v is an ancestor of u, so the tree path from v down to u followed by the edge (u, v) is a cycle. Conversely, suppose the graph contains a cycle, and let v be the first vertex of the cycle that the search visits. Every other vertex of the cycle is reachable from v along the cycle through vertices not yet visited, so all of them become descendants of v before Explore(v) finishes. In particular the vertex u preceding v on the cycle is a descendant of v, and the edge (u, v) is a back edge. ∎

The theorem yields an algorithm that returns a cycle when one exists.

Find-Cycle(G):
  run DFS(G)
  for each edge (u, v):
    if pre[v] < pre[u] < post[u] < post[v]:
      return the tree path from v to u followed by (u, v)
  return nothing

The search costs O(m + n), the test costs O(1) per edge, and writing out the path costs O(n), so the running time is O(m + n).

4.4 Topological ordering

A directed acyclic graph, or DAG, is a directed graph with no cycles. A topological ordering of a DAG is an arrangement of its vertices in a line such that every edge points from left to right. If the vertices are courses and the edges are prerequisites, a topological ordering is a sequence in which the courses can be taken.

The DAG above has several topological orderings, among them 4, 2, 3, 1 and 4, 3, 2, 1. In general a DAG may have many; some have exactly one.

Proof. Let (u, v) be an edge. If Explore(u) is called before Explore(v), then v is either visited from u or is already being explored as a descendant of u when u examines it; either way Explore(u) cannot finish until Explore(v) has finished, so post[u] > post[v]. If Explore(v) is called before Explore(u), then since the graph has no cycle there is no path from v to u, so Explore(v) finishes without ever reaching u, and post[v] < pre[u] < post[u]. In both cases post[u] > post[v]. ∎

Topological-Sort(G):
  R = []
  run DFS(G), and each time a vertex receives its post value, insert it at the front of R
  return R

The running time is that of DFS, O(m + n).

A great deal follows from examining consecutive vertices in a topological ordering T. If every consecutive pair (T[i], T[i+1]) is an edge, then T is a path through all the vertices, and it is the only topological ordering, since the path fixes the relative order of every pair. If some consecutive pair is not an edge, then those two vertices cannot reach one another, and exchanging them produces a second topological ordering. Three of the problems in this chapter and one on the practice midterm are instances of this observation.

4.5 Strongly connected components

In a directed graph, two vertices are strongly connected if each can reach the other. A strongly connected component is a maximal set of mutually reachable vertices, and every directed graph partitions into such components. They can be labelled in O(m + n) time as follows: reverse every edge to obtain G^R, run DFS on G^R, and then, taking the vertices in decreasing order of post value, run BFS in the original graph from each vertex not yet labelled, giving everything it reaches a new label.

In the graph above the components are {1, 2, 3}, {4}, and {5}, and the algorithm labels them c = [3, 3, 3, 2, 1]. This algorithm is not among those that may be called by name on the exam and no problem set uses it, so it is the least important topic of the chapter.

4.6 Worked problems from Problem Set 2

ALG(G):
  T = Topological-Sort(G)
  for i = 1, ..., n-1:
    if T[i+1] is not in G[T[i]]:
      return (T[i], T[i+1])
  return nothing

ALG(G):
  T = Topological-Sort(G)
  for i = 1, ..., n-1:
    if T[i+1] is not in G[T[i]]: return True
  return False

Exercises

Ch 55. Greedy algorithms

A greedy algorithm builds a solution by a sequence of choices, each made to look best at the moment it is made and never reconsidered. Chapter 1 showed that such a rule may or may not be optimal. This chapter presents several greedy algorithms that are optimal, and a single method, the exchange argument, by which each is proved so.

5.1 The exchange argument

The exchange argument establishes that a greedy algorithm's output ALG is optimal by comparing it with an optimal solution OPT and showing that OPT can be transformed into ALG without ever getting worse. It proceeds in three steps.

Written proofs should follow these steps in order and state explicitly what is exchanged for what. The remainder of the chapter consists of examples.

5.2 The k largest elements

Given an array A of n distinct integers and an integer k ≤ n, we wish to choose k elements with the largest possible sum. The greedy algorithm sorts A in decreasing order and returns the first k elements, in O(n log n) time.

Theorem 5.1. The k largest elements of A have the maximum sum among all k-element subsets.

Proof. Suppose OPT is a k-element subset other than the k largest. Then OPT omits some element A[i] among the k largest and, having k elements, includes some element A[j] that is not among them, so A[i] > A[j]. Let OPT′ be OPT with A[j] removed and A[i] added. OPT′ has k elements and its sum exceeds that of OPT by A[i] − A[j] > 0, contradicting the optimality of OPT. ∎

5.3 Scheduling to minimize total waiting time

Suppose n jobs with processing times A[1], …, A[n] are to be run one after another on a single machine. The waiting time of a job is the total processing time of the jobs run before it, and we wish to order the jobs so that the sum of the waiting times is as small as possible. With processing times 4, 1, 2, the order 4, 1, 2 gives waiting times 0, 4, 5 with sum 9, whereas the order 1, 2, 4 gives 0, 1, 3 with sum 4.

The greedy algorithm runs the shortest job first, that is, sorts the jobs by increasing processing time, in O(n log n) time.

Theorem 5.2. Ordering the jobs by increasing processing time minimizes the total waiting time.

Proof. Suppose OPT is an optimal order that is not sorted. Then somewhere in OPT a job i is immediately followed by a job j with A[i] > A[j]. Let OPT′ be OPT with these two jobs exchanged. Jobs before the pair and jobs after the pair have the same waiting times as before. Job j now waits A[i] less, and job i waits A[j] more, so the total changes by A[j] − A[i] < 0. Thus OPT′ is strictly better than OPT, a contradiction. ∎

5.4 Minimum spanning trees

Let G be a connected undirected graph in which every edge e has a weight w(e), and assume the weights are distinct. A spanning tree of G is a set of n − 1 edges that connects all n vertices; equivalently, a subgraph that is connected and contains no cycle. The weight of a spanning tree is the sum of its edge weights, and a minimum spanning tree (MST) is a spanning tree of least weight. When the weights are distinct the MST is unique, so we may speak of the MST. The problem is to find it.

A cut is a partition of the vertices into a set S and its complement; an edge crosses the cut if it has one endpoint in S and one outside. The three algorithms of this section rest on two structural facts.

Proof of the cut property. Let e be the lightest edge crossing a cut S, and suppose e is not in the MST T. Adding e to T creates exactly one cycle, since T is a tree. This cycle crosses from S to its complement along e and must return along some other edge f, which lies in T and crosses the cut. Because e is the lightest crossing edge, w(e) < w(f). Then T + e − f is a spanning tree, since removing f breaks the only cycle without disconnecting anything, and its weight is less than that of T. This contradicts the minimality of T. ∎

Proof of the cycle property. Let f be the heaviest edge on a cycle C, and suppose f is in the MST T. Removing f from T splits it into two pieces, which define a cut. The cycle C crosses this cut along f and therefore crosses back along some other edge e of C, and w(e) < w(f) since f is the heaviest edge of C. Then T − f + e is a spanning tree of smaller weight than T, a contradiction. ∎

Prim's algorithm

Prim's algorithm grows a single tree outward from vertex 1. At each step it adds the lightest edge that has exactly one endpoint in the tree so far.

Prim(G):
  S = {1}; F = []                  # S is stored as a 0/1 array of length n
  repeat n-1 times:
    e = the lightest edge with exactly one endpoint in S
    add e to F and its outside endpoint to S
  return F

Each added edge is the lightest edge crossing the cut S and so lies in the MST by the cut property; after n − 1 additions F is the entire MST. Each of the n − 1 rounds scans all m edges, so the running time is O(mn).

In the graph above, the edges leaving {1} have weights 5, 4, and 3, so {1,3} is added first. From {1,3} the lightest leaving edge is {3,4} of weight 1, and from {1,3,4} it is {2,3} of weight 2. The MST has weight 6.

Kruskal's algorithm

Kruskal's algorithm considers the edges in increasing order of weight and keeps each edge unless it would form a cycle with the edges already kept.

Kruskal(G):
  sort E by increasing weight
  F = []
  for each edge e = {u, v} in this order:
    if u cannot reach v using the edges of F:      # BFS on (V, F)
      add e to F
  return F

Correctness. When e = {u, v} is added, let S be the set of vertices reachable from u using the edges of F at that moment. No edge crossing S has yet been kept, and every lighter edge has already been considered and either does not cross S or was rejected; so e is the lightest edge crossing S and belongs to the MST by the cut property. Moreover F ends as a spanning tree: if some cut had no kept edge crossing it, then any edge crossing that cut would have been kept when considered. Running time. Sorting costs O(m log n). Each of the m reachability tests is a BFS on the forest (V, F), which has at most n − 1 edges and so costs O(n). The total is O(m log n + mn) = O(mn).

Reverse-Delete

Reverse-Delete runs Kruskal's algorithm backward: it considers edges from heaviest to lightest and deletes each one unless doing so would disconnect the graph.

Reverse-Delete(G):
  sort E by decreasing weight
  for each edge e in this order:
    if G - e is connected:                        # BFS
      remove e from G
  return G

Correctness. An edge whose removal leaves the graph connected lies on a cycle, and since edges are considered heaviest first, it is the heaviest edge on that cycle; by the cycle property it is not in the MST, so the MST survives every deletion. At the end no cycle remains, for the heaviest edge of any surviving cycle could have been removed without disconnecting the graph. A connected graph without cycles that contains the MST is the MST. Running time. Each of the m connectivity tests is a BFS costing O(m), for a total of O(m²).

A worked example

In increasing order the edges are {1,2}:1, {4,5}:2, {3,6}:3, {1,4}:4, {1,5}:5, {2,5}:6, {2,3}:7, {2,6}:8, {5,6}:9. Kruskal's algorithm keeps the first four; the kept edges then connect {1, 2, 4, 5} and, separately, {3, 6}. It rejects {1,5} and {2,5}, whose endpoints are already connected, keeps {2,3}, which joins the two groups, and rejects {2,6} and {5,6}. The MST has weight 17. Prim's algorithm from vertex 1 adds {1,2}, {1,4}, {4,5}, {2,3}, and {3,6} in that order and produces the same tree.

A data structure called Union-Find performs Kruskal's cycle test faster than BFS does. It was mentioned in lecture and is not examined.

5.5 Selecting compatible intervals

An interval [s, t] with s < t represents an event beginning at time s and ending at time t. Two intervals conflict if they share a point, endpoints included. Given n intervals, we wish to select as many as possible, no two of which conflict. This is the event-selection problem of Chapter 1, and Rule D there is the algorithm.

Select-Intervals(A):
  sort A by end time
  S = []
  for each interval e in this order:
    if e begins after the last interval in S ends:
      add e to S
  return S

An interval conflicts with some member of S exactly when it conflicts with the last member, because the members of S were added in order of end time and the last one ends latest. The test therefore costs O(1), and the running time is that of sorting, O(n log n).

Theorem 5.5. Select-Intervals returns a maximum set of pairwise compatible intervals.

Proof. List the intervals of ALG and of an optimal solution OPT in order of end time, and suppose they differ. Let i be the first position at which ALG[i] ≠ OPT[i]. The intervals ALG[1], …, ALG[i−1] and OPT[1], …, OPT[i−1] coincide, and both ALG[i] and OPT[i] are compatible with them. The algorithm chose ALG[i] as the earliest-ending interval compatible with those choices, so OPT[i] ends no earlier than ALG[i]. Let OPT′ be OPT with OPT[i] replaced by ALG[i]. The new interval ends no later than the one it replaces, so it does not conflict with OPT[i+1] or anything after it, and it is compatible with the earlier intervals; hence OPT′ is feasible, has the same size as OPT, and agrees with ALG in its first i positions. Repeating the exchange yields an optimal solution identical to ALG, so ALG is optimal. ∎

5.6 The fractional knapsack problem

We are given n items, the i-th having value v[i] and weight w[i], and a knapsack of capacity B. We may take any fraction x[i] between 0 and 1 of item i, receiving value x[i]·v[i] and using weight x[i]·w[i]. The goal is to maximize the total value subject to the total weight not exceeding B.

The greedy algorithm considers items in decreasing order of value per unit weight and takes as much of each as fits.

Fractional-Knapsack(v, w, B):
  sort the items by v[i]/w[i] in decreasing order
  x = [0]*n
  for each item i in this order:
    x[i] = min(1, remaining capacity / w[i])
  return x

At most one item is taken fractionally, namely the one that fills the knapsack. The running time is O(n log n) for sorting plus O(n) for the pass.

Example. Let v = [4, 1, 2], w = [5, 1, 4], and B = 7. The ratios are 0.8, 1, and 0.5, so the items are considered in the order 2, 1, 3. All of item 2 is taken (weight 1), then all of item 1 (weight 6 in total), then one quarter of item 3 to fill the remaining unit. The solution is x = [1, 1, 1/4] with value 4 + 1 + 0.5 = 5.5.

Theorem 5.6. Fractional-Knapsack returns a solution of maximum value.

Proof. Number the items so that v[1]/w[1] ≥ v[2]/w[2] ≥ ⋯. Suppose an optimal solution OPT has greater value than ALG, and let i be the first item on which they differ. The algorithm took as much of item i as would fit, so OPT takes less: OPT[i] < ALG[i]. Since OPT has at least as much value as ALG yet takes less of the early items, it must take a positive amount of some later item j > i, whose ratio is no larger. Form OPT′ by increasing x[i] by a small amount ε and decreasing x[j] by ε·w[i]/w[j]. The total weight is unchanged, so OPT′ is feasible for ε small enough. The value changes by ε·v[i] − ε·(w[i]/w[j])·v[j] = ε·w[i]·(v[i]/w[i] − v[j]/w[j]) ≥ 0. Thus OPT′ is at least as valuable as OPT and agrees with ALG on more of item i. Repeating the exchange transforms OPT into ALG without decreasing value, so ALG is optimal. ∎

Exercises

6. The practice midterm, with solutions

This chapter works the official practice midterm, which carries 25 points and allows 65 minutes. Attempt each problem before revealing its solution.

ALG(A):
  i, j = 1, n; best = (1, n)
  while i < j:
    if area(i, j) > area(best): best = (i, j)
    if A[i] <= A[j]: i += 1
    else:            j -= 1
  return best

ALG(G):
  c = [0]*n; k = 1
  for u = 1, ..., n:
    if c[u] = 0:
      run BFS(G, u), setting c[v] = k for every vertex v reached
      k += 1
  return c

ALG(G):
  R = Topological-Sort(G)
  for i = 1, ..., n-1:
    if R[i+1] is not in G[R[i]]: return nothing
  return R

7. A second practice examination

The following examination follows the format of the midterm. Allow 65 minutes with the solutions hidden. For each design problem, write the algorithm, the correctness argument, and the running-time analysis as three labelled parts.

ALG(A, t):
  i, j = 1, 2
  while j <= n:
    if A[j] - A[i] = t: return (i, j)
    if A[j] - A[i] < t: j += 1
    else:                i += 1
    if i = j: j += 1
  return nothing

ALG(G, s, t):
  run BFS(G, s), recording p[v] = u whenever d[v] is set from u
  if d[t] = ∞: return nothing
  P = [t]
  while the last vertex of P is not s: append p[last vertex of P]
  reverse P and return it

ALG(A):
  sort A by end time
  P = []; last = -∞
  for each [s, t] in this order:
    if s > last:
      add t to P; last = t
  return P

8. Summary

This chapter collects the definitions, algorithms, and facts of the book in the form of a single reference page.