Final Review for CMPS 6610/4610, Fall 2020

Relevant Material:

  1. Amortized Analysis
    • Aggregate analysis, accounting method, potential method
    • Dynamic tables, binary counter
    • Union-Find:
      • Union-find data structure definition (operations)
      • Union-find: List implementation, tree implemention
      • Union by weight/rank, path compression
      • Ackermann function, inverse Ackermann function
    • Fibonacci Heaps:
      • Fibonacci heap definition
      • Operations: Insert, extract_min, decrease_key
      • Bounded rank (= max # children), not height
      • Analysis using potential function
    • Relevant Material:
    • Practice problems from CLRS:
      • Amortized Analysis:
        • page 456: 17.1-1-3
        • page 458: 17.2-1-3
        • page 462: all
      • Union-Find:
        • page 564: all
        • page 567: 21.2-1,2,3,4
        • page 572: 21.3-12,3,4
      • Fibonacci Heaps:
        • page 518: 19.2-1
        • page 522: 19.3-1,2
        • page 526: 19.4-1,2
        • page 529: 19-3

  2. Graphs
    • Representation of Graphs:
      • Adjacency matrix
      • Adjacency lists
      • Handshaking lemma
    • Graph Traversal:
      • Breadth First Search, runtime O(|V|+|E|)
      • Depth First Search, runtime O(|V|+|E|)
    • Minimum Spanning Tree (MST)
      • Prim:
        • Runtime: Θ(|V|)·T_EXTRACT-MIN + Θ(|E|)·T_DECREASE-KEY
        • Runtimes using different variants of graph representations and priority queues (linked list, min-heap or array)
        • With Fibonacci heaps the runtime is O(|E| + |V|log|V|)
      • Kruskal:
        • Runtime: O(|E|log|E| + |E|α(|V|))=O(|E|log|E|)=O(|E|log|V|) which comes from sorting all the edges.
      • Boruvka:
        • Runtime: O(|E|log|V|). Multiple iterations of adding all safe edges (connecting multiple connected components at the same time). At most log |V| iterations.
    • Single Source Shortest Paths
      • Dijkstra: Works only for non-negative edge weights.
        • Runtime: Θ(|V|)·T_EXTRACT-MIN + Θ(|E|)·T_DECREASE-KEY
        • Runtimes using different variants of graph representations and priority queues; Fibonacci heaps
        • With Fibonacci heaps the runtime is O(|E| + |V|log|V|)
      • Bellman-Ford: Works for any edge weights and can detect negative weight cycles.
        • Runtime: O(|V||E|)
        • For a DAG, run Topological Sort and then one round of Bellman-Ford. Runtime O(|V|+|E|)
    • All Pairs Shortest Paths
      • Floyd-Warshall:
        • Runtime: O(|V|^3) [when graph is given in adjacency matrix]
        • Transitive closure, runtime: O(|V|^3).
      • Dijkstra:
        • Run single source Dijkstra once for each vertex as the source.
        • Runtime O(|V||E| + |V|^2 log |V|)
      • Bellman-Ford: Run single source Bellman-Ford once for each vertex as the source.
        • Runtime: O(|V|^2|E|)
      • Johnson:
        • Reweigh the graph edges. Use vertex weights determined by shortest path computation from new super-source (using Bellman-Ford).
        • Run Dijkstra's algorithm on the reweighted graph for each vertex as the source. Afterwards, adjust the computed shortest-path weights by subtracting the appropriate vertex weights.
        • Runtime: O(|V||E| + |V|^2 log |V|)
    • Relevant Material:
    • Practice problems from CLRS:
        1. Representation of Graphs, and Graph Traversal:
          • page 592: 22.1-12,3,4,5,6
          • page 601: 22.2-1,2,3,4,5,9
          • page 610: 22.3-2,7,8,11
          • page 623: 22-3
        2. Minimum Spanning Tree:
          • page 629: 23.1-1,5,6,10
          • page 637: 23.2-2,3,8
          • page 638: 23-1
        3. Shortest Paths:
          • page 654: 24.1-1,3
          • page 658: 24.2-4
          • page 662: 24.3-1,2,3
          • page 676: 24.5-1,2
          • page 699: 25.2-1,3
          • page 704: 25.3-1,2,3,5

  3. Network Flow
    • Definitions of flow network, flow, cuts
    • Definitions of residual network, augmenting path. Edges with zero residual capacity do not exist in the residual network (alternatively, an augmenting path over them would have capacity zero).
    • Max-flow min-cut theorem
    • Ford-Fulkerson:
      • Chooses an arbitrary graph in the residual network to augment
      • Runtime: O(|E| |f*|)
    • Edmonds-Karp:
      • Chooses a shortest augmenting path in the residual network. The length of the path is measured by the number of edges.
      • Runtime: O(|V| |E|^2)
    • Applications of flow networks: Maximum bipartite matching, image segmentation
    • Relevant Material:
    • Practice problems from CLRS:
      • page 649: 26.1-1,6
      • page 663: 26.2-2,3,4,10
      • page 668: 26.3-1,2,3

  4. More Randomized Algorithms
  5. P and NP
    • Definition of P, NP, NP-hard, NP-complete, Co-NP
    • Reductions
    • NP-complete problems (SAT, Clique, TSP, Hamiltonian Cycle, Vertex Cover, Independent Set)
    • Approximation algorithms (Vertex Cover, TSP, Max-3SAT)
    • Relevant Material:
    • Practice problems from CLRS:
      • page 1060: 34.1-1
      • page 1065: 34.2-1,2,3,6,7,8,9,10
      • page 1100: 34.5-1,5,6,7
      • page 1111: 35.1-1,2,4
      • page 1122: 35.3-2