Course Schedule, CSCE A351

MS = Automata Textbook (Maheshwair & Smid)
CLRS = Algorithms Textbook (Cormen, Leiserson, Rivest, Stein)

Date Topic Reading Wk Additional Reading Notes
TR Jan 12,14

Introduction and Motivation

Mathematical Notation

Regular Languages: DFA

MS: Chap 1

 1

Intro: ppt, pdf

Finite Automata: ppt, pdf

Video: Lecture 1, Lecture 2

TR Jan 19,21

Mon, Jan 18: MLK Holiday

Regular Languages: DFA

 MS: Chap 2.1-2.3 2

DFAs

Video: Lecture 3, Lecture 4

Group Problem Set 1, Solutions 1

TR Jan 26,28

NFA's

Regular Expressions

MS: Chap 2.4-2.7

 3

Regular Expressions: ppt, pdf

Unix/Java RegEx: pdf, RegExprTest.java

Group Problem Set 2, Solutions 2

Video: Lecture 5, Lecture 6

TR Feb 2,4

Pumping Lemma I

Context-Free Grammars

 MS: Chap 2.8-2.9, 3.1-3.2
 4

Non-regular langs: pdf, ppt

Context-Free Grammars: pdf, ppt

Group Problem Set 3, Solutions 3

Video: Lecture 7, Lecture 8

TR Feb 9,11

Pushdown Automata

Pumping Lemma II 

MS: Chap 3.3-3.8

 5

Pushdown automata: pdf, ppt

Video: Lecture 9, Lecture 10

Group Problem Set 4, Solutions 4

TR Feb 16,18

Turing Machines

 		MS: Chap 4 6

Pumping Lemma II: pdf, ppt

Turing Machines: pdf, ppt

Group Problem Set 5, Solutions 5

Video: Lecture 11, Lecture 12

TR Feb 23,25

Turing Machines, Decidability

Decidability

Reducibility

MS: Chap 5

 7

Video: Lecture 13, Lecture 14

Group Problem Set 6, Solutions 6

Midterm Topics

P/NP

TR Mar 1,3

Time Complexity, P/NP

Midterm, Thursday, Mar. 3

 MS: Chap 6, CLRS: Chap 34 8

No Lecture 15

TR Mar 8,10

Complexity, Algorithm Basics, Notation

9

P/NP: pdf, ppt

Video: Lecture 16, Lecture 17

Group Problem Set 7, Solutions 7

TR Mar 15,17

Spring Break

CLRS: Chap 1-3 10 

.

TR Mar 22,24

Recurrence Relations

CLRS: Chap 4 11

Algorithm Basics

Recurrence Relations

Group Problem Set 8, Solutions

Video: Lecture 18, Lecture 19

TR Mar 29,31

Selection, Sorting

 		CLRS: Chap 6-9 12

Selection

Group Problem Set 9, Solutions

Video: Lecture 20, Lecture 21

TR Apr 5,7

Graphs, Shortest Path

CLRS: Chap 22-24,26

 13

Non-comparison-based Sorting

Graphs/Greedy: pdf, pptx

Group Problem Set 10, Solutions

Video: Lecture 22, Lecture 23

TR Apr 12,14

Dynamic Programming

CLRS: Chap 15, 25

 14

Max Flow: pdf, ppt

Dynamic Programming: pdf, Word

Group Problem Set 11, Solutions

Video: Lecture 24, No Lecture 25

TR Apr 19,21

String Matching, Other Topics? Voronoi Diagrams?

 CLRS: Chap 32 15

Group Problem Set 12, Solutions

Final Exam Topics

Video: Lecture 26, Lecture 27

T Apr 26

Final Exam Week (normal classes scheduled on Monday)

 

 . Finals Week

Final Exam Tuesday 10:00-12:45