CS5311 Computation Theory
Course Information Page
Spring 2002

Course Instructor	Dr. C.-K. Shene
Office	Dow 717
Class Meeting	Tuesday and Thursday, 2:05 - 3:20pm, Fisher 126
Office Hour	Monday and Wednesday 4 - 5 pm
Phone	(906) 487-3392
e-mail	shene@mtu.edu

Click here for the most recent announcements (May 8, 2002)
Click here for the most recent grade posting (May 9, 2002)

A Few Important Notes

This is a theory course involving theorem proving and abstract reasoning. If you are not ready for rigorous mathematical reasoning, please do not take this course.

I expect everyone in this class has the background of CS4311 Computational Theory for the basics of grammars/languages and Turing machines and CS4321 Design and Analysis of Algorithms or better for the basics of complexity measures and NP-completeness.

Click here for some interesting and quotes.

Click here to see a Notes for Writing and Submitting Homework.

Course Description

This course covers the following important topics in theory of computing: computable functions, primitive recursive functions, a universal program, decidability problems, recursively enumerable sets, the parameter theorem, diagonalization, reducibility, the recursion theorem and various computational complexity related topics.

Textbook

Martin D. Davis, Ron Sigal and Elaine J. Weyuker,
Computability, Complexity, and Languages, second edition,
Academic Press, 1994.

Meeting Time and Office Hours

	Monday	Tuesday	Wednesday	Thursday	Friday
1 - 2 pm		Dept. Meeting
2:05 - 3 pm		CS5311 Fisher 126		CS5311 Fisher 126
3 - 3:20 pm		CS5311 Fisher 126		CS5311 Fisher 126	Dept. Seminar
3:35 - 4 pm		CS4411 Fisher 129		CS4411 Fisher 129
4 - 4:50 pm	Office Hour	CS4411 Fisher 129	Office Hour	CS4411 Fisher 129

Course Syllabus

*Week*		*Topics*	*Reading*
1	January 14	Introduction	Chap. 1
2	January 21	Computable Functions	Chap. 2
3	January 28	Computable Functions	Chap. 2
4	February 4	Primitive Recursive Functions	Chap. 3
5	February 11	Primitive Recursive Functions	Chap. 3
6	February 18	A Universal Program	Chap. 4
7	February 25
8	March 11
9	March 18
10	March 25	Turing Machines	Chap. 6
11	April 1	Time Complexity
12	April 8	Time Complexity
13	April 15	Space Complexity
14	April 22	Space Complexity
15	April 29	PRAM and Circuit Models

Important Dates

Week 3	January 31	Thursday	2:05pm	Homework 1 due
Week 5	February 19	Tuesday	2:05pm	Homework 2 due
Week 7	February 28	Thursday	2:05pm	Quiz 1 (40 min)
Week 5	March 21	Thursday	2:05pm	Homework 3 due
Week 10	March 28	Thursday	2:05pm	Midterm (in class 80 min)
Week 12	April 16	Tuesday	2:05pm	Homework 4 due
Week 14	April 23	Tuesday	2:05pm	Quiz 2 (40 min)
Week 15	May 2	Thursday	2:05pm	Homework 5 due

May 8	Wednesday	5:15pm (Fisher 126)	Final (2 hours)

Weights Assigned to Homework

There are five homework, two quizzes, a midterm and a final. The weights assigned to each item is shown below.

*Homework*	*Quizzes*	*Midterm*	*Final*
30%	15%	25%	30%

Suppose a person has the following scores:

*Home 1*	*Home 2*	*Home 3*	*Home 4*	*Home 5*	*Quiz 1*	*Quiz 2*	*Midterm*	*Final*
75	80	95	85	90	87	91	84	76

The averages of homework and quizzes are 85 and 89, respectively. The final score of this person is calculated as 85×0.3 + 89×0.15 + 84×0.25 + 76×0.3 = 82.65, which is rounded to 83.

Grading

Grading will be based approximately on the scale shown in the table below.

Grade	A	AB	B	BC	C	CD	D	F
Scale	90-100%	85-89%	80-84%	75-79%	70-74%	65-69%	60-64%	0-59%

Late Policy

No late homework will be graded unless you have a valid excuse. Note that homework is always due before class starts.

Collaboration and Cheating

You may discuss the meaning or intent of a homework problem, but not ways to solve it. All work turned in must be completely your own. Any and all use of materials from other texts or references must be explicitly stated as part of your solution. In general, any acts of plagiarism will result in a failing grade for the course along with the submission of a report to the Dean of Students. See Computer Science Policy on Cheating and Academic Integrity at MTU: A Guide for Students and Faculty for the details.

Exams and Final

You are responsible for avoiding exam time conflicts!!

ADA

``MTU complies with all federal and state laws and regulations regarding discrimination, including the Americans with Disability Act of 1990 (ADA). If you have a disability and need a reasonable accommodation for equal access to education or services at MTU, please call Dr. Gloria Melton, Associate Dean of Students, (2212). For other concerns about discrimination, you may contact your advisor, department head, or the Affirmative Action Office (3310).''

Downloadable and Other Stuffs

Files are in Postscript format. You need a PostScript printer to print these files.

Homework

Notes for Writing and Submitting Homework

Handouts and Solutions (Postscript files)

Homework 1	Handout	Solution
Homework 2	Handout	Solution
Homework 3	Handout	Solution
Homework 4	Handout	Solution
Homework 5	Handout	Solution

Reading Lists

Week 1	Week 2	Week 3	Week 4	Week 5
Week 6	Week 7	Week 8	Week 9	Week 10
Week 11	Week 12	Week 13	Week 14	Week 15

Exams

Quiz 1 Solutions (PostScript file)

Midterm Solution (PostScript file)

Quiz 2 Solutions (PostScript file)

You are visitor

since July 1, 1998.
Last update: December 23, 2001.

Please send comments and suggestions to shene@mtu.edu

CS5311 Computation Theory Course Information Page Spring 2002