Dr
CS 612 May 2 Term
Theory of Computation
Dr. Christos Nikolopoulos, Office: BR 197
URL:
class web site:
Communication by email preferred:
Email: chris@bradley.edu
Required Textbooks:
Introduction to the Theory of Computation, M. Sipser, PWS
Other References:
1. Notes found in the class website
2. Video tapes of lectures found in the class web site
Description:
We will cover the theory of formal language and automata, and selected topics from theory of algorithms and computability (Chapters 0, 1, 2, 3, 4 and sections from 5, 7).
Class delivery format:
The class is offered in an online, synchronous and asynchronous format.
Individual emails to the instructor will be answered by the end of the day received or earlier. Tests will be online.
The MIDTERM will be sent by email to each student by 9:00 a.m. of the announced day (W June 11th) and she/he will have till 9:00 p.m. the next day to complete, and email the answers back to the instructor. The answers could be typed in a word file or they could be handwritten and scanned.
The FINAL will be emailed to each student by 9:00 a.m. on Thursday July 10th and answers are due by 9:00 p.m. the next day (Friday) by scanning and sent by email back to the instructor. Times given are Peoria (central) tme.
The HOMEWORK is due by email also on the last day (Friday 11th) of the term by 9:00 a.m. (no need to be typed, can hand-write and scan)
LECTURES ARE VIDEO TAPED and on YouTube (see URLs below)
In addition to the online format, for those students who prefer the person to person interaction with the instructor, the instructor will be available at the BR156 Intelligent Systems and Robotics Lab to meet with students upon request. If you have doubts about the material and your questions were not satisfactorily answered by the video lectures or email communications, you can email me the night before the day you want to meet and we can meet the next day.
The table below gives the reading assignments each day from the books and online sources.
# Date Topics for reading/online discussion Readings/Assignments
|M day 1 |Overview of class |Introduction |
|T day 2 |Mathematical foundations |Chapter 0, Sipser’s book |
|And | | |
|W day 3 | | |
|TH day 4 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 1: 1.1 1.1 |
| |Lemma |1.2 |
| | |1.3 |
| | | |
|F day 5 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 1: 1.1 |
| |Lemma |1.2 |
| | |1.3 |
|M day 6 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 1: 1.1 |
| |Lemma |1.2 |
| | |1.3 |
|T day 7 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 2: |
| |Lemma |1.4 |
| | |2.1 |
|W day 8 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 2: |
| |Lemma |1.4 |
| | |2.1 |
|TH day 9 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 2: |
| |Lemma |1.4 |
| | |2.1 |
|F day 10 |DFSA, NFSA, RE, Right Linear |Chapter 1, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+watch Video 3: 2.2 |
| |Lemma examples |2.3 |
| | |2.5 |
| | | |
| | | |
|M day 11 |DFSA, NFSA, RE, Right Linear |Chapter 2, Sipser’s book |
| |Grammars (RLG), conversions, |+Online notes |
| |regular languages, Pumping |+ watch Video 4: |
| |Lemma |3.1 |
| | |3.2 |
|T day 12 |PDAs, CFGs, equivalency, |Chapter 2, Sipser’s book |
| |pumping lemma, |+Online notes |
|And | |+Video 5: |
| | |3.3 |
|W day 13 | |4.1 |
| | |+Video 6: 4.2 |
|And | |4.3 |
| | | |
|TH day 14 | | |
|F day 15 |PDAs, CFGs, equivalency, |Chapter 2, Sipser’s book |
| |pumping lemma, |+Online notes |
| | |+Video 7: 4.4 |
| | |4.5 |
| | | |
|M day 16 |PDAs, CFGs, equivalency, |Chapter 2, Sipser’s book |
|And |pumping lemma, |Online notes |
|T day 17 | |Video 8: 5.1 |
| | |5.2 |
| | | |
|W day 18 |MIDTERM EXAM |Online, from book chapters 1 and 2. |
|(June 11 th) |9:00 a.m.-12:30 p.m. |Will be emailed to you by 9:00a.m., answers should be emailed back by |
| | |9:00 p.m. next day Thursday. |
|TH day 19 |Turing machines, turing |Chapter 3, Sipser’s book |
|And |decidable, turing recognizable,|Online notes |
|F day 20 |co-recognizable, tuting |Video 9: |
| |computable functions, Library |5.3 |
| |of turing machines |5.4 |
| | |5.5 |
| | | |
| | | |
|M day 21 |Turing machines, Turing |Chapter 3, Sipser’s book |
|And |decidable, Turing recognizable,|Online notes |
|T day 22 |co-recognizable, Turing |Video 9: |
| |computable functions, Library |6.1 |
| |of Turing machines |6.2 |
|W day 23 |Turing machines, turing |Chapter 3, Sipser’s book |
|And |decidable, turing recognizable,|Online notes |
|TH day 24 |co-recognizable, tuting |On Alan Turing: |
| |computable functions, Library | |
| |of turing machines | |
|F day 25 |Turing machines, turing |Video 10: 6.3 |
|And |decidable, turing recognizable,|6.4 |
|M day 26 |co-recognizable, tuting |6.5 |
|And |computable functions, Library | |
|T day 27 |of turing machines | |
|W day 28 |Decidability, halting problem |Chapter 4, Sipser’s book |
|And | |Online notes |
|TH day 29 | |Video 11: 7.1 |
|And | |7.2 |
|F day 30 | | |
|M day 31 |Undecidable problems, Rice’s |Chapter 5, Sipser’s book |
|And |Theorem |Online notes |
|T day 32 | |Video 11: |
|And | |7.3 |
|W day 33 | | |
|And | | |
|TH day 34 | | |
|F day 35 |Time complexity, P-class, |Chapter 7, Sipser’s book |
| |NP-class, NP completeness |Online notes |
| | |Video 12: 7.4 |
|M day 36 |Time complexity, P-class, |Chapter 7, Sipser’s book |
| |NP-class, NP completeness |Online notes |
| | |Video 13: |
| | |7.5 |
|T day 37 |Time complexity, P-class, |Chapter 7, Sipser’s book |
| |NP-class, NP completeness |Online notes |
| | |Video 13: |
| | |7.5 |
| | | |
|W day 38 |overview |Questions |
|TH day 39 |Evaluating what has been |Prepare for final. |
| |learned | |
|F day 40th |FINAL EXAM |Good luck on the exam. Will be emailed to you by 9:00 a.m. on this |
|(July 11th) |And HOMEWORK DUE |Friday, answers due back by 9:00 p.m. on the next day, Saturday. |
| | |Also HOMEWORK DUE by email by 9:00 a.m. |
Assessment
250 Points Total
100 points Midterm Exam
100 points Final Exam
50 points Homework assignments
Other links, interesting videos:
On Alan Turing:
Formal languages:
Universal Turing machine:
(Wolfram’s page)
Wolfram’s “A new kind of Science”:
Video 1: Chomsky on YouTube:
Video 2: Semantic Web, grammars and NLP,
CS 612 Youtube videos links
1.1
1.2
1.3
1.4
2.1
2.2
2.3
2.5
3.1
3.2
3.3
4.1
4.2
4.3
4.4
4.5
5.1
5.2
5.3
5.4
5.5
6.1
6.2
6.3
6.4
6.5
7.1
7.2
7.3
7.4
7.5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.