Is there a problem that NO computer can ever solve?
What resources are needed to solve a problem?
Are some problems harder than others?
In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and contextfree grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.
Week  Monday  Tuesday  Wednesday  Thursday  Friday  Saturday  Sunday 

1  1/8 Introduction Regular expressions Sec 1.3 (Read) Slides Annotated (LecA), Annotated (LecB) 
1/9 Discussion: Lecture review 
1/10 DFA Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) 
1/11 Discussion: Chapter 0 review 
1/12 DFA design Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) 
HW Indiv0 Due 1/13 11pm Prerequisites PDF, source, style [Small typo fixed 1/8] Preclass survey 
1/14 Review Quiz Link 
2  1/15 No lecture MLK Day 
HW Indiv1 Due 1/16 11pm RegExp, DFA PDF, source, hw1.png, hw1.jff, style Discussion: Lecture review 
1/17 Closure Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) 
1/18 Discussion: RegExp, DFA 
1/19 NFA Sec 1.2 (Read) Slides Annotated (LecA), Annotated (LecB) 
Group HW1 Due 1/20 11pm RegExp, DFA PDF, source, style [Additional Hints added 1/17] 
1/21 Review Quiz Link 
3  1/22 NFA to DFA Sec 1.2 (Read) Slides Annotated (LecA), Annotated (LecB) 
HW Indiv2 Due 1/23 11pm Closure, NFA PDF, source, hw2_1.png, hw2_2.png, hw2_3.png, hw2_4.png, hw2_1.jff, hw2_2.jff, hw2_3.jff, hw2_4.jff, style Discussion: Lecture review 
1/24 Equivalence with RegExp Sec 1.3 (Read) Slides, Annotated (LecA), Annotated (LecB) 
1/25 Discussion: Closure, NFA 
1/26 Nonregular sets Sec 1.4 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW2 Due 1/27 11pm Closure, NFA PDF, source, style hw2_5.png, hw2_5.jff, 
1/28 Review Quiz Link 
4  1/29 Pumping Lemma Sec 1.4 (Read) Slides, Annotated (LecA), Annotated (LecB) 
HW Indiv3 Due 1/30 11pm Regular languages, PL PDF, source, hw3_1.png, hw3_2.png, hw3_3.png, hw3_4.png, hw3_1.jff, hw3_2.jff, hw3_3.jff, hw3_4.jff, style Discussion: Lecture review 
1/31 PDA Sec 2.2 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/1 Discussion: Regular languages, PL 
2/2 PDA Design Sec 2.2 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW3 Due 2/3 11pm Regular languages, PL PDF, source, (No new jff or png files), style 
2/4 Review Quiz Link 
5  2/5 CFG Sec 2.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/6 Discussion: Lecture review 
2/7 Exam 1 Practice questions 
Discussion: PDA, CFG 
2/9 CFL Sec 2.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/11 Review Quiz Link 

6  2/12 TMs: Formal def Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
HW Indiv4 Due 2/13 11pm PDA, CFG PDF, source, style 2/13 Discussion: Lecture review 
2/14 TMs: Implementation Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/15 Discussion: Turing machines 
2/16 TMs: Highlevel Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW4 Due 2/17 11pm PDA, CFG, CFL PDF, source, hw4_1.png, hw4_2.png, hw4_3.png, hw4_1.jff, hw4_2.jff, hw4_3.jff style 
2/18 Review Quiz Link 
7  2/19 No lecture Presidents' Day 
HW Indiv5 Due 2/20 11pm TM: formal, implementation PDF, source, style Discussion: Lecture review 
2/21 ChurchTuring thesis Sec 3.2 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/22 Discussion: Decidability, closure 
2/23 Algorithms Sec 3.3 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW5 Due 2/24 11pm TM: formal, implementation PDF, source, hw5TM.png, hw5TM.jff, style  2/25 Review Quiz Link 
8  2/26 Decidable langs Sec 4.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
2/27 Discussion: Lecture review 
2/28 Undecidability Sec 4.2 (Read) Slides, Annotated (LecA), Annotated (LecB) 
3/1 Discussion: Lecture review 
3/2 Exam 2 Practice questions 
3/4 Review Quiz Link 

9  3/5 Reductions Sec 5.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
HW Indiv6 Due 3/6 11pm Highlevel descriptions, decidability PDF, source, style Discussion: Closure 
3/7 Reductions Sec 5.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
3/8 Discussion: Indiv6 review 
3/9 Reductions Sec 5.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW6 Due 3/10 11pm Highlevel descriptions, decidability PDF, source, style 
3/11 Review Quiz Link 
10  3/12 Time complexity Sec 7.1 (Read) Slides, Annotated (LecA), Annotated (LecB) 
HW Indiv7 Due 3/13 11pm Undecidability, reductions PDF, source, style Discussion: Lecture review 
3/14 P vs. NP Sec 7.1, 7.2 (Read) Slides, Annotated (LecA), Annotated (LecB) 
Group HW7 Due 3/15 11pm Undecidability, reductions PDF, source, style Discussion: Review 
3/16 Review Sec 5.1 (Read) Slides, Annotated (LecA), Annotated (LecB) Optional HW Indiv8 PDF, source, style Review Quiz Link (Complete by 3/17 11pm for credit) 
Final exam Saturday 3/17 11:30am2:29pm Practice questions 
Upon successful completion of this course, you will be able to:
We are looking forward to working with you this quarter.
Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/winter2018/cse105).
Our office hours and locations can be found in the calendar above.
For private questions to Prof. Minnes, you can reach me at minnes@eng.ucsd.edu
The required textbook for this course is
This book is available at the Bookstore for under $20 and is also on reserve in the library. You will need the book to complete preclass reading before each lecture period.
To brush up on proofs, use: Richard Hammack, Book of Proof, 2nd ed. (available for download here)
An iClicker2 is also required, and is available for purchase at the bookstore. Register your iClicker here.
Prerequisites
Reading Sec 0.2, 0.3, 0.4: In particular, review the definitions of set, element, subset,
infinite set, proper subset, natural numbers, integers, empty set, union, intersection, complement, sequence,
Cartesian product, function, domain, range, graph, selfloop, alphabet, symbol, string over an alphabet,
length, empty string, substring, concatenation, lexicographic order, shortlex/string order, prefix,
proof by contradiction.
Optional extra practice: Chapter 0 Exercise # 1, 2, 3, 4, 5, 6.
Regular expressions
Reading Sec 1.3: Def 1.52 of regular expressions (p. 64), example 1.53 (p. 65)
Optional extra practice: Chapter 1 Exercise # 20
DFA
Reading Sec 1.1: Figure 1.4 (p. 34), Definition 1.5 (p. 35)
Optional extra practice: Chapter 1 Exercise # 1, 2, 3
Closure operations (Wednesday)
Reading Pages 4547 (paragraph before Theorem 1.25 and Theorem 1.25 and its proof).
Optional extra practice Chapter 1 Exercise # 4, 5
Nondeterminism (Friday)
Reading Page 48 (Figure 1.27 and description below it), Example 1.35 on page 52.
Optional extra practice Chapter 1 Exercise # 7, 9
NFA to DFA (Monday)
Reading Pages 55 paragraph that starts "Recall the "reader as automaton"..." and Example 1.41 on pages 5658..
Optional extra practice Chapter 1 Exercise # 13, 14, 16
NFA to RegExp (Wednesday)
Reading Example 1.56 on page 68.
Optional extra practice Chapter 1 Exercise # 7, 17
Nonregular sets (Friday)
Reading Page 77.
Optional extra practice Chapter 1 Exercise # 30
Pumping Lemma (Monday)
Reading Example 1.75 (page 81) and Example 1.77 (page 82)
Optional extra practice Chapter 1 Exercise # 29, 30
PDA (Wednesday)
Reading Informal description of PDA on pages 111112.
PDA Design (Friday)
Reading Example 2.16 (page 115) and Example 2.18 (page 116)
Optional extra practice Chapter 2 Exercise # 5
Contextfree grammars> (Monday)
Reading Intro to section 2.1 (pp. 102103)
Optional extra practice Chapter 2 Exercise # 2,4
Contextfree languages (Friday)
Reading Designing CFGs (pp. 106107), Ambiguity Definition 2.7 (p. 108)
Optional extra practice Chapter 2 Exercise # 15
Turing Machines (Monday)
Reading Pages 166167 on differences between finite automata and Turing machines.
Turing machines (Wednesday)
Reading Example 3.7 on page 171, Example 3.9 page 173.<
Optional extra practice Chapter 3 Exercise # 2
Turing machines (Friday)
Reading Bottom of page 166 and top of page 167 (highlevel and implementation level definitions of M1),
then terminology for describing Turing machines pages 184185
Optional extra practice Chapter 3 Exercise # 7,8
Variants of Turing machines (Wednesday)
Reading Section 3.2, especially "Equivalence with other models" on page 181.
Optional extra practice Chapter 3 Exercise # 18
Computational problems (Friday)
Reading Format and notation for describing Turing machines, middle of page 185
Optional extra practice Chapter 3 Exercise # 15, 16; Chapter 4 Exercise # 1
Decidable problems (Monday)
Reading Section 4.1, Theorem 4.5 (page 197) and Theorem 4.8 (page 199)
Optional extra practice Chapter 4 Exercise # 3,5
Undecidability (Wednesday)
Reading Section 4.2 page 207209
Optional extra practice Chapter 4 Exercise # 7,8
Reductions (Monday)
Reading Section 4.2 Theorem 4.22, Section 5.1 Theorem 5.1
Reductions (Wednesday)
Reading Section 5.1 Theorem 5.2
Reductions (Friday)
Reading Section 5.1 Theorem 5.3, 5.4
Optional extra practice Chapter 5 Exercise # 18 (without Rice's theorem)
Complexity: P and NP (Monday)
Reading Section 7.1 example at the top of page 279, Theorem 7.8, Theorem 7.11; Section 7.2 Definition 7.12, Theorem 7.14;
Section 7.3 Theorem 7.24
Optional extra practice Chapter 7 Exercise # 6, 7, 8, 10
NPcompleteness (Wednesday)
Reading Section 7.1 example at the top of page 279, Theorem 7.8, Theorem 7.11; Section 7.2 Definition 7.12, Theorem 7.14;
Section 7.3 Theorem 7.24
Optional extra practice Chapter 7 Exercise # 5, read through sample solution of 28