# Schedule

*This schedule is tentative and subject to change*.

Warmups are due **every class day**, even if they are not listed under the “Due” column.

## Week 1

M Sep. 11 |
Welcome! | ||||||

We discuss the structure of the course and the role of mathematics in modern computation. | |||||||

Learning ObjectivesGetting Oriented |
In ClassWelcome! |
DueJoin EdStem and Gradescope. |
|||||

W Sep. 13 |
Mathematics and Me | ||||||

We discuss our relationship to math and how we've learned what we've learned. | |||||||

Learning ObjectivesGetting Oriented |
PrepMath Autobiography |
In ClassMathematics and Me |
|||||

F Sep. 15 |
Lab 1: Technical Writing and Truth Tables | ||||||

We review truth tables for describing logical operations and begin our first lab assignment in Google Colab. | |||||||

Learning ObjectivesGetting Oriented |
PrepStatements and Truth Tables |
In ClassLab 1: Technical Writing and Truth Tables |

## Week 2

M Sep. 18 |
Working with Symbolic Logic | ||||||

We introduce formal manipulations of logical expressions and work with the many ways to manipulate conditional statements. | |||||||

Learning ObjectivesSets and Logic |
PrepConditionals and Friends |
In ClassConditionals and Friends |
|||||

W Sep. 20 |
Sets and Set Operations | ||||||

We introduce sets, set-builder notation, and operations for combining and measuring sets. | |||||||

Learning ObjectivesSets and Logic |
PrepSets |
In ClassSets |
|||||

F Sep. 22 |
Lab 2: Inclusion-Exclusion | ||||||

We use the inclusion-exclusion formula and its generalizations to compute the cardinality of unions of sets. Along the way, we practice writing mathematical computations and performing computational experiments. | |||||||

Learning ObjectivesSets and Logic |
PrepMore on Sets |
In ClassLab 2: Inclusion-Exclusion |
DueLab 1: Technical Writing and Truth Tables |

## Week 3

M Sep. 25 |
Quantifiers and Predicate Logic | ||||||

We discuss quantification of propositions over sets and how to apply logical operations to symbolic quantifiers. | |||||||

Learning ObjectivesSets and Logic |
PrepQuantifiers and Predicate Logic |
In ClassQuantifiers and Predicate Logic |
|||||

W Sep. 27 |
Further Topics: Logic and Sets | ||||||

We introduce logical deduction and review topics from the course so far. | |||||||

Learning ObjectivesSets and Logic Proof |
PrepMore on Quantifiers and Logic |
In ClassTBD |
|||||

F Sep. 29 |
Quiz 1 | ||||||

The first of four quizzes in which students have an opportunity to complete Learning Targets. This quiz includes targets LS1, LS2, and LS3. |
|||||||

DueLab 2: Inclusion-Exclusion |

## Week 4

M Oct. 02 |
Direct Proofs | ||||||

We introduce direct proofs, our first general technique for proving statements about mathematics and algorithms. | |||||||

Learning ObjectivesProof techniques |
PrepDirect Proofs |
In ClassTBD |
|||||

W Oct. 04 |
Cases, Contradictions, and Counterexamples | ||||||

We introduce several additional proof techniques, as well as the practice of counterexamples for disproving incorrect implications. | |||||||

Learning ObjectivesProof techniques |
PrepCases, Contradictions, and Counterexamples |
||||||

F Oct. 06 |
Lab 3: Proof Practice | ||||||

We practice proving mathematical statements using a variety of techniques. | |||||||

Learning ObjectivesProof techniques |
PrepProof Style |
In ClassLab 3: Proof Practice |

## Week 5

M Oct. 09 |
Induction | ||||||

We introduce mathematical induction, a powerful proof technique for demonstrating that a claim is true for infinitely many cases. | |||||||

Learning ObjectivesProof techniques |
PrepIntroduction to Induction |
||||||

W Oct. 11 |
More Induction | ||||||

We broaden our usage of induction to use strong induction and to write inductive proofs for the correctness of functions. | |||||||

Learning ObjectivesProof techniques |
PrepMore Induction |
||||||

F Oct. 13 |
No Class: Midterm Recess | ||||||

DueLab 3: Proof Practice |

## Week 6

M Oct. 16 |
Relations | ||||||

We introduce relations, with a special focus on equivalence relations on sets. | |||||||

Learning ObjectivesRelations and functions |
PrepRelations |
||||||

W Oct. 18 |
Functions | ||||||

We introduce functions, with a focus on recursive definitions of functions. | |||||||

Learning ObjectivesRelations and functions |
PrepFunctions |
||||||

F Oct. 20 |
Quiz 2 | ||||||

The second of four quizzes in which students have an opportunity to complete Learning Targets. This quiz includes targets LS1, LS2, LS3, PF1, PF2, and FR1. |
|||||||

DueLab 3: Proof Practice |

## Week 7

M Oct. 23 |
Counting | ||||||

We use the principles of addition, multiplication, and inclusion-exclusion to solve counting problems. | |||||||

Learning ObjectivesCounting |
PrepCounting |
In ClassCounting Activity |
|||||

W Oct. 25 |
Permutations and Combinations | ||||||

We use permutations and combinations to count possibilities in situations involving rearrangement and subset-selection. | |||||||

Learning ObjectivesCounting |
PrepPermutations and Combinations |
||||||

F Oct. 27 |
Lab 4: Counting Lattice Paths | ||||||

We use binomial coefficients and Python programming to efficiently compute the number of paths through grids. | |||||||

Learning ObjectivesCounting |
PrepCounting Lattice Paths |
In ClassLab 4: Counting Lattice Paths |

## Week 8

M Oct. 30 |
Recursion and Recurrence Relations | ||||||

We introduce recurrence relations and simple methods for solving them. | |||||||

Learning ObjectivesRecurrence Relations |
PrepRecursion and Recurrence Relations |
In ClassTower of Hanoi |
|||||

W Nov. 01 |
Recursion and Recurrence Relations | ||||||

We practice writing recurrence relations to describe quantities of interest and develop further techniques to solve them. | |||||||

PrepMore Recursion and Recurrence Relations |
In ClassParking Spaces |
||||||

F Nov. 03 |
Lab 5: Analyzing Gradient Descent | ||||||

We use recurrence relations to analyze the runtime of an algorithm for minimizing a function. | |||||||

PrepNumerical Algorithms |
In ClassLab 5: Analyzing Gradient Descent |
DueLab 4: Counting Lattice Paths |

## Week 9

M Nov. 06 |
Asymptotics and Big-Oh | ||||||

We formally define big-oh notation and prove asymptotic descriptions of various functions. | |||||||

Learning ObjectivesAsymptotics |
PrepAsymptotics and Big-Oh Notation |
||||||

W Nov. 08 |
Analyzing Algorithms: The Tree Method | ||||||

We use the tree method and other methods to estimate asymptotic runtimes of common algorithms. | |||||||

Learning ObjectivesAsymptotics |
PrepAnalyzing Algorithms |
||||||

F Nov. 10 |
Graphs | ||||||

We introduce graphs as models of data structures and connected systems. | |||||||

Learning ObjectivesGraph Theory |
PrepGraphs and Graph Theory |
DueLab 5: Gradient Descent |

## Week 10

M Nov. 13 |
Quiz 3 | ||||||

The third of four quizzes in which students have an opportunity to complete Learning Targets. This quiz includes targets LS1, LS2, LS3, PF1, PF2, FR1, C1, C2, and R1. |
|||||||

W Nov. 15 |
Graphs | ||||||

We continue our discussion of graphs with a focus on trees. | |||||||

Learning ObjectivesGraph Theory |
PrepMore Graph Theory |
||||||

F Nov. 17 |
Lab 6: Triangle-Counting | ||||||

We study the adjacency matrix of a graph and use it to count the number of triangles in real and synthetic graph data sets. | |||||||

Learning ObjectivesGraph Theory |
PrepNetwork Science |
In ClassLab 6: Introduction to Network Science |

## Week 11

M Nov. 27 |
Introducing Discrete Probability | ||||||

We introduce discrete probability through a discussion of a famous problem. | |||||||

Learning ObjectivesProbability |
PrepIntroducing Discrete Probability |
||||||

W Nov. 29 |
Sample Spaces and Conditional Probability | ||||||

We introduce formal discrete probability theory via sample spaces. We also introduce conditional probability. | |||||||

Learning ObjectivesProbability |
PrepSample Spaces, Conditional Probability |
In ClassSample Spaces, Conditional Probability |
|||||

F Dec. 01 |
Lab 7: TBD | ||||||

Learning ObjectivesProbability |
DueLab 6: TBD |

## Week 12

M Dec. 04 |
Bayes' Theorem | ||||||

We continue our discussion of conditional probability and introduce Bayes' Theorem. | |||||||

Learning ObjectivesProbability |
PrepConditional Probability and Bayes' Theorem |
In ClassBayes' Rule and DNA Testing |
|||||

W Dec. 06 |
Random Variables and Expectation | ||||||

We define random variables and compute the expected value of simple random variables. | |||||||

Learning ObjectivesProbability |
PrepRandom variables and expectation |
In ClassTBD |
|||||

F Dec. 08 |
Quiz 4 | ||||||

DueLab 7: TBD |

## Week 13

M Dec. 11 |
Flex, Review | ||||||

No matching items

## Final Exam

Our final exam will be another quiz covering all twelve core Learning Targets. So, it’s just like Quiz 4, except you’ll have 3 hours instead of 50 minutes.

© Phil Chodrow, 2023