CompSci 334, Spring 2021
Mathematical Foundations of CS
CompSci 334 Calendar

All materials we use in class are accessible via this page.

This is a temporary schedule for what we will do, subject to change!

Information about grading and course logistics.

January 18-22 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
1/18
MLK Day
1/19
1/20
1/21
Topics: Review Sets
Languages
Grammars
Automata


No Reading
No RQ
1/22
LECTURE
First Lecture

Lecture 1

Lecture (slides)
(handout)

(annotated)

Lecture Video posted in
Sakai under Resources
ASSIGNMENTS
HOMEWORK
DUE
Homework 1 out

January 25-29 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
1/25
1/27
Topics: Finite Automata
NFA

Read Linz Chapter 1
Sakai Quiz (RQ01)
is on Sakai
1/26
1/28
Topics: NFA, NFA vs DFA
Read Linz Chap 2.1-2.2

RQ02 on Sakai
1/29
LECTURE
Lecture 2

Lecture Finite Automata(slides)
(handout)


Intro notes(annotated)

Finite Automata notes(annotated)


jflapfiles0126.zip

Lecture Video posted in Sakai under Resources
Lecture 3

Classwork 1

Finite Automata notes(annotated)


jflapfiles0128.zip

Lecture Video posted in Sakai under Resources
ASSIGNMENTS
HOMEWORK
DUE
Homework 1 due
Homework 2 out

February 1-5 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
2/1
2/2
Topics: Properties
DFA to Min DFA

Read Linz Ch. 2.3-2.4

RQ03 in Sakai
2/3
2/4
Topics: Regular Expressions
Regular Grammars

Read Linz Ch. 3

RQ04 on Sakai
2/5
LECTURE
Lecture 4

Finite Automata notes(annotated)


jflapfiles0202.zip

Example Writeup Problem1

Lecture Video posted in Sakai under Resources
Lecture 5

Lecture Regular Languages(slides)
(handout)

Regular Languages notes(annotated)


jflapfiles0204.zip

Lecture Video posted in Sakai under Resources
ASSIGNMENTS
HOMEWORK
DUE
Homework 2 due
Homework 3 out
Project 1 out

February 8-12 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
2/8
2/9
Topics: Properties Regular Languages

Read Linz Ch. 4.1-4.2

RQ05 on Sakai
2/10
2/11
Topics: Regular Pumping Lemma

Read Linz Ch. 4.3

RQ06 on Sakai
2/12
LECTURE
Lecture 6

Lecture Regular Properties(slides)
(handout)

Regular Languages notes(annotated)


Regular Properties notes(annotated)


Lecture Video posted in Sakai under Resources
Lecture 7


Regular Properties notes(annotated)


HW3 hints(pdf)


Lecture Video posted in Sakai under Resources
ASSIGNMENTS
HOMEWORK
DUE
Homework 3 due

February 15-19 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
2/15
2/16
Topic: Pushdown Automata

Read Linz Ch. 7.1(all), 7.3(first 2 pages)

RQ07 on Sakai
2/17
2/18



2/19
LECTURE
Lecture 8

Lecture Pushdown Automata(slides)
(handout)


Classwork 2
Classwork 2 with hints
Turn in Classwork 2, Problem 1 by Friday night

Regular Properties notes(annotated)

Pushdown Automata notes(annotated)

jflapfiles0216.zip

Lecture Video posted in Sakai under Resources

Exam 1
Covers Chapters 1-3 in Linz book
Covers Chapter 1-4 in JFLAP book

Exam 1 info



ASSIGNMENTS
HOMEWORK
DUE

February 22-26 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
2/22
2/23
Topics:
Context-Free Grammar
Brute-Force Parsing

Read Linz Chap. 5.1-5.2

RQ08 in Sakai

2/24
2/25
Topics:
Equivalence NPDA/CFG

Read Linz Chap 5.3, 7.2-7.3

RQ09 in Sakai

2/26
LECTURE
Lecture 9

Lecture Context-free Languages(slides)
(handout)

Pushdown Automata notes(annotated)

CFL notes(annotated)

jflapfiles0223.zip

Lecture Video posted in Sakai under Resources
Lecture 10

Lecture Pushdown Automata Part 2(slides)
(handout)

CFL notes(annotated)

Pushdown Automata Part 2 notes(annotated)

jflapfiles0225.zip

Lecture Video posted in Sakai under Resources



ASSIGNMENTS
HOMEWORK
DUE
Project 1 due
Homework 4 out

March 1-5 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
3/1
3/2
General Parsing
LL Parsing

Read JFLAP Book 8.1-8.2

RQ10 in Sakai
3/3
3/4

LL Parsing

No RQ

3/5
LECTURE
Lecture 11
Lecture Parsing (slides)
(handout)

Pushdown Automata Part 2 notes(annotated)

Parsing notes(annotated)

jflapfiles0302.zip

Lecture Video posted in Sakai under Resources


Lecture 12

Lecture LL Parsing (slides)
(handout)


LL Parsing notes(annotated)

Lecture Video posted in Sakai under Resources


ASSIGNMENTS
HOMEWORK
DUE
Homework 4 due
Homework 5 out

March 8-12 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
3/8
3/9
NO CLASS

3/10
NO CLASS

3/11
LR Parsing

Read JFLAP Book 8.3

RQ11 in Sakai

3/12
LECTURE
NO CLASS


NO CLASS

Lecture 13

Lecture LR Parsing (slides)
(handout)

LR Parsing notes(annotated)

Lecture Video posted in Sakai under Resources


ASSIGNMENTS
HOMEWORK
DUE
Project 2 out

March 15-19 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
3/15
3/16
Transforming Grammars

Read Linz Chapter 6

RQ12 on Sakai
3/17
3/18

CFL Properties

Read Linz Chapter 8


RQ13 on Sakai
3/19
LECTURE
Lecture 14

Lecture Transform Grammars (slides)
(handout)

LR Parsing notes(annotated)

Transform Grammars notes(annotated)

Lecture Video posted in Sakai under Resources


Lecture 15

Lecture CFL Properties (slides)
(handout)

Transform Grammars notes(annotated)

CFL Props notes(annotated)


jflapfiles0318.zip

Exam 2 info

Lecture Video posted in Sakai under Resources
ASSIGNMENTS
HOMEWORK
DUE
Homework 5 due
Homework 6 out
Project 2 Part 1 due

March 22-26 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
3/22
3/23


Finish CFL Properties
No RQ

3/24
3/25


3/26
LECTURE
Lecture 16

CFL Props notes(annotated)


Lecture Video posted in Sakai under Resources

Exam 2

Exam 2 info

ASSIGNMENTS
HOMEWORK
DUE
Homework 6 due

March 29-April 2 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
3/29
3/30

Turing Machines

Read Chapter 9 Linz

RQ 14 on Sakai
3/31
4/1
L-Systems
Read L-systems paper

Or try this link

RQ 15 on Sakai
4/2
LECTURE
Lecture 17


Lecture Turing Machines (slides)
(handout)

CFL Props notes(annotated)

Turing Machines notes(annotated)




Lecture 18

Lecture L-Systems (slides)
(4up)

Turing award - Ullman and Aho

Turing Machines notes(annotated)

L-Systems notes(annotated)

jflapfiles0401.zip



ASSIGNMENTS
HOMEWORK
DUE
Project 2 Part 2 due
Homework 7 out
Project 3 out

April 5-9 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
4/5
4/6
Read Chap 10.1-10.2 Linz book

RQ16

4/7
4/8
Read Chap 10.3-10.5 Linz book

RQ17

4/9
LECTURE
Lecture 19


Lecture TM Other Models (slides)
(handout)

TM Other Models notes(annotated)

jflapfiles0406.zip

Lecture Video posted in Sakai under Resources
Lecture 20


TM Other Models notes(annotated)

Lecture Video posted in Sakai under Resources


ASSIGNMENTS
HOMEWORK
DUE
Homework 7 due

April 12-16 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
4/12
Wellness Day

4/13
Read Linz Chapter 11.1-11.2

No RQ
4/14
4/15
Read Linz Chapter 11.3-11.4

RQ 18 on Chap 11.1-11.4
4/16
LECTURE


Lecture 21


Lecture Rec Enum Languages (slides)
(handout)

TM Other Models notes(annotated)

Rec Enum Lang notes(annotated)

jflapfiles0413.zip

Lecture Video posted in Sakai under Resources


Lecture 22

Rec Enum Lang notes(annotated)

Python List as Tree (pdf)

Lecture Video posted in Sakai under Resources



ASSIGNMENTS
HOMEWORK
DUE
Homework 8 out
Project 3 due

April 19-23 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
4/19
4/20

Read Linz Chapter 12.1-2

RQ19
4/21
4/22


4/23
LECTURE
Lecture 23
Last Lecture

In Person and Zoom
Lecture Decidability (slides)
(handout)

Lecture Compilers (slides)
(handout)

scanner.l
parser.y
y.output

Rec Enum Lang notes(annotated)

Decidability Notes(annotated)

Compilers notes(annotated)

Lecture Video posted in Sakai under Resources

Exam 3

Exam 3 info
ASSIGNMENTS
HOMEWORK
DUE
Homework 8 due

April 26-30 Week

  Monday Tuesday Wednesday Thursday Friday
FINAL
EXAM
WEEK
4/26
Reading Day

4/27
4/28
4/29
NO FINAL EXAM
4/23