CS 360 - Introduction to Theory of Computing

Location: MC 4064
Time: Tu/Th 13:00-14:20
Instructor:
  Chris Marriott
Office: DC 3125
TA(s): Narges Simjour
EvaluationNumber% of Final GradeDue/Exam Dates (Tentative)
Assignment 4 20%
Assignment 1 Oct. 5
Assignment 2 Oct. 26th
Assignment 3 Nov. 16
Assignment 4 Dec. 7th
Midterm 2 40%
Midterm 1 Oct. 13th
Midterm 2 Nov. 10th
Final 1 40% Dec. 10th
Note: Assignment 4 replaced with a corrected version - Nov. 26, 2009.

You can view your pre-final marks here.

The final exam is marked. In order to curve the grades up slightly the percentage is calculated taking 112 as the maximum marks on the exam so it was possible to get over 100%. Final grades will be available on Quest early next week.

Final Min Score = 40.5

Final Max Score = 115

Final Mean Score = 78.4

Final Median Score = 77

Slight curves have been applied to assignments 2, 3, and 4 taking them out of 17, 16, and 15 respectively. In light of the curves applied I will not be hearing appeals for increases in grades in order to boost your average. However, I will still hear appeals on any erroneous marking or totaling on any assignment/exam. Please contact me by email.

Have a great holidays!

Assignments
Assignment 1 assignment1.pdf assignment1.tex solution1.pdf
Assignment 2 assignment2.pdf assignment2.tex solution2.pdf
Assignment 3 assignment3.pdf assignment3.tex solution3.pdf
Assignment 4 assignment4.pdf assignment4.tex solution4.pdf

Course Schedule
DateTopicReadings
Sept. 15 Alphabets/Strings/Languages/Finite Automata/Grammars 1.5
Sept. 17 Formal Definitions and Equivalence of Deterministic and Non-deterministic Finite Automata 2.2, 2.3, (2.4), 2.5
Sept. 22 Closure of Regular Languages/Regular Operations/Regular Expressions 3.2.3, 4.2.1, 4.2.2, (4.2.3), (4.2.4), 3.1
Sept. 24 Equivalence of Regular Expressions to DFA/NFA 3.2
Sept. 29 Pumping Lemma for Regular Languages 4.1
Oct. 1 Context Free Grammars/Parse Trees/Derivations/Ambiguity 5.1, 5.2, (5.3), 5.4
Oct. 6 Chomsky Normal Form/Context Free Languages 7.1
Oct. 8 Push-Down Automata 6.1, 6.2
Oct. 13 Midterm I  
Oct. 15 Equivalence of PDA to CFG 6.3
Oct. 20 Pumping Lemma for Context Free Languages 7.2
Oct. 22 Closure of Context Free Languages 7.3
Oct. 27 Turing Machines: Definitions and Examples 8.2
Oct. 29 Turing Machine Variants and Equivalence 8.3, 8.4
Nov. 3 High-Level Turing Machine Descriptions/Church-Turing Thesis/Encoding Schemes 8.6
Nov. 5 Decidable Languages/Languages of Encoded Machines 4.3, 7.4
Nov. 10 Midterm II  
Nov. 12 Non-deterministic Turing Machines/Closure of Decidable Languages 8.4.4
Nov. 17 Undecidability/Unrecognizability 9.1
Nov. 19 Universal Turing Machine/Halting Problem/Accepting Problem 9.2, 9.3.2
Nov. 24 Computable Functions and Recursion Theorem  
Nov. 26 Computable Reductions 9.3.1
Dec. 1 Reductions and Undecidability  
Dec. 3 Busy Beaver Function