Lecture 37 NP completeness

Today, we talked about why 3SAT is NP complete. We also discussed  problems between P and NPC.

Lecture 36. More on NP-Completeness

Today, we talked about co-NP and the cook-levin theorem. Under the assumption that a polynomial time algorithm can be efficiently converted into a polynomial size circuit. We show that Circuit-Sat is NP-complete.

Lecture 35. NP Completeness

Today, we talked about the definition of P, NP and polynomial time reducible.

Homework 6

Homework 6 is out. This homework is optional.
If you do not submit it, we will take average over your first 5 homework scores.
If you submit it, we will take average over your 6 homework scores if it is better than the average of your first 5 homework scores


Hint for problem 1: use max flow to make the fair assignment. Basically we just want to assign a driver to the days he need to drive with the fairness constraint.
Hint for problem 2:The general approach is to somehow create an instance of problem B from an
instance of problem A and apply the algorithm for B on it.

Lecture 34. Applications of Max Flow

Today, we talked about the applications of max flow on the following problems
1. min cut
2. edge disjoint path
3. vertex disjoint path
4. bipartite graph matching

Lecture 33 Edmonds-Karp algorithm

Today, we talked about Edmonds-Karp algorithm for the max flow problem.

Lecture 32 Max Flow Min Cut Theorem and Ford-Fulkerson's algorithm

In this lecture, we talked about Ford Fulkerson's algorithm for finding the max flow. To show the correctness of the algorithm, we also proved the Max-Flow Min-Cut Theorem.