Click for the "scroll" 
1. 
Why Study Computability, Complexity, and Languages?
(revised with minor changes August 21, 2017)

2. 
Sets, Tuples, Cartesian Products, Partial and Total Functions,
Predicates, Quantifiers, Proofs
(scroll corrected August 21, 2017)

 
PART 1: Computability 
 
3. 
The Minimalist (but all powerful) Programming Language S
(scroll revised August 28, 2013)

4. 
Partially Computable Functions
(scroll corrected September 11, 2015)

5. 
Primitive Recursive Functions
(scroll corrected September 20, 2017)

6. 
Sixteen BuildingBlock PRC Functions
(scroll revised August 29, 2013)

7. 
The Pairing Function and The Godel Numbers
(scroll corrected September 11, 2015)

8. 
Church's Thesis and the Unsolvability of the Halting Problem

9. 
A Universal Program that can Execute Any Program and the Concept of
Recursive Enumerability

10. 
Calculations on Strings, and the Minimalist (but all powerful) Language
S_{n} for String Processing
(scroll revised September 20, 2013)

11. 
The PostTuring Language T for String Processing and the Equivalence
of S, S_{n}, and T
(scroll corrected September 15, 2017)

12. 
Turing Machines
(scroll corrected September 15, 2017)

13. 
What's Meant by a Turing Machine Accepting a Language

 
PART 2: Grammars and Automata 
 
14. 
String Computations with Productions and Processes

15. 
Post's Correspondence Problem and Grammars

16. 
Phrase Structure Grammars and Context Sensitive Grammars
(scroll corrected September 20, 2017)

17. 
Finite Automata and Regular Languages

18. 
Properties of Regular Languages
(scroll corrected October 7, 2017)

19. 
Regular Expressions and the Pumping Lemma
(scroll corrected October 7, 2017)

20. 
ContextFree Languages
(scroll corrected October 23, 2015)
The two scribbles you see at the bottom right of the second page are my mother's signature dating back to the year 2006 when she visited Lafayette. A woman of indomitable spirit who raised five children ' under difficult circumstances, she passed away in 2012.

21. 
Regular Grammars, Chomsky Normal Form, and BarHillel's Pumping
Lemma
(scroll revised October 13, 2011)

22. 
Properties of ContextFree Languages
(scroll corrected October 23, 2015)

23. 
Bracket Languages and the Pushdown Automata

 
PART 3: The Theory of NPCompleteness

 
24. 
Computational Complexity: Some Basic Definitions

25. 
Defining P and NP
(scroll revised December 16, 2011)

26. 
A More Formal Definition of Class NP
(scroll updated November 30, 2015)

27. 
Polynomial Transformability of Problems in Class NP
(scroll revised December 16, 2011)

28. 
Definition of NPComplete and the SATISFIABILITY Problem
(scroll revised November 3, 2011)

29. 
The Six Basic NPComplete Problems and the NPCompleteness
Proof for 3SAT

30. 
NPCompleteness Proofs for 3DM, VC, CLIQUE, HC, and PARTITION
(scroll significantly expanded, November 24, 2015)

31. 
NPCompleteness Proofs by Restriction: Subgraph Isomorphism (SGI),
KNAPSACK, Multiprocessor Scheduling (MS), and BoundedDegree
Spanning Tree (BDST)

32. 
NPCompleteness Proofs by Local Replacement: Sequencing within
Intervals (SQUINT), and Partition into Triangles (PIT)
(scroll revised December 1, 2011)

33. 
NPCompleteness Proofs by Component Design: Minimum Tardiness
Sequencing (MINTARD)
(scroll corrected November 24, 2015)

34. 
Reasoning About the Complexity of the Subproblems of a Given
NPComplete Problem (Example: Graph 3Colorability)

35. 
StrongSense and WeakSense NPCompleteness for Number
Problems
(scroll revised December 16, 2011)

36. 
Extending the Complexity Theory to Search Problems

37. 
Generalizing Polynomial Transformability to Turing Reducibility
and the Definition of NPHard

38. 
Complements and Optimization Versions of the NPComplete
Decision Problems
(scroll revised December 15, 2011)

39. 
Approximation Algorithms for Combinatorial Optimization:
Bin Packing Optimization (BINPACKO), Traveling Salesman
(Restricted) Optimization (TSRO), etc.

40. 
Nonapproximable and Easily Approximable NPHard Optimization
Problems: Graph Coloring Optimization Problem (GRAPHCOLO),
Knapsack Optimization Problem (KNAPSACKO), etc.
(scroll revised December 15, 2011)

41. 
The Classes NPI, coNP, P^{NP} and NP^{NP} of Problems and
the Class #P of Enumeration Problems
(scroll revised December 6, 2011)

42. 
Storage Considerations: The Classes PSPACE, PSPACEComplete,
and PSPACEhard

 
PART 4: Random Graphs

 
43. 
Random Graphs: An Introduction

 
44. 
The Degree Sequence and PolynomialTime Graph Isomorphism
for Random Graphs
