CAS CS 131 -- Fall 2017 -- Lectures and Readings Page

CAS CS 131 - Fall 2017 - Lectures, Readings, and Assignments

Homework Assignments

Assignments, solutions and all other handouts can be found on our Piazza page, under the Resources tab.

Homework 1 was due on Friday, September 15th, returned September 27th in lab. Solutions have been posted. The class average was 52.6 out of 60.

Homework 2 was due on Friday, September 22nd, and was returned in lecture on Tuesday, October 3rd. Solutions have been posted. The class average was 40.7 out of 48. (Each homework is of equal weight, so think of your score in percentage terms).

Homework 3 was due on Friday, September 29th, returned in lab Wed 10/11. The class average was 48.6 out of 60.

The first midterm was held in class on Thursday, October 5th. The class average was 64%.

Homework 4 was due on Friday, October 13th, returned in lab Wed 10/25. The class average was 41.9 out of 50.

Homework 5 was due on Friday, October 20th, returned in lab on Wed 11/1. The class average was 49.6 out of 60.

Homework 6 was due on Friday, October 27th, returned in lab on Wed 11/8. The class average was 29.7 out of 40.

Homework 7 was due on Friday, November 3, returned in lab on Wed 11/15. The class average was 50 out of 60, amongst those who submitted.

The second midterm was held in class on Thursday, November 9th.

Homework 8 was due on Friday, November 17, and was returned in lab. The class average was 48.7 out of 60.

Homework 9 was due on Friday, December 1. Solutions have been posted.

Homework 10 was due on Friday, December 8. Solutions have been posted.

Lecture Topics

Lecture 1 (9/5) [John]: Babis introduced the course and the staff, then John reviewed the syllabus. Lecture: introduction to proofs and logical reasoning. Propositions, deductions and axioms. Famous propositions in discrete mathematics: Euler's conjecture, 4-color theorem, Fermat's Last Theorem. Warm-up on proving propositions.
Reading: Chapter 1.1 and 1.7

Lecture 2 (9/7) [Babis]: Propositions and propositional logic. Logical negation, conjunction, disjunction, XOR: truth tables, use as a bitwise operator, and use in English. Compound operators and precedence. Implication/conditional and contrapositive. Consistency (referencing Godel's incompleteness theorem).
Reading: Chapter 1.1 - 1.2

Lecture 3 (9/12) [Babis]: Translating English to proposoitional logic: propositions, variables and connectives. Building logic circuits (NOT, AND, OR gates). Tautologies, contradictions, logical equivalences and proving them via Laws and truth tables. Examples: proving De Morgan's Laws and an associative law.
Reading: Chapter 1.3

Lecture 4 (9/14) [John]. Basic equivalences involving implications, in logic and in English. Proof that x^3+x+1=0 has no rational solution (Lab problem). "Odd/even" truth tables for addition and multiplication. Logical operators in computer programs, example of stopping condition in iterative algorithm for computing square roots. Intro to existential and universal quantifiers and their negations.
Reading: Chapter 1.4

Lecture 5 (9/19) [John]. Quantifiers in programs. Implementing "every mail message > 5MB must be compressed" using conditional tests and assertions. Quantifiers as ANDs and ORs, De Morgan's Law applied to quantifiers. Proving propositions involving quantifiers and their negations. Proof of Lemma: "if x is even, x^2 is divisible by 4". Proof of Theorem: "\sqrt(2) is irrational" (using Lemma and quantifiers). Nested quantifiers, especially \forall \exists and \exists \forall.
Reading: Chapter 1.5. We also covered the reasoning underlying Chapter 1.6, but we are not going to use this formal notation. Skim read it.

Lecture 6 (9/21) [Babis]. Before proving something, understand the problem! Proof types with basic examples: direct proofs, proof by contradictions (another look at \sqrt(2) is irrational), constructive existence proofs and non-constructive proofs (proof that there exists irrationals x, y s.t. x^y is rational). Coloring proofs: can you tile a chessboard with dominos when: 0, 1, and 2 squares are missing?
Reading: Chapter 1.7 - 1.8.

Lecture 7 (9/26) [Babis]. Sequences, sets, and recurrences: basic definitions and applications. Sets: review of notation and |A union B| = |A|+|B|-|A intersection B|. Counting elements above the diagonal in an n by n grid. Important arithmetic sum: 1+2+...+N = N(N+1)/2. Finding a missing element from a set 1...N by computing this sum. Finding the bucket of counterfeit coins with one weighing. Examples of sequences including arithmetic and geometric progressions and Fibonacci sequences. Recurrences for each of these sequences.
Reading: Chapter 2.4. (The preceding sections of Chapter 2 are very dry, and should be mostly review.)

Lecture 8 (9/28) [John]. Propositional logic as a foundation for AI and Robotics: an example of seeing the path planning problem as an instance of theorem proving using logical deductions. Motivation and introduction to mathematical induction, and where it is useful. 5-step rubric for proofs by induction. Proof of '1+2+...+N = N(N+1)/2' by induction. Proof that the sum of the first i odd numbers is a perfect square (not finished).
Reading: Chapter 5.1.
Midterm 1 material ended here.

Lecture 9 (10/3) [Babis]. The induction axiom. Many examples of inductive proofs, and some alternative proofs. Three proofs that 3 divides n^3-n. Completion of proof from last lecture (+ geometric intuition). Proof of geometric sum: 1+2+4+...+2^n = 2^{n+1}-1. Assorted inductive proofs involving factorials and square roots.

Lecture 10 (10/5): In-class Midterm 1.

No lecture on Tuesday, October 10 due to Columbus Day.

Lecture 11 (10/12) [Babis]. Selected midterm answers. Basic induction and strong induction. Optimal strategy for the pile of matches game (example 3, 5.2), postage stamp problem (example 4, 5.2). Geometric induction: polygons, internal diagonals and triangulation.
Reading: Chapter 5.2.

Lecture 12 (10/17) [John]. Basic number theory. Integers represented in different bases (decimal, binary, octal, hex) and converting between bases. Binary arithmetic, the division "algorithm". Brute force algorithms for primality testing and factoring. Foreshadowing of poly-time algorithm vs. intractability.
Reading: Chapter 4.1 - 4.2.

Lecture 13 (10/19) [John]. Fundamental Theorem of Arithmetic (FTA). Existence proof by strong induction (Example 2 in 5.2). Uniqueness proof requires knowledge of greatest common divisors (GCD). GCD problem, brute force algorithm, relationship between linear combinations and GCD. Fast algorithm for GCD (Euclid), recursive implementation. Linkage between GCD, LCM and prime factorization. Proof of uniqueness of FTA via GCD.
Reading: Chapter 4.3

Lecture 14 (10/24) [Babis]. Review of Euclid's algorithm. Congruences and modular arithmetic. Key Theorem: If a \equiv b mod m, c \equiv d mod m, then a+c \equiv b+d mod m, and ac \equiv bd mod m. Multiplicative inverses. Chinese remainder theorem, proof of correctness and applications.
Reading: Chapter 4.1, 4.4.

Lecture 15 (10/26) [Babis]. Solving linear congruences of the form ax \equiv b mod m, using the book's method and by multiplying with the inverse. Back substitution to solve Chinese remainder problems. Arithmetic with large primes. Fermat's Little theorem. Applications to hashing, ciphers and public-key cryptography.
Reading: Chapter 4.6.

Lecture 16 (10/31) [John]. Review of key sequences in the course, writing them as recurrences, and analyzing their asymptotic behavior. Distinguishing between polynomial functions and exponential functions using little-o notation, limits definition, and L'Hopital's Rule [not in textbook]. Time complexity of algorithms, correctness and running time of selection sort.
Reading: Use class notes and handout on Piazza. Parallels Chapter 3.1 - 3.3.

Lecture 17 (11/2) [John]. More on asymptotic notation and commmon algorithmic running times. Little-o, big-O, and big-Theta, both using limits and the quantificational logic definition. Review that selection sort uses Theta(n^2) comparisons, and that n log n sorting algorithms would be highly preferable. Binary search sketch, recurrence and discussion of logarithmic time. Lame's proof that Euclidean GCD is logarithmic time. Reading: Chapter 5.3 - 5.4.

Lecture 18 (11/7) [Babis]. Computing Computing n! recursively and iteratively. Computing pow(a,n) recursively and iteratively -- two recurrences, and why a^n = a a^{n-1} is slower than a^n= (a^n/2)^2). Generating binary strings of length n with no two consecutive ones recursively. Towers of Hanoi Towers with more detail than the textbook, including a tight lower bound on the number of moves. Reading: Chapter 5.4, 8.1.

Lecture 19 (11/9): In-class Midterm 2.

Lecture 20 (11/14) [Babis]. Divide-and-conquer algorithms, solving recurrences via the Master theorem (p. 532). Floors and ceilings. Clarification that b in f(n/b) of Master theorem does not have divide n. Mergesort algorithm and analysis. Reading: Chapter 5.4, 8.3 + floors/ceilings in 2.3.

Lecture 21 (11/16) [John]. Definitions and examples of one-to-one, onto, and bijective functions and relation to counting. Basic counting of sets and sequences using various rules and applications: bijection rule, # of subsets, dozens of donuts. Product rule: counting telephone numbers. Sum and difference rules: counting representatives. Reading: Chapter 6.1 + material about functions in 2.3.

Lecture 22 (11/21) [John]. Review of rules from last time. Counting passwords example using bijection + sum and product rules. Division rule. Permutations: counting permutations as a special case of the product rule. Counting groups of kids in the front row: subsets of size 10 vs. sequences of length 10. Counting sequences is easy through product rule: n! / (n-10)! Sequences to subsets is k! to 1: there are k! ways to permute a subset of size k (of n). Implication by division rule: # subsets = (#sequences / k!). Reading: Chapter 6.1, 6.3.

(11/23) Thanksgiving!

Lecture 23 (11/28) [Babis]. Algebraic and combinatorial proofs involving combinations. N choose r = N choose N-r, via bijective and algebraic proof. How many 10 letter words use exactly 4 As, 3Bs, 2Cs, 1D? (10 choose 4) (6 choose 3) (3 choose 2) (1 choose 1), plus an alternative formulation. Two proofs of Pascal’s identity. Pascal’s triangle. Binomial theorem and applications. Vandermonde’s identity. Reading: Chapter 6.3, 6.4.

Lecture 24 (11/30) [Babis]. Pigeonhole principle (PHP). Sock example as motivation. Proof of PHP + several examples from 6.2 Generalized PHP, proof and applications. Ramsey theory: definition of Ramsey number R(m,n), and proof using PHP that R(3,3) = 6. Reading: Chapter 6.2.

Lecture 25 (12/5) [John]. Problem solving: inductive proof that row i of Pascal’s triangle sums to 2^n. Then: probability: definition and examples when outcomes are equally likely. Method for computing probabilities when outcomes are not equally likely: 1) tree diagram to define outcomes, 2) define events, 3) compute edge probabilities and multiply together to compute outcome probabilities, 4) compute event probability. Monty Hall problem. Reading: Chapter 7.1 - 7.2

Lecture 26 (12/7) [John]. Problem solving: should I start mining Bitcoin? Brief overview: blockchain implementation of a distributed ledger, role of cryptographic hash functions, and concept of mining a block (for a Bitcoin reward). Bitcoin definition of difficulty D and hardness = 0xFFFF * 2^208 / D. Sadly, even with a CPU/GPU doing 10^8 hashes per sec, the contribution to the global mining pool is roughly 2^{-32}. Can’t even make a buck a year in expectation. Then, conditional probabilities and independence. Application to families with 3 children (textbook example). Birthday paradox.

Lecture 27 (12/12) [John]. Online course evaluations -- bring your laptop. How 131 fits in to CS major curriculum. Bayes' Rule, application of Bayesian spam filters, random variables and expectations.