Skip to main content

CSC 236 Topics

This page gives the order of topics as they are covered in the DePauw course CSC 236, Algorithmic 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. Basics of Functional Programming.​

Overview of Algorithmic Foundations​

Introduction to Functional Programming​

Recursion and Induction​

Algebraic Data Types and Pattern Matching​

Week 2: Elementary Functional Algorithms.​

Functional Graphics and Drawing Project​

MapReduce​

Functional Sorting​

Program Verification​

Week 3: Functional Trees. Introduction to Graphs.​

Tree Traversals​

Binary Search Trees and Heaps​

Balanced Binary Search Trees​

Week 4: Graph Algorithms.​

Graphs, Representations, Traversals​

Topological Sort and Connected Components​

Shortest Paths; Minimum Spanning Trees​

Transitive Closure​

Week 5:​

Exam 1​

Week 6: Recurrences. Algorithm Strategies.​

Running Time and Recurrences​

Algorithm Strategies: Decrease-and-Conquer​

Divide-and-Conquer​

Week 7: Greedy Algorithms. Dynamic Programming.​

Greedy Algorithms​

Dynamic Programming​

Edit Distance; Longest Common Subsequence​

Week 8: Advanced Algorithms.​

Hashtables and Bloom Filters​

Bucket, Counting, and Radix Sort​

Week 9: Algorithmic Complexity.​

Tractability​

NP Completeness​

Amortized Analysis​

Week 10:​

Exam 2​

Week 11: Regular Languages. State Machines.​

Knuth-Morris-Pratt​

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

State Machines, and their implementations in Java and Scala​

Week 12: Context-Free Languages. Parsing.​

Non-deterministic Automata, Equivalence with Regular Expressions​

Grammars and Backus-Naur Form​

Parsing, Pushdown Automata, Recursive Descent​

Week 13: Turing Machines. Lambda Calculus.​

General Grammars, Turing Machines, Computability, Halting Problem​

Lambda Calculus​

Week 14: Recursive Functions. Wrap-up.​

Recursive Functions​

Church-Turing Thesis​