CompSci 140, Spring 2010
Mathematical Foundations of CS
Syllabus

Monday Tuesday Wednesday Thursday Friday
1/11
1/12
1/13
1/14
First Day of Class
Review, Languages, Grammars
Lecture (slides), (handout)
Who am I?
Homework 1
1/15


Monday Tuesday Wednesday Thursday Friday
1/18
MLK day
1/19
Finite Automata
Read Linz Chapter 1
RQ 1 due
RQs are due before class starts
RQs are on blackboard
Lecture (slides), (handout)
1/20
1/21
Finite Automata
Read Linz Chapter 2.1-2.2
RQ 2 due
Homework 2 out
new groups
1/22
1/25
1/26
Read Linz Chapter 2.3-2.4
RQ 3 due
1/27
1/28
Read Linz Chapter 3
RQ 4 due
Homework 3 out
Project 1 out
Regular Grammars and Expressions
Lecture (slides), (handout)
1/29
2/1
2/2
Read Linz Chap 4.1-4.2
RQ 5 due
Pumping Lemma and Reg. Props.
Lecture (slides), (handout)
2/3
2/4
Regular Properties
Read Linz Chap 4.3
RQ 6 due
new groups
Classwork 2
2/5


Monday Tuesday Wednesday Thursday Friday
2/8
2/9
Read Linz Chap 7.1(all), 7.3(only pages 195-196)
RQ 7 due
NPDA
Lecture (slides), (handout)
2/10
2/11
Read Chapter 5.1-5.2
Reading Quiz 8 Due
Context-free Grammar
Lecture (slides), (handout)
Homework 4
2/12
2/15
2/16
Compare CFG to NPDA
Read Chap. 5.3, Chap.7.2-7.3
Reading Quiz 9 due
Lecture (slides), (handout)
Test 1 S09
2/17
2/18
Review
No Reading quiz
2/19
2/22
2/23
Exam I
2/24
2/25
Lecture Parsing (slides), (handout)
Lecture LL Parsing
(slides), (handout)
Read JFLAP book 8.1-8.2
Reading quiz 10 due
2/26


Monday Tuesday Wednesday Thursday Friday
3/1
3/2
Lecture LR Parsing (slides), (handout)
Homework 5 out
3/3
3/4
TODAY MEET in LSRC D344
No RQ
3/5
3/8
3/9
Spring Break
3/10
3/11
Spring Break
3/12
3/15
3/16
Read Linz Chapter 6
No RQ due
Transform Grammars (slides), (handout)
Homework 6 out
Project 2 out
3/17
3/18
TODAY MEET IN LSRC D344
RQ 11 due on Chapter 6
CFL Pump Lemma (slides), (handout)
3/19


Monday Tuesday Wednesday Thursday Friday
3/22
3/23
RQ 12 due
Read Chapter 8
Turing Machines
(slides), (handout)
3/24
3/25
Read Chapter 9
RQ 13 due
Classwork 3 (turned in during class)
3/26
3/29
3/30
No RQ due
BB Turing Machines
(slides), (handout)
Classwork 4
3/31
4/1
Read L-systems paper

L-systems (slides) (handout)
(files)
RQ due
Classwork 5
Homework 7 out
4/2
4/5
4/6
Models of TM
Read Linz Chapter 10.1-2
NO RQ due
(slides), (handout)
Test2 Spring2009
4/7
4/8
Read Linz Chapter 10.3-5
RQ on Chapter 10 due
Review
Test 2 review
Project 3 out
4/9


Monday Tuesday Wednesday Thursday Friday
4/12
4/13
Exam II
4/14
4/15
Classwork 6
4/16
4/19
4/20
Read Linz Chapter 11
RQ due
(slides), (handout)
4/21
4/22
Decidability
(slides), (handout)
4/23
4/26
4/27
Read Chapter 12.1 Linz
Reading Quiz due
Last Day of Class
Compilers (slides), (handout)
scanner.l
parser.y
y.output
Final Review
VOTE for Lsystems by 5pm Apr 30
A souvenir
4/28
4/29
4/30


Monday Tuesday Wednesday Thursday Friday
5/3
5/4
5/5
5/6
Final Exam SATURDAY
May 8, 9am-noon
5/7