This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. The course explores fundamental algorithm design techniques such as greedy, divide and conquer, dynamic programming, network flow, reduction, approximation, linear programming and randomization for efficient algorithm construction. The course describes Turing machines and explains what NP-completeness means with respect to possibilities for solving these problems efficiently.
| No. | Name | PDF file | Tags | Score |
|---|---|---|---|---|
| 1 | Homework 1 | Runtime Complexity BFS DDFS Induction Proof Graph |
100/100 | |
| 2 | Homework 2 | Greedy Algorithm |
80/80 | |
| 3 | Homework 3 | Divide-and-Conquer Dynamic Programming Master Theorem |
133/135 | |
| 4 | Homework 4 | Network Flow Reduction Ford-Fulkerson |
100/100 | |
| 5 | Homework 5 | Linear Programming NP-Completeness SAT |
100/100 | |
| 6 | Homework 6 | Linear Programming NP-Completeness Reduction Approximation |
96/100 |
| No. | Name | PDF file | Tags | Score |
|---|---|---|---|---|
| 1 | Exam 1 | Practice Material | Runtime Complexity BFS DDFS Induction Proof Graph Divide-and-Conquer Dynamic Programming Master Theorem |
62/85 |
| 2 | Exam 2 | Practice Material | Network Flow Reduction Ford-Fulkerson Linear Programming NP-Completeness SAT Independent Set Approximation |
85/100 |
-
Q&A
-
Java
-
Python