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.

Homework 3 distribution

Max 80
average 60.433
median 65.5

Lecture 31 Max Flow and Min Cut

Today, we finished algorithm on strongly connected component. We also defined the problem of max flow and showed that the maximum flow is always upper bounded by the minimum cut.

Lecture 30. Strongly Connected Component

Today, we explained how to use DFS to find all the strongly connected components of a graph.

Homework 5

Homework 5 is out. Any question can be asked here.

Problem 1
Q: is there a maximum grade?
A:You can assume there is no maximum grade for each course.


Q: Can you give us hint on the running time for problem 1?
For full credit. The running time should be O(n), O(T log n+ n), O(nT^2)
Hint for case 3:　dynamic programming


Problem 4
Q:The goal is to: delete as many edges as possible from G , when Vertex u is reachable from v if there is a path from v to u. Also, do we need to remove as many edges as possible from the other vertexes that will be along the path from u--to --v? or just to remove the edges that connect u--to--v and left the minimum path.

A:　This problem requires you to delete the maximum number edges so that the reachability does not change for *ANY* two vertices u, v; i.e., for any two vertices u,v in V,  u is reachable from v in G if and only if u is reachable from v in G'.

Lecture 29 DFS, longest path, topological sort, and strongly connected component

Today, we talked about DFS and its applications on solving topological sort, longest path in a graph, and deciding whether a directed graph is strongly connected.

Lecture 28. Algorithms for finding the shortest path

Today, we talked about three different algorithms for the shortest path problem. The Bellman-Ford algorithm, Floyd-Warshall algorithm and Dijkstra's algorithm.

Lecture 27. Dynamic Proigramming (2)

Today, we talked about the longest increasing subsequence. We gave two algorithms with running time O(n^2) and O(n log n).

Then we talked about 0-1 Knapsack problem and gave a dynamic programming algorithm for it.

Lecture 26 Dynamic programming

Today we talked about dyanmic programming. We showed how to use Dynamic Programming to solve the weight verision of activity selection.