Fundamentals of Computer Science Study Guide

Books

1. Rosen, K.H. Discrete Mathematics and its Applications, Global Edition Direct Link
2. Sipser, M. Introduction to the theory of computation PDF excerpts are provided on Coursera, however I suggest getting the book, because we only have access to chapter 1. The international edition can be found for cheap. Link
3. Hopcroft, J., R. Motwani and J.D. Ullman Introduction to automata theory, languages and computation PDF Excerpts are provided on Coursera.
4. Forbes, M. A theoretical introduction to Turing Machine Direct Link
5. Kozen, D.C. Automata and Computability. PDF excerpts are provided on Coursera
6. Chang, S. (ed) Data structures and algorithms Direct Link

Topics Covered

• Discrete Math Prerequisites
  • Logic
  • Proofs:
    • Direct Proof
    • Proof by Contraposition
    • Proof by Contradiction
    • Proof by Induction
  • Combinatorics
• Automata Theory
  • Finite State Automata
    • Deterministic
    • Nondeterministic
  • Regular Languages
    • Regular Expressions
  • Non-Regular Languages*
    • Pumping Lemma
    • Context-Free Grammars
  • Turing Machines*
• Algorithms
  • Algorithm Complexity
  • Algorithms Covered:
    • Insertion Sort
    • Bubble Sort
    • Heap Sort
    • Quick Sort
    • Merge Sort
    • Binary Search
    • Gale-Shapley
  • Master Theorem

*Consult external resources because these topics are not explained well in the lectures

Topic Map

Suggested Reading List

Week	Topic	Reading
1 & 2	Logic	Rosen: Chapter 1.1 - 1.4, 1.5 (optional)
3 & 4	Proofs	Rosen: Chapter 1.8, 1.9 (optional, to practice proof-writing) 5.1, 5.3 (optional, but highly recommended to get more comfortable with recursion)
5 & 6	Combinatorics	Rosen: Chapter 6.1 - 6.3
7 & 8	Automata Theory: DFA and NFA	Sipser: Chapter 1.1, 1.2
9 & 10	Automata Theory: Regular Languages	Sipser: Chapter 1.3, 1.4
11 & 12	Automata Theory: Non-Regular Languages*	Sipser: Chapter 2.1 (More concise and easier to understand than Hopcroft reading) Hopcroft: Chapter 5 Chapter 7.1 (Covers Chomsky Normal Form)
13 & 14	Automata Theory: Turing Machines*	Forbes: Chapter 1 (I found this book to be unreadable. Read Sipser or Hopcroft instead) Kozen: Lecture 32 Sipser: Chapter 3.1 (Optional) Hopcroft: Chapter 8.1, 8.2 (Optional)
15 & 16	Algorithms I	Rosen: Chapter 3.1 Chang: Chapter 8, 9
17 & 18	Algorithms II	Rosen: 5.4
19 & 20	Algorithms: Complexity	Rosen: Chapter 3.2, 3.3 (both optional) Chang: Chapter 2, 3 (optional)

*The lectures in weeks 11 - 14 (covering non-regular languages and Turing machines) are exceptionally poor so I suggest consulting the resources below

Resources

Lecture notes by Felipe Balbi

Writing Proofs

1. The exercises in chapters 1.8, 1.9, and 5.1of the Rosen book give you the opportunity to practice proof-writing. Check your answers here
2. A Guide to Proof-Writing
3. Techniques for Proof-Writing
4. The Stanford CS103 website has many resources related to writing proofs

Automata Theory

1. Practice designing automata, regular expressions, grammars, and Turing machines by solving homework problems in the Automata Theory MOOC (#5 below) or the Sipser book. Check your answers here
2. The Stanford CS103 website also has very well made and detailed slides covering Finite State Automata, Regular Expressions, Context-Free Grammars, and Turing Machines
3. Theory of Computation lectures by UC Davis. Follows the Sipser book.
4. Harry Potter Theory of Computation Playlist
5. Stanford Automata Theory MOOC. Follows the Hopcroft book. Includes homework as well.

Algorithms

There are many resources to learn algorithms online here is a few of them:

1. Khanacademy
2. Visualgo
3. GeeksforGeeks
4. Interview Cake sorting algorithms reference, Binary Search reference
5. Algorithms Youtube Playlist
6. We also have access to CLRS, a popular algorithms textbook. Direct Link The chapters relevant to this course are: 2, 3, 4.5, 4.6, 6, 7