CompSci 140, Spring 2012
Mathematical Foundations of CS
Syllabus

Monday Tuesday Wednesday Thursday Friday
1/9
1/10
1/11
1/12
First Day of Class
Review, Sets, Languages, Grammars
Lecture (slides), (handout)
No RQ due
Who am I?
Homework 1 out
1/13


Monday Tuesday Wednesday Thursday Friday
1/16
MLK day
1/17
Finite Automata
Lecture (slides), (handout)
Read Linz Chapter 1 (RQ 1)
RQ are on Sakai

1/18
1/19
Read Linz Chapter 2.1-2.2 (RQ 2)
classwork 1
Homework 2 out
1/20
1/23
1/24
Read Linz Chapter 2.3-2.4 (RQ 3)
1/25
1/26
Read Linz Chapter 3 (RQ 4)
Regular Expressions
Regular Grammars
Lecture (slides), (handout)
RQ 1, RQ 2 and RQ 3 due
Homework 3 out
Project 1 out
1/27
1/30
1/31
Read Linz Chapter 4.1-4.2 (RQ 5)
RQ 4 and RQ 5 due
2/1
2/2
Properties Regular Languages
Regular Pumping Lemma
Read Linz Chapter 4.3 (RQ 6)
Lecture (slides), (handout)
RQ 6 due
2/3


Monday Tuesday Wednesday Thursday Friday
2/6
2/7
Pushdown Automata
Read Linz Chap. 7.1(all), 7.3(first 2 pages)
Lecture (slides), (handout)
RQ 7 due
2/8
2/9
Context-Free Grammar
Brute-Force Parsing
Read Linz Chap. 5.1-5.2
Lecture (slides), (handout)
Homework 4 out
RQ 8 due
2/10
2/13
2/14
Equivalence NPDA/CFG
Read Linz Chap 5.3, 7.2-7.3
Lecture (slides), (handout)
RQ9 Due
2/15
2/16
Review
No RQ
2/17
2/20
2/21
Exam I
2/22
2/23
Parsing
Read JFLAP Chap 8.1-8.2
Lecture (slides), (handout)
No RQ due
2/24


Monday Tuesday Wednesday Thursday Friday
2/27
2/28
Read JFLAP Book Chap 8.1-8.3
LL Parsing
Lecture (slides), (handout)
RQ 10 Due
Test1 Solns
Homework 5 out
2/29
3/1
Transform Grammars
Lecture (slides), (handout)
No RQ due
3/2
3/5
3/6
Spring Break
3/7
3/8
Spring Break
3/9
3/12
3/13
LR Parse
Lecture (slides), (handout)
Read Linz Chap 6
Homework 6 out
Project 2 out
3/14
3/15
Properties CFL
CFL Pumping Lemma
Read Chapter 8 Linz
RQ 11 due(on Ch.6)
Lecture (slides), (handout)
3/16


Monday Tuesday Wednesday Thursday Friday
3/19
3/20
RQ 12 due (On Chap 8 Linz)
3/21
3/22
Turing Machines
Read Chapter 9 Linz
RQ 13 due
Lecture (slides), (handout)
classwork 3
3/23
3/26
3/27
Combining TM
Lecture (slides), (handout)
classwork 4
3/28
3/29
Read L-systems paper
L-Systems
Lecture
(handout)/Classwork 5
RQ 14 due
Homework 7 out
3/30
4/2
4/3
Other Models TM
Lecture (slides), (handout)
Read Chap 10.1-10.2
Do Test 2 Spring 2011
No RQ
4/4
4/5
Test 2 review
Read Chap 10.3-10.5 Linz
RQ 15 due
4/6
Project 3 out


Monday Tuesday Wednesday Thursday Friday
4/9
4/10
Exam II
4/11
4/12
Finish Chapter 10
Classwork 6
No RQ
4/13
4/16
4/17
Read Chapter 11.1-2
Classwork 7
Homework 8 out
NO RQ
Test2 soln (pdf)
4/18
4/19
Read Chapter 11.3-4
Recursively Enumerable
Unrestricted Grammar
Lecture (slides), (handout)
RQ 16 due
Classwork 8
4/20
4/23
4/24
Read Chapter 12.1
Lsystem Voting
RQ 17 due
Last Day of Class
Final Review
Lecture Compiler (slides), (handout)
scanner.l
parser.y
y.output
Lecture Decide
(slides), (handout)
souvenir
4/25
4/26
4/27


Monday Tuesday Wednesday Thursday Friday
4/30
5/1
Final Exam
9am-noon
5/2
5/3
5/4