Office hour next week & Thanks

Yi: Tue 4pm-5:30pm
Leo: Wed 3:30pm-4:30pm
Siddharth: Monday 9:30-11:30

The class is over. Thanks a lot for coming (at every early monring) and making it a fun affair for me. I really appreciate it. Don't forget to fill in the teaching evaluation form.

Homework 5 distribution

median 62
max 77

Lecture 39 Approximation Algorithm

Today, we talked about the approximation algorithms for vertex cover and metric travelling salesman problem.

Lecture 38 NP complete problems

We talked  about why Clique, Maximum size Independent set, and Vertex Cover are NP Complete.

Homework 4

Max:  90
Average: 70.3
Median: 72

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.