Swarthmore CS46 Theory of Computation Spring 2010

Introduction

Welcome to CS46: Theory of Computation! Computer technology changes rapidly, but the underlying model of computation is relatively unchanged in the past 50 years. How do computers compute, and why is this method of computation preferred over others methods. Do other methods even exist? Could we solve more interesting problems with another model? Could we solve the same problems we solve today using a simpler model of computation? In this course will will look at various theoretical models of computation and examine the computational power of these models. For each model we consider problems that can and cannot be solved, and develop a rigorous method of classifying how difficult certain problems are to compute. While the course emphasis is on theory, there are many applications of the topics discussed. Regular expressions, compilers, CPU job scheduling, and many other real-world problems have some underlying computational model rooted in the theory of computation.

Announcements

Final Exam is May 6th, 9am-Noon

Class info

Room: Science Center 264
Time: TR 9:55am–11:10am
Text: Elements of the Theory of Computation 2nd Ed. by Lewis and Papadimitriou

Professor: Andrew Danner
Office: Science Center 253
Phone: (610) 328-8665
Office hours: by appointment. Drop by if my door is open, or email me to set up a time

Schedule

WEEK	DAY	ANNOUNCEMENTS	TOPIC & READING	HOMEWORK
1	Jan 19		Math preliminaries p1-28 Languages p42-51	HW 1
	Jan 21
2	Jan 26		Finite automata p55-89,102-109 regular languages Context free grammars p113-122	HW 2
	Jan 28	Drop/Add ends (Jan 29)
3	Feb 02			HW 3
	Feb 04
4	Feb 09		Pushdown automata Context free languages Determistic CFLs p123-149	HW 4
	Feb 11
5	Feb 16			HW 5
	Feb 18
6	Feb 23		Deterministic CFLs	HW 6
	Feb 25		Turing Machine Intro
7	Mar 02		Turing machine computation
	Mar 04
	Mar 09	Spring Vacation
	Mar 11
8	Mar 16		Turing machine extensions
	Mar 18
9	Mar 23		Non-determinism and Turing Machines
	Mar 25	Last day to declare CR/NC or withdraw with a "W" (Mar 26)	Unsolvable problems	HW 7
10	Mar 30
	Apr 01
11	Apr 06		Computational complexity	HW 8
	Apr 08
12	Apr 13	No Class
	Apr 15		NP-complete problems
13	Apr 20		Complexity hierarchies Wrapup
	Apr 22
14	Apr 27
	Apr 29
	May 06	Final exams start
	May 15	Final exams end

Grading

Grades will be weighted as follows:

40%	Homework assignments
10%	Lab assignments
10%	Class Participation and Discussion
20%	Midterm exam
20%	Final Exam

Homework policy

Each week, reading and several problems will be assigned. You should work on all of the problems but hand in clearly written solutions to a subset (usually four) of the problems at the beginning of the Thursday session. Sometimes I will specify certain problems that must be part of what you hand in. All students should be prepared to discuss the reading and solutions to any of the problems. Always do all parts of a problem unless I specify otherwise.

It is best if you start the assignments early, and at least read the problems and make sure you understand what the problem is asking soon after the problems are assigned. If you do not understand a problem, ask for clarification. I often find that the solution to problems in this course only come if the problems sit in your brain for several hours, even if you are not constantly thinking about the problem during that time.

Late assignments will not be accepted except in extreme situations and only if you contact me well before the deadline. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.

Academic Accommodations

Academic accommodations are available for students with disabilities who are registered with Student Disability Services in the Dean's office. Students in need of disability accommodations should schedule an appointment with me early in the semester to discuss accommodations for this course that have been approved by the Dean's office. All requests must come through an accommodation letter from the Dean's office. To receive an accommodation for a course activity, your meeting with me must be at least one week prior to the activity.

Contact Tracey Rush at the Dean's office and follow these steps for obtaining accommodations.

Academic Integrity

Academic honesty is required in all work you submit to be graded. You may not submit work done with (or by) someone else. You may not examine or use work done by others to complete your own work. You may discuss assignment specifications and requirements with others in the class to be sure you understand the problem. In addition, you are allowed to work with others to help learn the course material. However, with the exception of the student mentors and your partner on group assignments, you may not work with others on your assignments.

All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

"It is the opinion of the faculty that for an intentional first offense, failure in the course normally is appropriate. Suspension for a semester or deprivation of the degree in that year may also be appropriate when warranted by the seriousness of the offense." - Student Handbook (2009-2010, pg18 Section I.B.3.b.i)

Please see me if there are any questions about what is permissible.

External Links

Links that are related to the course may be posted here. If you have suggestions for links, let me know.

A real DIY Turing Machine
JFLAP: Java Formal Languages and Automata Package

CS46 — Theory of Computation Spring 2010