Theoretical Computer Science

Lectures	TOPIC ( Click to Download PPT)
Lec 1	0: Overview, mathematical notation, proof by induction ( pdf, ppt)
Lec 2	0 and 1: Strings, String Operations, Languages (pdf, ppt)
Lec 3 & 4	1.1:Introduction to Deterministic Finite Automata(DFA) , formal definition of a DFA, simple examples of DFA's (pdf, ppt)
Lec 3 & 4	1.1: Designing Finite Automata, formal definition of computation (pdf, ppt)
Lec 5	1.1/1.2: Regular operations on Languages, Union closure of regular languages, motivation for and introduction to Nondeterministic Finite Automata (NFA) (pdf, ppt)
Lec 6	1.2: Examples of NFA's, Introduction to converting NFA's to DFA's (pdf, ppt)
Lec 7	1.2: Converting NFA's to DFA's (pdf, ppt)
Lec 8	1.2: Closure of Regular Languages (pdf, ppt)
Lec 9	1.3: Regular Expressions (pdf, ppt)
Lec 9	1.3: Regular Expressions (pdf, ppt)
Lec	Regular Expressions and JFLAP SOFTWARE, GREP INTRODUCTION(ppt)
Lec	1.3:Regular Expressions and GNFA (ppt)
Lec 10 & 11	1.4: Non-Regular Languages/Pumping Lemma part 1: (ppt) part 2: (ppt)
Lec	Pumping Lemma Examples: (ppt) Is { a^(2n) | n > 0 } non-regular? (ppt)
Lec 11	2.1: Context Free Grammars part 1: (ppt) part 2: (ppt)
Lec 11 & 12	2.1 CFG part 1: (ppt) part 2: (ppt)
Lec 13	2.2: Pushdown Automata (PDA) (ppt)
Lec 14	2.2: Pushdown Automata (PDA) (ppt)
Lec 14	2.2: Pushdown Automata (PDA), Chomsky Normal Form (CNF) (ppt)
Lec 14	2.3/2.4: Non-Context Free Languages (ppt) Mid-Semester Course Evaluation (ppt)
Lec 14 & 15	2.3/2.4: Non-Context Free Languages (ppt) (ppt)
Lec 16	Parsing Introduction (Handout): (ppt)
Lec 17	Parsing Introduction (Handout): (ppt) Construction of LL(1) parsing table. "Common prefixes" and "left recursion" problems.
Lec 18	LL(1) Parsing, Shift/Reduce Parsing (ppt) (JFLAP examples: 1, 2, 3, 4)
Lec 19	Lex & Yacc (ppt) Examples
Lec	Linux Command line (ppt)
Lec 20	3.1: Turing Machines, Basic Examples, Formal Definition (ppt)
Lec 21	3.2: Turing Machines, More examples, Multitape machines (ppt)
Lec 22	4.1: Decidability, Examples of Decidable languages (ppt)
Lec 23	4.2 Halting Problem (ppt)
Lec 23	4.2 Halting problem (ppt) JFLAP Turing Machines (ppt)
Lec 24	7.1: Time Complexity Introduction, big-O notation (ppt)
Lec 25	7.2: Class P of languages, examples (ppt)