ECS122A-Final-Prep

Final Review Vids:

• OLD Review Part1

• OLD Review Part2

• Review 1

• Review 2

• Review 3

• Review 4

---

New Vid 1

1. Induction
2. Asymptotic Analysis
3. Divide and Conquer
4. Greedy Algos
5. Dynamic Programming
6. Graph
   1. Graph representation - Adj. List/Mat
   2. BFS/DFS
   3. Bellman/Dijkstra
   4. Prims
   5. Kruskal
   6. All pairs shortest paths
7. Proofs: Greedy choice and suboptimality

Q0) Analyze code runtime (algo analysis)
Q1) Implement DFS/BFS on sample graph, know and analyze the run time
Q2) Implement Bellman/Dijkstra on sample graph, know and analyze the run time
Implement Prims on sample graph, know and analyze the run-time off
Q3) Algorithm Design:

• Brute Force
• Divide and Conquer
• Greedy
• Dynamic Programming
• Graph Algo Design

Graph Traversal:

• T = Tree Edge = Encounter new vertex (grey to white)
• B = Back Edge = From descendant to ancestor (grey to grey)
• F = Forward Ede = From ancestor to descendant (grey to black)
• C = Cross Edge = Any other edges (between tree and subtrees) grey to black)