CSE540 Home Page (Fall 2007)

Welcome to the CSE540 (Theory of Computation) home page for Fall 2007.

• Course staff information, including office hours.
• Course syllabus.
• Course sign-up questionnaire (please fill out and return to Prof. Stark).
• Homeworks:
  • Homework 1, due September 13, 2007.
  • Homework 2, due October 2, 2007.
  • Homework 3, due October 18, 2007.
  • Homework 4, due November 1, 2007.
  • Homework 5, due November 27, 2007.
  • Homework 6, due December 18, 2007.

Important Course News and Messages

Please check this page regularly for new messages. The newest messages will always appear first.

Final exam statistics.

FINAL (whole class ) Valid 19; Mean 41.00; Std. Dev. 28.46 FINAL (section MS) Valid 11; Mean 22.27; Std. Dev. 14.76 FINAL (section PHD) Valid 8; Mean 66.75; Std. Dev. 21.51 The maximum number of points attainable was 100. The maximum score actually attained was 95 (PhD: 95, MS: 45). The minimum score actually attained was 3 (PhD: 30, MS: 3). I was very sparing with partial credit, and I did not give full credit for correct Yes/No answers with wrong reasons.

Midterm exam statistics.

I've decided to report MS and PHD statistics separately, because basically for PHD students the main issue in final grade assignment is whether or not they pass the qualifier in this area, whereas for MS students the main issue is whether they should pass the proficiency requirement. These are quite different objectives. Also, the grades are turning out to be strongly polarized into MS and PHD groups. MIDTERM (whole class ) Valid 20; Mean 23.30; Std. Dev. 14.17 MIDTERM (section MS) Valid 12; Mean 13.58; Std. Dev. 6.61 MIDTERM (section PHD) Valid 8; Mean 37.88; Std. Dev. 8.46 In the above, "Valid" means the number of nonzero scores in the applicable category. The maximum number of points attainable was 60. The maximum score actually attained was 50 (PhD: 50, MS: 25). The minimum score actually attained was 3 (PhD: 26, MS: 3). I tended not to give very much partial credit, because I did not want to make decisions about things like the "degree of correctness" of an incorrect automaton for a given language. Also, I tended not to give any credit for a Yes/No answer with no stated reason.

Solutions to Midterm Exam:

I put here solutions to the midterm exam.

Midterm Exam:

We decided to have the midterm exam during class on November 8.

Exercise 2.7.2(c):

I put here a solution to Exercise 2.7.2(c), which seems to be more subtle than people realized, even those whose papers I thought were correct.
(Updated: October 11, 2007, 9:30AM)

Exercise 2.6.2(c):

I put here a solution to Exercise 2.6.2(c), which nobody got correct.

Exercise 2.8.5:

I put here a solution to Exercise 2.8.5.

Logic, Proof, and Sets:

I put here some scanned material on this topic. I will announce the ID and password to this download in class.

Homework 1 due date:

I didn't realize that September 13 was a no-class day. You can hand in Homework 1 until September 18.