|
|
|||||||
|---|---|---|---|---|---|---|---|
CMSC 28100-1: Introduction to Complexity Theory
Class: Monday, Wednesday and Friday 9:30-10:20 pm in Ry 251 Midsem Test: Monday, May 4 in Ry 251 Final Exam: Monday, June 8, 10:30am to 12:30pm in Ry 251 Tutorials: Tuesday-Thursday 5:00-6:00 pm Ry 276 Instructor: Office Hour: Wednesday
2:30-3:30 pm in Ry 165-B. TA: Office Hour: Wednesday
3:30-4:30 pm in Young 208-B. TA: Office Hour: Friday
3:30-4:30 pm in Ry 176. Overview:
Computability
topics are discussed. This course
introduces complexity theory. Relationships between space and
time, determinism and nondeterminism, NP-completeness, and the
P versus NP question are investigated.
Text:
Introduction
to Automata Theory, Languages, and Computation Other useful texts (added by Pooya):
Introduction to the Theory of Computation Computational Complexity: A Modern Approach Computability: An Introduction to Recursive Function Theory Assignments:
Will be posted here every Friday, due in class the
following Friday. |
|||||||
| Homework 1 (due Friday April 10th – in class) Solutions | |||||||
| Homework 2 (due Friday April 17th – in class) Solutions | |||||||
| Homework 3 (due Friday April 24th – in class) Solution guidelines | |||||||
| Homework 4 (due Friday May 1st – in class) Solution guidelines | |||||||
| Homework 5 (due Friday May 8st – in class) Solution guidelines | |||||||
| Homework 6 (due Friday May 15th – in class) Solution guidelines | |||||||
| Homework 7 (due Friday May 22nd – in class) Solution guidelines | |||||||
| Homework 8 (due Friday May 29nd – in class) Solution guidlines |
|
Grade Breakdown: |
|---|
| Homeworks: 40% |
| Midterm: 20% |
| Final Exam: 40% |
|
Homework Statistics: |
|---|
| Total points possible: 300 |
| Number of people: 47 |
| Median: 226 |
|
Midterm Statistics: |
| Total points possible: 31 |
| Number of people attended: 45 |
| Median: 17.5 |
| Upper quartile: 25 |
| Lower quartile: 13.75 |