**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

**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-22 (last updated Nov 10)

#### 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.