CSC280

Computer Models and Limitations

                                               

Instructor: Mehdi Manshadi

 

Department of Computer Science

University of Rochester

Spring 2010

 

This page is under construction. Contents are subject to change.

 

Location: CSB 601

Time: MW 3:25-4:40

 

Instructor's office hours: Please make an appointment by email.

 

TA: Curtis Menton

TA's office hours: TR 2-3pm (CSB 617)

 

Workshop Leaders: Adina Rubinoff (Tuesdays), Scott Ames (Fridays)

 

Textbook

Michael J. Sipser, Introduction to the Theory of Computation (2nd edition), Thomson (Course Technology), 2006.

or alternatively,

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

-Both are on reserve in the library. There will be handouts for the topics not covered in the book.

 

Grading

Workshop 5%

Homework 15%

Quiz 10%

Short Exams 10%

Midterm 20%

Final: 40%

 

Workshop

There will be 15 workshops. Each workshop will be held twice: Fridays 3:30-5pm and the follwoing Tuesdays 5-6:30pm, both in CSB 632 (e.g. Workshop-1 will be held on Friday 1/15 and Tuesday 1/19, Workshop-2 will be held on Friday 1/22 and Tuesday 1/26, etc.). Attending one session of each workshop is required and counts for 5% of your final grade.

 

 

Homework

There will be 15 problem sets, posted on the course web site on Wednesdays right before class. The assignments are due 1 week later in class (except the one assigned before spring break, which will be due the Monday after break). No late submissions will be accepted. In order to allow for any sick days, religious holidays, unavoidable trips, etc. the lowest 3 problem set grades will be dropped.

 

 

Quiz

There will be 15-20 quizzes with no advance warning (exception: there will be a quiz on the first day of class!), given at the beginning, in the middle, or at the end of the class. The quizzes may be based on the two previous lectures, the reading assigned for the day, the lecture just given, or the assignment due that day. You will get 25% of the score just for taking the quiz. As with homework, the lowest 3 quiz grades will be dropped.

 

Short Exams (2/15, 4/7)

There will be two short exams, at the end of the first and third quarters of the semester, covering part 1 (Automata) and part 3 (Complexity) of the course respectively (See course syllabus below). They each contribute 5% to your final grade.

 

Midterm (3/17)

There will be a midterm on Wednesday 3/17, covering the first two parts of the course (Automata and Computability). The midterm counts for 20% of your final grade.

 

Final (5/3, 8:30AM)

The final exam will be on May 3rd at 8:30AM. It is cumulative, and counts for 40% of your final grade. The final will be an open-book exam.

 

Collaboration

Collaboration on homework is allowed as long as no written solutions are taken out of the discussion, and each student writes up their own independent solution.


 

Syllabus

Date

Topic

Reading assignment

Slides

HW

W 1/13

Introduction

This handout

SP Ch. 0/HU Ch. 1

Lecture 1

HW1

M 1/18

Martin Luther King Day, No class.

Part 1. Automata

W 1/20

Strings, Languages, and Regular Expressions

SP pp 63-66

Lecture 2

HW2

M 1/25

Finite Automata

SP pp 31-54/HU pp 13-21

 

 

W 1/27

Regular Grammars, Equivalence of the models

 

 

HW3

M 2/1

Properties of Regular Languages

 

 

 

W 2/3

Context-Free Grammars

 

 

HW4

M 2/8

Push Down Automata

 

 

 

W 2/10

Pumping Lemma

 

 

HW5

M 2/15

Review, Q&A, Short Exam 1

 

 

 

Part 2. Computability

W 2/17

Turing Machines

 

 

HW6

M 2/22

Alternative definitions

 

 

 

W 2/24

Decidability

 

 

HW7

M 3/1

Reduction

 

 

 

W 3/3

Post Correspondence Problem

 

 

HW8

M 3/8

Spring break

W 3/10

Part 3. Complexity

M 3/15

Review, Q&A

 

 

 

W 3/17

Midterm

 

 

HW9

M 3/22

Time complexity & the class P

 

 

 

W 3/24

Class NP: P vs. NP

 

 

HW10

M 3/29

NP-Completeness

 

 

 

W 3/31

Space Complexity

 

 

HW11

M 4/5

The class L and NL

 

 

 

W 4/7

Review, Q&A, Short Exam 2

 

 

HW12

Part 4. Advanced topics

M 4/12

Kolmogorov Complxity

 

 

 

W 4/14

Cryptography and one-way functions

 

 

HW13

M 4/19

Randomized computation and the class BPP

 

 

 

W 4/21

Take it easy: Approximation

 

 

HW14

M 4/26

Take it easy [cont.]:

Average Case Complexity

 

 

 

W 4/28

Something fun:

Quantum computing and the class BQP

 

 

HW15