This page contains an outline of the midterm exam for CS 303. This covers the first chapters in Building Blocks for Theoretical Computer Science up through Induction.

Goals

The goal of the midterm is to evaluate you on the most important topics from the first half of the term.

Quizzes in canvas, all will be timed, and only one chance to take them

Math notation quiz, updated with new notation (5-10 min)
Math bases quiz, same as before (5-10+ min)
Truth table - able to write one out correctly (few minutes)
Proof that a number is irrational - able to write out the proof correctly (few minutes)
Euclid's GCD algorithm - able to show the steps of the algorithm on a given example (few minutes)
Logic - given a logical formula, identify whether a formula is unsatisfiable, valid, satisfiable (1 minute per simple formula)
Identify the logical rule or theorem - De Morgan's, distributing union over intersection (and vice versa), definition of implication, pigeon hole principle, contrapositive, inclusion-exclusion, rules of exponents/logs
Number theory - congruence notation, divisibility statements, lcm and gcd
Sets - terminology, operations
Functions/Relations - terminology/definitions
Other math - factorial, combinations, exponents/logs
Graphs - terms, basic properties
Induction and big O asymptotics - maybe some basic

CS 303 midterm