ECS-122A-S19-Discussion

Discussion Notes for ECS-122A "Algorithm Design and Analysis" Spring 2019 at UC Davis.

MIT License

Copyright (c) 2019 Ji Wang

Week 1

1. Mathematical Induction
2. Recursion, Stack
3. Merge Sort

---

Week 2

1. Mathematical Review: Polynomial, Exponential, Logarithms, and their Derivatives
2. Asymptotic Notation
3. Solving Recurrence Relation:
   • Substitution method
   • Master theorem

---

Week 3

1. Mathematical Review: Polynomial, Exponential, Logarithms, and their Derivatives
2. Asymptotic Notation
3. Solving Recurrence Relation:
   • Substitution method
   • Master theorem
4. Divide and Conquer: Chip Testing

---

Week 4

1. Divide and Conquer: Chip Testing
2. Divide and Conquer: Stock Investment

---

Week 5

Greedy Algorithms: Off-line Caching

---

Week 6

1. Recap: Largest Common Subsequence Problem
2. Dynamic Programming VS Divide and Conquer
3. Dynamic Programming: Image Compression

---

Week 7

1. Revisit: Edit Distance
2. Implementation in Python3: Edit Distance
3. Variant: DNA Matching

---

Week 8

1. Graph Basics
2. DFS & BFS

---

Week 9

1. Minimum Spanning Tree
2. Single-Source Shortest Paths
3. MST VS SSSP

---

Week 10

Review Homework 8

1. P, NP, NP-complete
2. How to prove a problem is NP-complete