Final Review¶
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.
Practice your ability to work on an algorithm on paper. Play with the visualization website to see how the algorithm works step by step.
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¶
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¶
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 :math:’Theta(n)`
Backtracking
Decision/Enumeration problems (can be used for optimization problems)
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
find one solution (search)
brute force
backtracking
divide and conquer
find all solutions (enumeration)
brute force
backtracking
dynamic programming
find best solution (optimization)
greedy
divide and conquer
genetic algorithm
all find all methods
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!