ECS 122A : Algorithm Design and Analysis
Quarter: WINTER 2018
Instructor: Zhaojun Bai
Teaching Assistant:
Nima Joharizadeh (johari at ucdavis.edu)
Kenan Nalbant (kanalbant at ucdavis.edu)
Yuan Pan (yapan at ucdavis.edu)
Course Website: ECS 122A
Discussion Schedule:
- week 1
Jan 10 | Kenan | Induction Review, Solving Linear Recurrences
- week 2
Jan 17 | Kenan | Asymptotic Analysis, Big-Oh, Big-Omega, Big-Theta, Proving bounds with limits
- week 3
Jan 24 | Kenan | Master Method, Solving recurrence relations by unrolling/by recursion trees
Jan 22 | Yuan | Asymptotic Notation, Master theorem | document_asymptotic_master.pdf
- week 4
Jan 31 | Kenan | Midterm Review, asymptotics, solving recurrence relations, D&C Algorithms
Jan 29 | Yuan | Master theorem, Divide and Conquer | master_dc.pdf
- week 5
Feb 5 | Yuan | Greedy Algorithm | document_greedy.pdf
Feb 7 | Kenan | Huffman Coding, Dynamic Programming (Fibonacci & Matrix Multiplies)
- week 6
Feb 12 | Yuan | DP | document_dynamic_programming.pdf
- week 7
Feb 19 | Yuan (holiday, no discussion)
- week 8
Feb 26 | Yuan | DFS, BFS, topological sort (some examples)
- week 9
Mar 5 | Yuan | MST(Prim's Algorithm and Kruskal's Algorithm), Shortest Path(BFS, Dijkstra, Bellman ford)
Nima
March 7th:
- A review on Graph Algorithms:
BFS, DFS- Going over HW7
- Prim and Kruskal (Greedy choice property and HW7.1)
- Prim: Starting with A and V\A, assigning keys to Vertices
- Kruskal: Starting with V sets of size one and merge sets (Going through edges in increasing order)
- There's going to be no talk about Bellman-Ford this week.
- Lecture today is going to be about two simpler versions of shortest path. We get to Bellman-Ford next week in our discussion.
- However, we are going to shortly review the SSSP problem to make the stage for Dijkstra's lecture
- Prim and Kruskal (Greedy choice property and HW7.1)
- SSSP (No proof of correctness today)
- Path relaxation property
- (Negative weight okay, but no cycles) Topological sort + Shortest path on DAG
- O(|V| + |E|) instead of O(|V||E|)
- (Cycles okay, but no negative weight) Dijkstra
- Analysis of time complexity (O(|E| lg|V|)
Week 6: Dynamic Programming, continued
- Counting Bits
- Suppose you have an n by n grid. At each step you can make a move to right and up. Count the number of paths starting from (0, 0) to (n-1, n-1) such that you would not pass the diagonal.
- Maximum Product Subarray
Week 5: Greedy algorithms and Basic Dynamic Programming
- Greedy algorithms
- An example that the greedy strategy doesn't work?
- Some discussions about HW3 (Q1 and Q2)
- Optimal subprolem
- Some basic dynamic programming
- House Robber (Easy)
- Fibonacci sequence and
Rod cutting
Week 4: Divide and conquer
- Understanding the Maximum Subarray Problem (the divide and conquer solution from lecture notes)
- Sidenote: Can we do better than the O(nlogn) divide and conquer solution?
- Open discussion on
- "O, Omega, and Theta, when to use which?"
- HW3
- Understanding the subproblems, and recognizing the benefit of the proposed observation in "Part a"
- Interactive discussions about the base case
- Study tips for a successful midterm experience
- See also the midterm review checklist.
Week 3: Master Theorem
- Some examples on different cases of master theorem (see this document from University of Western Ontario for additional practice examples)
- Open discussion on
- HW2 (examples of substitution method and master theorem)
Week 2: Mathematical Induction
- Proving via mathematical induction
- For additional practice exercises, see this excellent problem-set from University of Manitoba
Week 1: Cost function, recurrence and the Fibonacci sequence
- The Fibonacci sequence, basics of cost functions
- Climbing stairs problem