Chapter 1 ■ Mathematical Data Types
1.5 UNION, INTERSECTION, DIFFERENCE, COMPLEMENT
1.8 TUPLES AND CARTESIAN PRODUCTS
1.12 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 2 ■ Deterministic Finite Automata
2.3 FORMAL DEFINITION OF A DFA
2.9 CHAPTER SUMMARY AND KEY CONCEPTS
3.4 TRUTH TABLES
3.6 QUANTIFIERS
3.7 BIG-O NOTATION
3.8 NEGATING LOGICAL STATEMENTS
3.9 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 4 ■ Nondeterministic Finite Automata
4.2 WHY NFAS CAN BE SIMPLER THAN DFAS
4.4 FORMAL DEFINITION OF AN NFA
4.8 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 5 ■ Regular Expressions
5.3 REGULAR EXPRESSION OPERATIONS
5.4 FORMAL DEFINITION OF REGULAR EXPRESSIONS
5.5 APPLICATIONS
5.6 REGULAR EXPRESSIONS IN PYTHON
5.7 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 6 ■ Equivalence of Regular Languages and Regular Expressions
6.2 CONVERTING A REGULAR EXPRESSION TO A λ-NFA
6.3 CONVERTING A DFA TO A REGULAR EXPRESSION
6.4 ANOTHER DEFINITION FOR REGULAR LANGUAGES
6.5 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 7 ■ Direct Proof and Closure Properties
7.3 THE IMPORTANCE OF DEFINITIONS
7.4 NUMERICAL PROOFS
7.5 CLOSURE UNDER SET OPERATIONS
7.6 CHAPTER SUMMARY AND KEY CONCEPTS
8.3 AN ANALOGY FOR UNDERSTANDING INDUCTION
8.4 INDUCTION FOR ANALYZING SORTING RUN-TIME
8.5 HOW MANY BIT STRINGS ARE THERE OF LENGTH (AT MOST) N ?
8.6 COMPARING GROWTH OF FUNCTIONS
8.7 COMMON ERRORS WHEN USING INDUCTION
8.8 STRONG INDUCTION
8.9 AN ANALOGY FOR UNDERSTANDING STRONG INDUCTION
8.10 PROOFS WITH REGULAR EXPRESSIONS
8.11 CORRECTNESS OF BINARY SEARCH
8.12 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 9 ■ Proving the Language of a DFA
9.2 A SIMPLE EXAMPLE
9.4 AN EXAMPLE WITH SINK STATES
9.5 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 10 ■ Proof by Contradiction
10.1 WHY YOU SHOULD CARE
10.2 OVERVIEW OF THE TECHNIQUE
10.3 WHY YOU CAN’T WRITE √2 AS AN INTEGER FRACTION
10.4 WILL WE RUN OUT OF PRIME NUMBERS?
10.5 THE MINDBENDING NUMBER OF LANGUAGES
10.6 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 11 ■ Pumping Lemma for Regular Languages
11.1 WHY YOU SHOULD CARE
11.3 APPLYING THE PUMPING LEMMA
11.4 SELECTING THE STRING FROM THE LANGUAGE
11.5 SPLITTING THE CHOSEN STRING
11.6 CHOOSING THE NUMBER OF TIMES TO PUMP
11.8 CHAPTER SUMMARY AND KEY CONCEPTS
Chapter 12 ■ Context-Free Grammars
12.2 AN EXAMPLE CONTEXT-FREE GRAMMAR
12.4 CONTEXT-FREE GRAMMARS FOR REGULAR LANGUAGES
12.5 FORMAL DEFINITION OF CFGS
12.8 CHAPTER SUMMARY AND KEY CONCEPTS
13.2 AN EXAMPLE TURING MACHINE
13.3 FORMAL DEFINITION OF A TURING MACHINE
13.5 CONDITIONAL BRANCHING WITH A TURING MACHINE
13.6 TURING MACHINES CAN ACCEPT ALL REGULAR LANGUAGES
13.7 TURING MACHINES AS COMPUTERS OF FUNCTIONS
13.8 CHAPTER SUMMARY AND KEY CONCEPTS
14.2 VARIATIONS OF TURING MACHINES
14.4 UNIVERSAL TURING MACHINES
14.5 RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES
14.11CHAPTER SUMMARY AND KEY CONCEPTS
A.3 Arrangements without repeats, order matters
A.4 Arrangements without repeats, order doesn’t matter
A.5 Chapter Summary and Key Concepts
B.4 Chapter Summary and Key Concepts
Appendix C ■ Elementary Number Theory
C.3 Euclid’s Algorithm for GCD
C.4 Chapter Summary and Key Concepts
Appendix D ■ Asymptotic Notation
D.7 Chapter Summary and Key Concepts
E.5 Chapter Summary and Key Concepts
F.4 Insertion Sort
F.5 Chapter Summary and Key Concepts
Appendix G ■ Recurrence Relations
G.2 Merge Sort
G.4 A Review of Some Log Rules
G.6 Analyzing the Karatsuba-Ofman Algorithm
Biography
Ashwin Lall is Professor of Computer Science at Denison University. He joined the Denison faculty in 2010. Prior to this, he was a postdoctoral researcher at Georgia Tech, a Ph.D. student and Sproull fellow at the University of Rochester, and a math/computer science double major at Colgate University. Dr. Lall has taught all the existing flavors of the introductory Computer Science course as well as advanced topics such as Theory of Computation and Design/Analysis of Algorithms. He also enjoys teaching the Game Design elective in the CS major.
