Lectures

Schedule:

Detailed Information:

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
03/06 Lecture 13 (Umrawal)
Divide & conquer and selection algorithms

Lec 13

Note 13
03/11 Lecture 14 (Umrawal)
Backtracking

Lec 14

Note 14
03/13 Midterm 2
In-class midterm covering Lectures 07 - 13
03/25 Lecture 15 (Umrawal)
Dynamic programming I

Lec 15

Note 15
03/27 Lecture 16 (Umrawal)
Dynamic programming II

Lec 16

Note 16
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

 [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
04/24 Lecture 23 (Umrawal)
NP complete problems and reductions I

Lec 23

Note 23
04/29 Lecture 24 (Umrawal)
NP-complete problems and reductions II

Lec 24

Note 24
05/01 Lecture 25 (Abraham)
Decidability

Lec 25

Note 25
05/06 Midterm 4
In-class midterm covering Lectures 20 - 25