**Lectures**: Tuesday-Thursday 14:20 – 15:40 (Caldwell Lab 220)

**Midterm**: Thursday October 3rd

— Midterm – Solutions

— Median: 74 — Average: 65.5 — Max possible: 100,

— Median with Bonus: 80 — Average with Bonus: 70.8 — Max possible with Bonus: 110

**Final Exam:** Friday, December 6th, 4:00pm to 6:00pm (Caldwell Lab 220)

The final exam will cover all of the material covered in class up to and not including the randomized complexity theory. While containing computability theory, the exam will more so emphasize the complexity theory portion of the material. The following pdf contains some sample problems to solve as preparation for the final exam. Please note that the final exam is not bound to these sample problems, and the student is expected to be familiar with all the material covered in the lecture notes.

sample final questions (updated dec 5)

**Instructor:** Pooya Hatami (Dreese Lab **489**, last_name.2@osu.edu)

**TA**: Minghao Tian (Dreese Lab **474**, last_name.394@osu.edu)

**Office Hours:
**Pooya Hatami: Tuesdays 17:00-18:00 (Dreese 489) or by appointment

Minghao Tian: Wednesdays 16:00-17:00 (Dreese 474)

#### Lecture Notes

I will maintain the pdf file below, gradually adding new lectures:

Lectures 1-24 (last updated Nov 14)

#### Homeworks

Assignment #1, due September 10th at the start of class,

Assignment#1 — Solutions

Total points possible: 100/100, Median: 78/100

Assignment #2, due October 3rd at the start of class

Assignment#2 – Solutions

Note: HW2.7 is now a bonus problem worth 10 points

Total points possible: 85/85, Median: 55.5/85=65/100

Assignment #3 due November 26th at the start of class

**Course Summary (tentative):**

- This course intends to introduce the student to theory of computability, and computational complexity theory, with a slight more emphasis on the latter.
- Computability Theory: Notions of algorithms, Turing Machines (deterministic, nondeterministic, …), Church-Turing Thesis, Decidability, Turing-recognizability and Enumerability, Diagonilization, Reducibility
- Complexity Theory: Complexity classes and measures, P, NP, coNP, NP-completeness, Hierarchy Theorems, Space Complexity, Boolean circuits, randomized computation, RP, ZPP, BPP, RL, BPL

**Related Reading: **

- Sanjeev Arora and Boaz Barak,
**Complexity Theory: a Modern Approach** - Michael Sipser,
**Introduction to the Theory of Computation** - Christos Papadimitriou,
**Complexity Theory**

**Grading:
**25% homeworks — 30% midterm — 45% last exam

**Policy on Collaboration:**

Studying in groups is encouraged, however we also encourage students to work on the current homework set on their own. If you do collaborate, state it clearly at the beginning of your solution (give name of collaborator). Acknowledged collaboration does not mean **copying** someone else’s solution: Discuss the solutions, understand the ideas and give your own rendering.