Lectures

Schedule:

Detailed Information:

Note

Sometimes (for reasons we haven’t figured out yet) the annotated notes show up with blank pages on browsers, but are fine when downloaded. If you see blank pages, please download the notes and view them on your computer. If there are still blank pages after downloading, post on Campuswire.

Date Topic Lecture Notes References
01/21 Lecture 01 (Umrawal)
Course introduction and preliminaries

Lec 01

Note 01

 [SITC] - Ch. 0
01/23 Lecture 02 (Umrawal)
Proof techniques and introduction to languages

Lec 02

Note 02

 [SITC] - Ch. 0
01/28 Lecture 03 (Umrawal)
Deterministic finite automata (DFAs) and regular languages

Lec 03

Note 03

 [SITC] - Ch. 1
01/30 Lecture 04 (Umrawal)
Non-deterministic finite automata (NFAs)

Lec 04

Note 04

 [SITC] - Ch. 1
02/04 Lecture 05 (Umrawal)
Regular Expressions (RegExs)

Lec 05

Note 05

 [SITC] - Ch. 1
02/06 Lecture 06 (Umrawal)
Equivalence of DFAs/NFAs/RegExs

Lec 06

Note 06

 [SITC] - Ch. 1
02/11 Lecture 07 (Abraham)
Non-regularity and fooling sets

Lec 07

 Note 07
Extra 07		 [SITC] - Ch. 1,
[JEMC] - Ch. 3
02/13 Midterm 1
In-class midterm covering Lectures 01 - 06
02/18 Lecture 08 (Abraham)
Context-free grammars and context-free languages

Lec 08

 Note 08
Extra 08		 [SITC] - Ch. 2,
[JEMC] - Ch. 5
02/20 Lecture 09 (Abraham)
Push-down automata

Lec 09

 Note 09
Extra 09		 [SITC] - Ch. 2
02/25 Lecture 10 (Abraham)
Turing machines

Lec 10

Note 10

 [SITC] - Ch. 3,
[JEMC] - Ch. 6
02/27 Lecture 11 (Abraham)
Universal Turing machines

Lec 11

Note 11

 [SITC] - Ch. 3,
[JEMC] - Ch. 6
03/04 Lecture 12 (Umrawal)
Reductions and recursions

Lec 12

Note 12

 [JEAL] - Ch. 1
03/06 Lecture 13 (Umrawal)
Divide & conquer and selection algorithms

Lec 13

Note 13

 [JEAL] - Ch. 1
03/11 Lecture 14 (Umrawal)
Backtracking

Lec 14

Note 14

 [JEAL] - Ch. 2
03/13 Midterm 2
In-class midterm covering Lectures 07 - 13
03/25 Lecture 15 (Umrawal)
Dynamic programming I

Lec 15

Note 15

 [JEAL] - Ch. 3
03/27 Lecture 16 (Umrawal)
Dynamic programming II

Lec 16

Note 16

 [JEAL] - Ch. 3
04/01 Lecture 17 (Abraham)
Graphs and basic search

Lec 17

Note 17

 [JEAL] - Ch. 5
04/03 Lecture 18 (Abraham)
Directed graphs

Lec 18

Note 18

 [JEAL] - Ch. 5, 6
04/08 Lecture 19 (Abraham)
Shortest paths I

Lec 19

 Note 19
Extra 19		 [JEAL] - Ch. 8
04/10 Lecture 20 (Abraham)
Shortest paths II

Lec 20

Note 20

 [JEAL] - Ch. 9
04/15 Midterm 3
In-class midterm covering Lectures 14 - 19
04/17 Lecture 21 (Abraham)
Minimum spanning trees

Lec 21

Note 21

 [JEAL] - Ch. 7
04/22 Lecture 22 (Umrawal)
Reductions

Lec 22

Note 22

 [JEAL] - Ch. 12
04/24 Lecture 23 (Umrawal)
NP complete problems and reductions I

Lec 23

Note 23

 [JEAL] - Ch. 12
04/29 Lecture 24 (Umrawal)
NP-complete problems and reductions II

Lec 24

Note 24

 [JEAL] - Ch. 12
05/01 Lecture 25 (Umrawal)
Decidability

Lec 25

Note 25

 [JEMC] - Ch. 7
05/06 Midterm 4
In-class midterm covering Lectures 20 - 25