Microsoft Word – hw0
COMS 4236, Introduction to Computational Complexity
Homework 0
Due Thursday 1/18 on Courseworks
Instructions
Please supply the following information:
1. Name:
2. Your UNI:
3. Program, track and year:
4. List relevant background courses and where you have taken them (e.g. computability,
algorithms, discrete math, …):
5. How familiar are you with the following topics (None, Somewhat, Very):
1. Big-O notation
2. Proof by induction
3. Logic
4. Turing Machines
5. Graph algorithms
6. NP-completeness
6. Why are you taking this course?