CompSci 334, Fall 2024
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.

August 26-30 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
8/26
8/27

Topic: Introduction:

Read Course Webpages
QZ01 on Canvas

8/28
8/29

Topics: Sets, Languages, Grammars, Automata

Read LnzRgr: Chap. 1
QZ02 on Canvas due

8/30
LECTURE

First Lecture

LectureCh1 (slides)
(handout)

LectureCh1 (annotated)



Lecture 2

LectureCh2 (slides)
(handout)

LectureCh1 (annotated)

LectureCh2 (annotated)

JFLAP files (.zip)

ASSIGNMENT

Homework 1 out


September 2-6 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
9/2
9/3
Topics:
NFA,
NFA vs DFA

Read LnzRgr: Chap. 2.1-2.2

QZ03 due

9/4
9/5

Topics: Properties
DFA to Min DFA

Read LnzRgr Ch. 2.3-2.4
Read JFLAP Ch. 2.2

QZ04 due
9/6
LECTURE

Labor Day

Lecture 3

LectureCh2 (annotated)

Example Problem 1 - R1awb(.pdf)

JFLAP files (.zip)


Lecture 4

LectureCh2 (annotated)

JFLAP files (.zip)

Classwork 1 (.pdf)

ASSIGNMENT

Homework 1 due



Homework 2 out



September 9-13 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
9/9
9/10

Topics: Regular Expressions
Regular Grammars

Read LnzRgr Ch. 3

QZ05 due
9/11
9/12

Topics: Properties Regular Languages

Read LnzRgr Ch. 4.1-4.2

QZ06 due

9/13
LECTURE

Lecture 5

LectureCh3 (slides)
(handout)

LectureCh3 (annotated)

JFLAP files (.zip)


Lecture 6

LectureCh4 (slides)
(handout)

LectureCh4 (annotated)



See 9/19 for Exam 1 topics and old test suggestions

ASSIGNMENT

Homework 2 due

Homework 3 out


September 16-20 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
9/16
9/17

Topics: Regular Pumping Lemma

Read LnzRgr Ch. 4.3

QZ07 due

9/18
9/19
No Reading
NO QZ
9/20
LECTURE

Lecture 7

LectureCh4 (annotated)

Hw3 Hints (.pdf)

Classwork 2 (.pdf)



See 9/19 for Exam 1 topics and old test suggestions



Exam 1

Exam 1 Topics (webpage)

Relevant Old Exam 1's (webpage)

ASSIGNMENT

Homework 3 due



Project 1 out


September 23 - 27

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
9/23
9/24

Topics:
Pushdown Automata

Read LnzRgr Chapter 7.1, 7.3 (first 2 pages)

QZ08 due
9/25
9/26

Topics:
Context-Free Grammar
Brute-Force Parsing

Read LnzRgr Chap. 5.1-5.2

QZ09 due
9/27
LECTURE


Lecture 8

LectureCh7 Sec 1 (slides)
(handout)

Classwork 3 (.pdf)

LectureCh4 (annotated)

LectureCh7 (annotated)


JFLAP files (.zip)



Lecture 9

LectureCh5 (slides)
(handout)

LectureCh7 (annotated)

LectureCh5 (annotated)


JFLAP files (.zip)



ASSIGNMENT

September 30 - October 4 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
9/30
10/1

Topics:
NPDA/CFG

Read LnzRgr Chap. 5.3, Chap 7.2-7.3

QZ10 due

10/2
10/3

Topics:
Parsing, First and Follow

Read LnzRgr Chapter 15
OR JFLAP Book Chap 8.1

QZ11
10/4
LECTURE

Lecture 10

LectureCh7 Sec 2 (slides)
(handout)

LectureCh5 (annotated)

LectureCh7 Sec 2 (annotated)


JFLAP files (.zip)


Lecture 11

LectureCh15 (slides)
(handout)

LectureCh7 Sec 2 (annotated)

LectureCh15 (annotated)


JFLAP files (.zip)

ASSIGNMENT

Project 1 due

Homework 4 out


October 7-11 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
10/7
10/8

Topics: LL Parsing
Read LnzRgr Chapter 16
OR JFLAP Book 8.2

QZ12

10/9
10/10

Topics:
LR Parsing

Read LnzRgr Chapter 17 OR Read JFLAP Book Chap. 8.3

QZ13 due
10/11
LECTURE

Lecture 12

LectureCh16 (slides)
(handout)

LectureCh16 (annotated)


JFLAP files (.zip)


Lecture 13

LectureCh17 (slides)
(handout)

LectureCh17 (annotated)

Classwork 4 (.pdf) (annotated)

ASSIGNMENT

Homework 4 due

Homework 5 out


October 14-18 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
10/14
10/15
10/16
10/17

Continue LR Parsing

Review

No QZ

10/18
LECTURE
FALL BREAK FALL BREAK

Lecture 14

LectureCh17 (annotated)

Classwork 5 (.pdf)

ASSIGNMENT

Homework 5 due

Homework 6 out

Project 2 out


October 21-25 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
10/21
10/22
Topics:
Transforming Grammars

Read LnzRgr Chapter 6

QZ14 due
10/23
10/24

Topics:
CFL Properties

Read LnzRgr Chapter 8

QZ15 due
10/25
LECTURE

Lecture 15 LectureCh6 (slides)
(handout)


LectureCh6 (annotated)

Classwork 5 (annotated)

See 10/29 for Exam 2 materials


Lecture 16

LectureCh8 (slides)
(handout)


LectureCh6 (annotated)


LectureCh8 (annotated)

Example LR Parsing (annotated)

See 10/29 for Exam 2 materials

ASSIGNMENT

Homework 6 due

Project 2 Part 1 due


October 28 - November 1 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
10/28
10/29

No Reading,
No QZ

10/30
10/31
Topics:
Turing Machines

Read LnzRgr Chapter 9

QZ16 due
11/1
LECTURE


Exam 2

Exam 2 Logistics

Suggested Old Exam problems


Lecture 17


LectureCh8 (annotated)

ASSIGNMENT

November 4-8 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
11/4
11/5

No Reading

No Quiz
11/6
11/7

Topic: Turing Machine Models

Read LnzRgr Chapter 10.1-10.2

QZ17 due
11/8
LECTURE


Lecture 18

LectureCh9 (slides)
(handout)


LectureCh9 (annotated)

Classwork 6 (pdf) (discussed)




Lecture 19

LectureTMBB (slides)
(handout)


LectureTMBB (annotated)

Classwork 7 (pdf)
ASSIGNMENT

Project 2 Part 2 due



Homework 7 out



Project 3 out


November 11-15 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
11/11
11/12

Topic: L-Systems

Read L-systems paper

Or try this link

QZ18 due
11/13
11/14
Topic: More Turing Machines

Read LnzRgr Chapter 10.3-10.5

QZ19 due
11/15
LECTURE


Lecture 20

LectureLSystems (slides)
(handout)


LectureLSystems (annotated)

Classwork 8 (pdf)



Lecture 21

LectureCh10 (slides)
(handout)


LectureCh10 (annotated)

ASSIGNMENT



Homework 7 due



Homework 8 out


November 18-22 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
11/18
11/19


Topic: Recursively Enumerable Languages

Read LnzRgr Chapter 11.1-11.2

No RQ
11/20
11/21

Topic: Context-Sensitive Languages

Read LnzRgr Chapter 11.3-11.4

QZ 20 due
11/22
LECTURE

Lecture 22

LectureCh11 (slides)
(handout)


LectureCh10 (annotated)

LectureCh11 (annotated)

Classwork 9 (pdf)

Lecture 23

LectureCh11 (annotated)

Classwork 10 (pdf)
JFLAP files (.zip)

ASSIGNMENT

Homework 8 due



Homework 9 out



Project 3 due


November 25 - 29 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
11/25
11/26
11/27
11/28
11/29
LECTURE

No Class

Thanksgiving Break
Thanksgiving Break

Thanksgiving Break
ASSIGNMENT

December 2-6 Week

  Monday Tuesday Wednesday Thursday Friday
PRE-
WORK
12/2
12/3
Topic: Decidability

Read: LnzRgr Chap 12.1

QZ 21 due

12/4
12/5
12/6
LECTURE

Lecture 24

LectureCh12 (slides)
(handout)

LectureCompilers (slides)
(handout)


LectureCh11 (annotated)

LectureCh12 (annotated)

LectureCompilers (annotated)

scanner.l (textfile)

parser.y (textfile)

y.output (textfile)

We ate cookies

Souvenir



******
EXAM 3
******


Exam 3 Logistics


ASSIGNMENT

Homework 9 due



December Finals Week

 
FINAL
EXAM

No Final