Teaching Assistants:
Peer Teachers:
This course discusses some basic mathematical techniques that are useful in the analysis of algorithms. In particular, we will discuss proof techniques; basic mathematical notions such as sets, functions, and relations; basic techniques from combinatorics concerning counting and recurrence relations. We will give a brief introduction to algorithms and their complexity, and discuss the automata and the Turing machine models of computation.
| T Jan 17 | Introduction pdf keynote |
| R Jan 19 | Time Complexity of Algorithms pdf keynote |
| T Jan 24 | Time Complexity of Algorithms, Inequalities, Proof Techniques pdf keynote |
| R Jan 26 | Propositional Logic pdf keynote |
| T Jan 31 | Propositional Logic pdf keynote |
| R Feb 02 | Predicate Logic pdf keynote Proofs pdf keynote |
| T Feb 07 | Sets and Functions pdf keynote |
| R Feb 09 | Sets and Functions |
| T Feb 14 | Sequences and Sums pdf keynote |
| R Feb 16 | Review pdf keynote |
| T Feb 21 | Exam 1 |
| R Feb 23 | Induction and Strong Induction pdf keynote |
| T Feb 28 | Strong Induction |
| R Mar 01 | Inductive Sets, Recursive Functions, Structural Induction pdf keynote |
| T Mar 06 | Counting pdf keynote |
| R Mar 08 | Counting |
| T Mar 13 | Spring Break |
| R Mar 15 | Spring Break |
| T Mar 20 | Recurrences pdf keynote |
| R Mar 22 | Review pdf keynote |
| T Mar 27 | Midterm 2 |
| R Mar 29 | Generating Functions pdf keynote |
| T Apr 03 | Solving Recurrences, Divide-and-Conquer pdf keynote |
| R Apr 05 | Relations pdf keynote |
| T Apr 10 | Equivalence Relations, Partial Orders (slides: see above) |
| R Apr 12 | Lattices, n-ary Relations, Relational Databases (slides: see above) |
| T Apr 17 | Formal Languages pdf keynote |
| R Apr 19 | Formal Languages (slides: see above) |
| T Apr 24 | Regular Languages and FSMs (slides: see Formal Languages above) |
| R Apr 26 | Review pdf keynote |