这门课程所使用的教材是康奈尔的 Algorithm Design 和 MIT 的 Introduction to Algorithms，本份笔记直接沿用书本中对变量及名词的定义，在此没有对它们进行特殊解释。

Lecture 1

1. we say f(n) = O(g(n)) if g(n) eventually dominates f(n). Formally: there exists a constant c such that for all sufficiently large n: f(n) ≤ c * g(n). The definition for Ω is similar to the definition for O. If f(n) = O(g(n)) and f(n) = Ω(g(n)), then f(n) = Θ(g(n)).
   • (1/3)^n + 100 = O(1) is True.
2. The handshaking theorem: 2 * E = Σx∈V deg(x) (undirected graph)
3. Adjacency List Representation is used for representation of the sparse (E = O(V)) graphs; Adjacency Matrix Representation is used for representation of the dense (E = Ω(V^2)) graphs.
   • Maximally sparse connected graph: tree;
   • Maximally dense connected graph: complete graph Kn.
4. Linear time topological sort for DAG algorithm:
   • Select a vertex;
   • Run DFS and return vertices that has no undiscovered leaving edges;
   • May run DFS several times.
5. Is strongly connected graphs:
   • Select a vertex;
   • Run DFS, if some vertices are not reachable, stop;
   • Construct GT and run DFS again, if some vertices are not reachable, stop.
6. Euler’s Formula: If G is a connected planar graph, then V – E + F = 2 (proof is by induction).
7. 4 Color Theorem: Any simple planar graph can be colored with less than or equal to 4 colors.
8. A graph is bipartite if the vertices can be partitioned into two disjoint sets. A subset of edges is a matching if no two edges have a common vertex.

Lecture 2

1. Complete Binary Tree: completely filled, except the bottom level that is filled from left to right; and a binary heap is a complete binary tree which satisfies the heap ordering property.
2. In heap, consider the k-th element of the array:
   • Its left child is located at 2 * k index;
   • Its right child is located at 2 * k + 1 index;
   • Its parent is located at k / 2 index.
3. Heap operations:
   • Insert: insert at the end, then percolate it up by swapping positions with the parent, if it’s necessary;
   • deleteMin: move the last element of the heap to the root and then restore the heap property by percolating down; So the complexity for heap sort is O(n * log n)
   • decreaseKey: restore a heap property by percolating up this item;
   • buildHeap: by insertion: O(n * log n); heapify: O(n).
4. Binomial heap operations:
   • merge: make the larger root to be the child of the smaller root. Complexity: O(log n);
   • deleteMin: find the binomial tree that contains the min; delete the root and move subtrees to top list; then merge the binomial trees. Complexity: O(log n);
   • insert: merge trees.
5. Amortized analysis gives the average performance (over time) of each operation in the worst case.
   • The amortized cost of insertion of Binomial heap is constant O(2).
6. Complexities:

Lecture 3

1. Scheduling Problem: early finish time first. Complexity: O(n * log n).
2. Minimum Spanning Tree:
   • Kruskal’s Algorithm: Continue choosing the minimum weight edge that will not create a cycle until all vertices are connected.
     • Sorting edges: O(E * log E);
     • Cycle detection: O(V);
     • Total: O(E * log E + E * V).
   • Prim’s Algorithm: Start with an arbitrary vertex as a sub-tree C; Expand C by adding a vertex having the minimum weight edge of the graph having exactly one end point in C; Update distances from C to adjacent vertices; Continue doing this until all vertices are connected.
     • If we use an array to maintain vertices distance to C, then findMin / deleteMin needs O(V), and update needs O(1). Complexity: O(V ^ 2 + E);
     • If we use a heap, then findMin / deleteMin needs O(log V), and update needs O(log V). Complexity: O(V * log V + E * log V);
     • If graph is dense -> array; if graph is sparse -> heap.
   • If a connected undirected graph G = (V, E) has V + 10000 edges, we can find an MST of G in O(V) runtime.
     • True. Randomly generate a spanning tree (O(n)), for each edge in the last 10000 edges, add it to the tree, delete the max edge in the cycle (O(n)). So the total complexity should be 10000 * O(n) = O(n).
3. The Shortest Path Problem:
   • Dijkstra’s Algorithm: almost identical to Prim’s algorithm, but picks the shortest path from the source. It’s complexity is same as Prim’s Algorithm.
     • If priority queue is an array: O(V ^ 2 + E);
     • If priority queue is a heap: O(V * log V + E * log V);
     • If graph is dense (E = V ^ 2) -> array O(V ^ 2); if graph is sparse -> heap O(V * log V)

Lecture 4

1. The Master Theorem: T(n) = a * T(n / b) + f(n), where a ≥ 1 and b > 1 are constants and f(n) is a positive function, c = logb(a):
   • Case 1: if f(n) = O(n^(c-ε)), then T(n) = Θ(n ^ c); (only leaves)
   • Case 2: if f(n) = Θ(n^c * (log n) ^ k), k ≥ 0, then T(n) = Θ(n^c * (log n)^(k + 1)); (all nodes)
   • Case 3: if f(n) = Ω(n^(c+ε)), then T(n) = Θ(f(n)); (only internal nodes)
2. Closest pair of points: T(n) = 2 * T(n / 2) + O(n * log n), so the complexity should be Θ(n * (log n) ^ 2)

Lecture 5

1. Two Approaches for DP:
   • Memoization: a top-down approach;
   • Tabulation: a bottom-up approach.
2. Pseudo-Polynomial Algorithm: A numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input: T(n) = Θ(n·W).

Lecture 6

1. Basic steps for DP:
   • Define subproblems;
   • Write the recurrence relation;
   • Construct the solution in bottom-up way;
   • Compute its runtime complexity.
2. Bellman-Ford Algorithm:
   • How would you apply the Bellman-Ford algorithm to find out if a graph has a negative cycle? Run 1 more round for k = V, if the distance reduced for some point, there must be a negative cycle.
   • Complexity: O(E * V).

D[v, 0] = INFINITY for all v != s
D[s, k] = 0 for all k
for k = 1 to V-1 do
  for each v in V do
    for each neighbor w of v do
      D[v, k] = min(D[v, k - 1], c(w, v) + D[w, k - 1])

1. Floyd-Warshall Algorithm:
   • If the diagonal has negative numbers, then there must be a negative cycle.
   • How do we extract the shortest path? Every time we update D[i, j], we set P[i, j] to k. Then we recursively compute the shortest path from from i to k = P[i, j] and the path from from k = P[i, j] to j.
   • Complexity: O(V ^ 3)

D[i, j, 0] = c[i, j] for all i and j
for k = 1 ... V do
  for i = 1 ... V do
    for j = 1 ... V do
      D[i, j, k] = min (D[i, j, k - 1], D[i, k, k - 1] + D[k, j, k - 1])