Learning materials

Final Review

On this page

How to use this document

Only contains the topics after the midterm 2 and the cross-module concepts
Self-test using this document to see what concepts are challenging to you.
The slides are the most concise and focused document you can start with.
Course supplement material website is the systematic view for tips, pitfalls.
Refer to the practice exam for the format of the exam and the types of questions.
Refer to the test exam for how the Honorlock will work.

Type of Questions

True/False (TF)
Multiple Choice (MC)
Fill in the Blank (FIB)
Matching (MAT) - match a list of items to another list of items
Short Answer/Coding (SA)

Topics

Dynamic programming

For full notes and examples, revisit Chapter 10: Dynamic Programming.

Two core components to justify dynamic programming
- Overlapping subproblems
- Optimal substructure
Other characteristics
Approach
- Top-down (memoization)
- Bottom-up (tabulation) - preferred for efficiency
Complexity depending on the problem

Graph algorithms

For full notes and examples, revisit Chapter 11: Graph Algorithms.

Concepts
Types
Graph representation
- Edge list
- Adjacency matrix
- Adjacency list
Complexity depending on representations (important)
- Find all neighbors of a vertex
- Check if two vertices are connected / or check weight
Graph traversal
- BFS - Queue ADT
- DFS - Stack ADT or recursive

Probability

Classic only - all events have equal probability
Events
- range of probability
Sample space
Principles and rules
- Complement rule
- Addition rule
- Multiplication rule
Calculation of classic probability
- Count first
- Count of specific events / total number of possible events
- Example: dice, coin, cards, balls from a bag, lottery

Randomized Algorithms

Types
- Monte Carlo - approximate algorithms to solve hard problems that are impractical to solve exactly
  - Random sampling
  - Use statistics to estimate a property of interest
- Las Vegas - exact, randomness to improve efficiency
Genetic algorithm (employs some Monte Carlo techniques)

Cross-Module Concepts

Algorithmic paradigms
- Greedy
  - Optimization problems
  - Approximate algorithms
    - Exceptions: Huffman coding, Prim’s, Krukal’s, Dijkstra’s will provide the best solution
  - Mostly $\Theta(n)$
- Backtracking
  - Often used for search or enumeration; can support decision or optimization by stopping at a witness or tracking the best candidate
  - Close to brute force with pruning
- Divide and conquer
  - Exact algorithms
  - Distinct subproblem only (in this course)
  - Recurrence relation
  - Solve recurrence using master theorem
- Dynamic programming
  - Exact algorithms
  - Key components
    - Overlapping subproblems
    - Optimal substructure
Relationship between algorithms
- Different types of problem to solve
- Exact vs approximate
- Complexity (efficiency)
  - Greedy < Divide and conquer, backtracking, dynamic programming < Brute force
Problem types and algorithms to solve them
- Search, enumeration, optimization, decision, and counting specify the requested output; they are not one-to-one matches with paradigms.
- Brute force and backtracking can implement search or enumeration, and can be adapted for decision, counting, or optimization.
- Divide and conquer, dynamic programming, greedy, branch and bound, and other paradigms apply when their structural requirements fit the problem. For example, DP may compute an optimum, a count, or a Boolean answer; branch and bound is commonly used for exact optimization.
- Enumeration can derive search, decision, counting, or optimization answers by processing all solutions, but may do more work than needed.
- Randomized algorithms are employed in may approximate algorithms
Problem perspective
- TSP
  - Optimization
  - NP-hard: prefer approximate algorithms because exact algorithms are not practical
  - Circular permutation
    - $\Theta(n!)$ brute force
  - Exact algorithms only for small number of cities
    - Brute force
    - DP
  - Approximate algorithms
    - Greedy (not covered)
    - Genetic algorithm
- Bin packing
  - Optimization
  - NP-hard: prefer approximate algorithms because exact algorithms are not practical
  - Online vs offline
  - DP is possible but greedy is usually good enough but faster
  - Greedy: First fit, best fit, next fit
    - near optimal result
  - Permutation + next fit brute force for small problem size
    - $\Theta(n!)$
- Huffman coding
  - Optimization
  - Priority Queue ADT
  - Full binary tree
  - Prefix code
  - Greedy algorithm as an exact algorithm
    - $\Theta(n)$
- Max sum subarray
  - Optimization
  - Brute force $\Theta(n^2)$
  - Divide and conquer $\Theta(n\log n)$
  - DP (Kadane’s) $\Theta(n)$
  - Know how they work on paper!
- Chain matrix multiplication
  - Different ways to parenthesize
  - Minimize the number of scalar multiplications (optimization)
  - NP-hard: prefer approximate algorithms
  - Brute force Catalan number impractical
  - Space complexity
  - DP
    - Bottom-up
    - Iterate chain length L, start index i, bisect index k $\Theta(n^3)$
- Longest common subsequence
  - Optimization
  - Brute force $\Theta(2^n)$
  - DP
    - Bottom-up
    - $\Theta(mn)$
    - (m+1)(n+1) table or 2(m+1) table (find length only)
    - backtracking to find the sequence (know how it works on a table)
- Graph: Minimal spanning tree
  - Optimization
  - Brute force: find V-1 edges out of E edges without cycle,
  - Prim’s algorithm
    - Priority Queue ADT
    - Greedy
    - Focus on vertices
    - Better for dense graph
    - Start from an arbitrary vertex and grow the tree greedily by adding the shortest edge that connects the tree to a vertex not in the tree
    - Complexity depending on graph representation and priority queue implementation
  - Krukal’s algorithm
    - Sorted array data structure
    - Disjoint set data structure to memorize the forest (unconnected trees)
    - Greedy
    - Focus on edges
    - Better for sparse graph (with less edges)
    - Better for parallel implementation
    - Adding edges in increasing order of weight without loop until all vertices are connected
    - Complexity depending on graph representation and disjoint-set implementation
  - Know how they work on paper!
- Graph: Shortest path
  - Single source shortest path (SSSP)
    - Dijkstra’s algorithm
      - Priority Queue ADT
      - Greedy
      - Close to Prim’s algorithm
      - Complexity depending on graph representation and priority queue implementation
      - Know how it works on paper!
  - All pairs shortest path (APSP)
    - Floyd-Warshall algorithm
      - DP
      - Bottom-up
      - $\Theta(n^3)$
- Estimation of Pi
  - Monte Carlo
  - Random sampling of x and y
  - Find the ratio of points inside the circle to the total number of points
  - $\pi = 4 \times ratio$
  - Know how it works on paper!