Skip to main content

Topics

This page gives the order of topics as they are covered in the DePauw course CSC 233, Foundations of Computation. Note that it does not precisely follow the order in the book's table of contents, because some of the dependencies among sections cut across the chapter topics.

Week 1: Introduction​

Overview of Foundations and Functional Programming​

Propositional Logic and Boolean Algebra​

Week 2: Logic​

Logic Circuits and Circuit Simplification​

Common Circuit Components and Design​

Week 3:​

Sets: Concepts and Boolean Algebra​

Predicates and Quantifiers, Natural Deduction for Propositions​

Week 4:​

Natural Deduction for Predicates​

Induction and Recursion​

Week 5:​

Programming with Sets, Functions and Relations​

Relational Databases​

Week 6:​

Exam 1​

Week 7: Functional Programming​

Algebraic Data Types and Pattern Matching; MapReduce​

Functional Graphics​

Week 8: Lists and Sorting​

Functional Sorting​

Running Time and Recurrences; Program Verification​

Week 9: Trees and Graphs​

Tree Traversals; Binary Search Trees and Heaps​

Graphs, Representations, Traversals​

Week 10: Machine Models​

Languages, Regular Expressions, and Applications; Finite-State Automata​

Non-deterministic Automata, Equivalence with Regular Expressions​

Week 11:​

Exam 2​

Week 12:​

Sequential Circuits​

State Machines, and their implementations in Java and ReasonML​

Week 13:​

Grammars and Backus-Naur Form​

Parsing, Pushdown Automata, Recursive Descent​

Week 14:​

General Grammars, Turing Machines, Computability, Halting Problem​

Lambda Calculus​