The intro lecture

We discussed the implications of looking at Computation as an abstract notion, and about formalising the notion of efficiency. Today, we looked at the demarcation between efficient and intractable problems and got ourselves comfortable with the notion of "polynomial time" algorithms. We also looked at the powerful idea of the "reduction" and saw how there is a non-trivial transformation from the familiar 3-SAT problem to the Vertex Cover problem. We also looked at a very gentle introduction to the notion of NP-Completeness.

We used the wonderful notes for the first lecture from this.