Syllabus: CSC 341, Theory of Computation

	Location:	Julian 040, TTh 2-3:50 pm
	Home Page:	http://www.csc.depauw.edu/~bhoward/courses/0304Spring/csc341/
	Professor:	Brian Howard (bhoward@depauw.edu)
	Office:	Julian 266, ph. 658-4120
	Office Hours:	TTh 10-11:30, MTWTh 4-5, or by appointment (or when my door is open)

Text:

Michael Sipser, ``Introduction to the Theory of Computation'', PWS, 1997.

Course Description:

(from the Catalog) Various models of formal languages (which provide a basis for compilers) and computation (which defines the kinds of problems that can be solved by a computer) are studied. Topics include regular languages, regular expressions, finite state automata, context-free languages, context-free grammars, push-down automata and Turing machines. The application of these models to several practical problems in computer science is considered. Computational limits are also discussed, using as examples several problems which cannot be solved by any algorithm.

Grading:

The grade for this course will be based on the following:

• 45%: Homework, Quizzes, Participation, and Presentations
• 30%: In-class exams (15% each)--Tuesday, March 2 and Tuesday, April 13
• 25%: Take-Home Final Exam

Policy Statements:

 

• You are expected to attend all class sessions. However, I expect you to take your own education seriously, so I do not keep formal attendance records. If you miss a class, you are responsible for catching up with the material that was covered and any announcements that were made.

• Homework assignments are due by the start of class on the assigned date. Late submissions will be accepted until the next class time at a penalty of half the grade. Extensions will be considered only by prior arrangement.

• Cheating, plagiarism, submission of the work of others, etc., violates the DePauw policy on academic integrity and may result in penalties ranging from a lowered grade to course failure or expulsion. The policy and discussion of each student's obligations and rights are in the Student Handbook.

  With respect to this course, no collaboration is permitted on exams or quizzes. You may discuss homework problems with anyone you want (in fact, you are encouraged to do so), but you should not copy another student's work nor permit your work to be copied. The key idea is that you should understand all of the work you turn in, and you should be able to replicate it on your own. If you do not feel that you can replicate the work independently, then it is not fair (to yourself or to others) to submit it as your own work. If at any time you are uncertain what constitutes ``appropriate'' collaboration, it is your responsibility to clarify it with me.

• During class time, the computer at your seat should be used for note-taking, classroom interaction, and in-class exercises. You are not permitted to read e-mail, browse the web, play games, etc. while class is in session.

Calendar:

Note that there will be no class meeting on Thursday, March 4.

Week	Tuesday	Thursday
1	Feb. 3	5
2	10	12
3	17	19
4	24	26
5	Mar. 2: Exam	No Class
6	9	11
7	16	18
Spring Break
8	30	Apr. 1
9	6	8
10	13: Exam	15
11	20	22
12	27	29
13	May 4	6
14	11	13
Final Exam

Schedule of Topics:

This schedule is only approximate and subject to change.

• Week 1: Chapter 0 (Introduction)
• Weeks 2-4: Chapter 1 (Regular Languages)
• Week 5: Exam I, Tuesday, March 2
• Weeks 6 & 7: Chapter 2 (Context-Free Languages)
• Week 8: Chapter 3 (Turing Machines)
• Week 9: Chapter 4 (Decidability)
• Week 10: Exam II, Tuesday, April 13
• Week 11: Chapter 5 (Reducibility)
• Week 12: Chapter 6 (More Computability)
• Weeks 13 & 14: Chapters 7-10 (Complexity)

Especially for Chapters 6-10, we will not be covering all of the material in the text; more details on the readings will be given as the semester progresses.