IMPORTANT: Everyone MUST read the Course Policies listed HERE .
This course requires you to run Jupyter notebooks and run the “Jove” automata package I’ve developed and provided at https://github.com/ganeshutah/Jove.git
Here is how to run Jove under Jupyter notebooks and have fun learning:
We will keep Youtube video recordings:
Date of lecture | Topics Covered Read these before class | Work assigned, Resources Due date shown as [on ...] |
1: 8/21/18 | 1.1-1.5: What Machines Think 2.1-2.2.6: Languages
| Quiz-1 [on 8/26] Asg-1 [on 9/9] |
2: 8/23/18 | 2.3: Languages 3.1-3.4: Kleene Star | |
3: 8/28/18 | 3.5-3.6: Kleene Star, Enumeration 4.1-4.2: DFA as machines
(the Jove notebook is on Github under asgjove/Asg1) | Quiz-2 [on 9/3] |
4: 8/30/18 | 4.3-4.5: DFA for defining languages
|
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
5: 9/4/18 | 4.6-4.9: Pumping Lemma DFA building: plz see this video Pumping a Phone: plz see this video
| Quiz-3 [on 9/13]
|
6: 9/6/18 | 5: Designing DFA
| Asg-2 [on 9/26] Please note new date. This is to help discuss the solutions of Asg-2 in class before Midterm-1. |
7: 9/11/18 | 6: Operations on DFA
| Quiz-4 [on 9/17] |
8: 9/13/18 | 7.1-7.7: NFA
|
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
9: 9/18/18 | 8.1-8.5: RE | Quiz-5 [9/24] |
10: 9/20/18 | 8.6-8.8: RE 9: NFA to RE See Lec9 slides also; more below |
|
11: 9/25/18 | Slack (to catch up) 10: Derivatives (briefly) - skipped Review for Midterm-1 | Quiz-6 [on 10/1] |
12: 9/27/18 | Review for Midterm-1 Pdf after lecture |
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
13: 10/2/18 | Midterm-1 [in class] | Asg-3 [on 10/28] |
14: 10/4/18 | 11.1-11.4: CFGs and CFL IMPORTANT! Asg3 will involve this |
|
Fall Break | ||
15: 10/16/18 | 11.5-11.8: CFGs and CFL | Quiz-7 [on 10/22] |
16: 10/18/18 | 11.9-11.10: More on CFL Design CFL Pumping Lemma (begin)
| Asg-4 [on 11/7] |
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
17: 10/23/18 |
| Quiz-8 [on 11/03] Will be worth 1.5x quiz pts |
18: 10/25/18 | More on CFL Design CFL Pumping Lemma (begin)
|
|
19: 10/30/18 | Finish the CFL Pumping Lemma 12.1-12.3: PDA | |
20: 11/1/18 | 12.4-12.6: PDA construction 12.7: Practical Parsers | Quiz-9 [on 11/12] |
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
21: 11/6/18 | Chapter 13 : Basics of TMs 13.7: Chomsky Hierarchy --- Begin Review for Midterm-2 Problems and solutions on Canvas | |
22: 11/8/18 | Continue Review for Midterm-2 |
|
23: 11/13/18 | Midterm-2 [in class] |
|
24: 11/15/18 | 13.4-13.6: Construction of DTM and NDTM, Nondet. Runtime 14.1-14.3: Recursive and RE Lecture Slides Before Class Lecture Slides After Class [.pdf] LINK to JFLAP that works for NDTM is here (save JAR file and run it) Here is the w#w DTM I ran Here is the ww NDTM I ran | Quiz-10 should be up here on 11/16/18 [ Due on 12/03 ] Asg-5 should be up here on 11/16/18 [Due on 12/09] THIS IS THE LAST ASG Due Sunday 12/09 midnight |
Date of lecture | Topic | Work assigned, Resources Due date shown as [on ...] |
25: 11/20/18 | Direct discussion of Asg-5 and Quiz-10
| |
Thanksgiving Break | ||
26: 11/27/18 | 15.3-15.5: Halting, Acceptance, Mapping Reductions Lecture Slides for Ch15 Lecture Slides for Ch16 | Quiz-11 [ on 12/06 ] THIS IS THE LAST QUIZ |
27: 11/29/18 | 16.1-16.4: NP-Completeness
| |
28: 12/4/18 | 16.5 - 16.8 : NP-Completeness |
|
29: 12/6/18 | Review for Final Exam Lecture Slides | |
12/11/18 | Final Exam [10:30am - 12:30pm] |