Syllabus for CSC427 Introduction to the Theory of Computation.
General
This is a first course in the theory of computation. The course is of a generally
mathematical nature, however it requires no calculus, or other "normal" mathematics.
It explores what is computation. This is presented by way of machine models, and
also linguistic models.
-
Join the Slack channel, csc-courses.slack.com#csc427-232.
Uses your cs.miami.edu, miami.edu, or umaimi.edu email to join.
- The assigned textbook is
Introduction
to the Theory of Computer, Third Edition by Mike Sipser.
-
There maybe reading assignments from texts other than the class text.
- We have a csc427-232 github with some public information, and the assignments.
-
The course assigns problem sets — either written assignments or programming projects.
-
Programming assignments are in Python and Jupyter.
- You will need a github account.
- Assignments are distributed and submitted (and help can be obtained) using Github
classroom.
- Grace Periods
-
Three days grace.
-
After which 1/3 off.
-
Until a week, when its 2/3 off.
-
Until a second week, when it is 5/6 off.
-
Until the third week, when it is not graded but marked submitted.
- Homework is due midnight
Miami time of the date due; and late days are also counted at midnight Miami time of that day.
-
No work accepted after midnight of the last day of classes,
and this rule has precedence over grace periods.
-
Our TA is Jamie Deng jdeng@cs.miami.edu
- Grades are 30% final, 30% midterm, 40% problem sets.
- Midterm Date: Wednesday 1 March. In class.
- Final Exam Date:
Friday 5 May, 11:00–1:30.
- Final Exam Replaced with a Final Project: Wednesday 3 May – Monday 8 May.
Problem Sets for CSC427 Introduction to the Theory of Computation.
The problem sets are on github classroom. An invitation is posted in our Slack channel for each assignment.
- Problem Set 1: Python Exercises
- Problem Set 2: Deterministic Finite Automata
- Problem Set 3: Nondeterministic Finite Automata
- Due: Friday, February 10.
- Problem Set 4: Closure Properties of Regular Languages
- Due: Friday, February 17.
- Problem Set 5: Regular Expressions
- Due: Friday, February 24.
- Problem Set 6: Turing Machines
- Problem Set 7: Decidable Languages
- Problem Set 8: NP Completeness
Errata:
Problem Set 1:
-- none yet ---
Problem Set 2:
ex_1_6l_test = (['1','11','','00','01010'],['0','1000','111000'])
ex_1_6i_test = (['','1','11','101','11101'],['0','01','100','110','10001'])
Problem Set 3:
-- none yet ---
Problem Set 4:
-- none yet ---
Problem Set 5:
-- none yet ---
Problem Set 6:
-- none yet ---
Problem Set 7:
Exercise A, m1_e definition, change accept set to: 'accept':{'q3'}
Exercise A, about the 14th line in the function basic_test,
change to: if not de.decide_empty():
In the basic_test, add/change to the red words:
correct += 1
p = de.prove_not_empty()
m = SimpleFiniteAutomata(m1)
if m.compute(p):
print(f'm1:\tcorrect: the language accepts {p}')
correct += 1