▼CS420:   Intro to Theory of Computation
On this page:
CS420:   Intro to Theory of Computation
7.7
    ← prev  up  next → 

CS420: Intro to Theory of Computation

UMass Boston, Fall 2022

image Thu, 1 Sep 2022 00:00:00 -0400

Hi Students,

Welcome to CS420! I am looking forward to the semester.

To ensure a smooth start, please fill out this pre-class survey as soon as you can. (Enter your full umb.edu email into the Google sign-in box to access the survey. You may need to sign out of other accounts first, or open the link in an incognito window.) This way I can address any concerns as soon as possible.

Also, please note that CS220 (discrete math) is a requirement (and you will need it).

See you in the first class!

image

Last updated: Fri, 9 Dec 2022 16:49:55 -0500

Schedule (subject to change):

Lectures meet TuTh 11:00AM - 12:15PM EST, Wheatley W01-0034

Readings: S = Sipser; HMU = Hopcroft, Motwani, Ullmann

#

Date

Topic

Reading

HW out

1

9/6 Tue

Welcome to CS420 [slides]

S0.2-0.4, HMU1.2-1.4

0

2

9/8 Thu

Finite State Automata (FSM) [slides]

S1.1

3

9/13 Tue

Computing with FSMs [slides]

HMU2.2

4

9/15 Thu

Regular Languages [slides]

S1.1, HMU2.2

1

5

9/20 Tue

Combining FSMs, Closed Ops [slides]

S1.1, HMU2.2

6

9/22 Thu

Nondeterminism and NFAs [slides]

S1.2, HMU2.3,2.5

7

9/27 Tue

NFA -> DFA [slides]

S1.2, HMU2.3

2

8

9/29 Thu

Proofs Using NFAs [slides]

S1.2, HMU2.3

9

10/4 Tue

Regular Expressions [slides]

S1.3

3

10

10/6 Thu

Proof by Induction [slides]

S0.4,1.3, HMU1.4

no class

10/10 Mon

Indigenous Peoples Day

11

10/11 Tue

Non-Regular Languages [slides]

S1.4

4

12

10/13 Thu

Context-free Grammars (CFG) [slides]

S2.1, HMU5.1

13

10/18 Tue

Pushdown Automata (PDA) [slides]

S2.2, HMU6.1

5

14

10/20 Thu

CFL iff PDA, DPDAs [slides]

S2.2, HMU6.1

15

10/25 Tue

DPDAs and Parsing, non-CFLs [slides]

S2.3-2.4

6

16

10/27 Thu

Turing Machines (TMs) [slides]

S3.1-3.3

17

11/1 Tue

Nondeterministic TMs [slides]

S3.2

7

18

11/3 Thu

Decidability [slides]

S4.1

19

11/8 Tue

Decidability for CFLs [slides]

S4.1

8

20

11/10 Thu

Undecidability [slides]

S4.2,5.1, HMU9.3

no class

11/11 Fri

Veterans Day

21

11/15 Tue

Reducibility [slides]

S4.2,5.1, HMU9.3

9

22

11/17 Thu

Mapping Reducibility [slides]

S5.3, HMU9.5

23

11/22 Tue

Unrecognizability [slides]

S4.2,5.2-5.3, HMU9.5

10

no class

11/24 Thu

Thanksgiving Recess

24

11/29 Tue

Intro to Time Complexity [slides]

S7.1

25

12/1 Thu

P [slides]

S7.2-3

26

12/6 Tue

NP [slides]

S7.2-3

11

27

12/8 Thu

NP-Completeness [slides]

S7.3-4

28

12/13 Tue

Cook-Levin & NP-Complete Problems [slides]

S7.5

12

    ← prev  up  next →