Discrete Mathematics

# cs2102: Discrete Math

Problem Set 8 Revisions (Thu, 3 Nov 2016)

There are three important revisions to Problem Set 8:

1. The definition of height for Problem 4 should have included that the height of the null tree is 0.

2. The definition of the OrderedBinaryTree before Problem 7 did not make sense for constructing nodes where one (or both) of the subtrees are null. I have added clauses that allow empty trees to be used as the subtrees in a node. Without these, it would not be possible to construct any trees (other than the base null tree), since it would not be sensible to satisfy the maximum or minimum constraints for the null tree. It makes more sense to consider these undefined for the null tree, so it would be impossible to satisfy the constructor constraints without adding the disjunction clauses that allow the sub-trees to be null.

3. For Problem 11, the definition of length using list_accumulate should be list_accumulate(lambda a, b: b + 1, lst, 0).

The version now posted has these revisions. If you already found work-arounds to these problems in your solutions, you can add a note to your assignment indicating this and don’t need to revisit them, but otherwise, please solve the revised problems.

Class 18: Infinite Sets (Tue, 1 Nov 2016)

### Schedule

Before Thursday, everyone should have finished reading MCS Chapter 8.

Problem Set 8 is due Friday (4 November) at 6:29pm.

I am out of town Wednesday and will not be able to hold my normal office hours.

Friday, 4 November at 11am (Rotunda Dome Room): Steve Huffman (BSCS 2005, co-founder and CEO of Reddit), Computer Science Distinguished Alumni Speaker.

## Exam 2

Exam 2 will be in class on Thursday, 10 November. It will be similar in format to Exam 1. If you need to make special arrangements for taking Exam 2, please contact me by the end of this week (Nov 6).

Resources. As with Exam 1, you will be permitted to use a single paper page of notes that you prepare and bring to the exam. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page. No other resources are permitted during the exam.

Content. The problems on the exam will cover material from Classes 1–17, Problem Sets 1–8 (including the provided solutions), and MCS Chapters 1–7. Exam 2 will emphasize material covered since Exam 1 (Classes 12–17, Problem Sets 6–8, and MCS Chapters 6–7), but will also include questions that cover earlier material in the class. In particular, you should not be at all surprised if Exam 2 includes questions very similar to Problem 4 and Problem 8 from Exam 1, so it would be quite foolish for any student to go into the exam without making sure they understand those problems and their solutions. There will not be any questions about trick-xor-treat protocols, despite their practical importance and mathematical beauty. If you understand the problems on the problem sets and questions on the class notes well enough to be able to answer similar questions, you should do well on the exam.

The main topics the exam will cover include:

• State Machines (how to interpret and reason about a state machine given its formal description, how to model a problem with a state machine)

• Invariant Principle (you should be able to construct a proof that uses the invariant principle to reason about properties of reachable states, and be able to understand proofs that use and mis-use the invariant principle)

• Termination Proofs (you should be able to prove a state machine eventually reaches a terminating state, or that a program eventually terminates)

• Stable Matching (you should understand the definition of a stable matching and the Gale-Shalpey algorithm for finding a stable matching, and be able to prove properties about matchings)

• Recursive Data Types (how to define a data type constructively, operations on recursive data types; lists, trees, and other recursively defined data types)

• Structural Induction (how to use the principle of structural induction to reason about all objects of a recursive data type; understand the connections and differences between structural induction, invariant principle, and induction on the natural numbers)

For most students, I believe the best way to prepare for the exam will be to (1) go over exam 1 and the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the questions in the class notes and convince yourself you can answer them well; (3) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and understand well the problems on the problem set, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #2 and #3 as well. If you have anything you want me to review before the exam, post on slack before Monday (7 November).

Apostolos Doxiadis and Christos Papadimitriou. Logicomix: An epic search for truth, Bloomsbury USA, 2009.

Math Professors at UVa (1825-1900)

Courtenay’s tenure at Virginia was, in contrast to that of his predecessor, a resounding success. He was described as a model professor: “He never by look, act, word, or emphasis disparaged the efforts or undervalued the acquirements of his pupils. His pleasant smile and kind voice, when he would say, ‘Is that answer perfectly correct?’ gave hope to many minds struggling with science”

Charles Bonnycastle, UVA’s Professor of Mathematics, 1825-1840

As mathematics professor, “Old Bonny,” as he was fondly called, replaced the antiquated British approach to mathematical pedagogy typified by his own father’s texts with a new approach borrowed from French mathematicians. British writers had imitated Euclid by clinging to the deductive manner of presenting material. They opened their texts with axioms and definitions and proceeded to the derivation of facts and theorems. Although logically satisfying to mathematicians, the method did little to motivate beginning students. French textbook writers, on the other hand, approached mathematics analytically, leading from concrete examples to abstractions. Bonnycastle introduced this method at the University of Virginia and published his own college textbook, Inductive Geometry, or, An Analysis of the Relations of Form and Magnitude: Commencing with the Elementary Ideas Derived Through the Senses, and Proceeding by a Train of Inductive Reasoning to Develop the Present State of the Science (1834). Painfully prolix even by nineteenth-century standards, the innovative book was not a financial success. (Excerpt from article by Karen Parshall)

# Infinite Sets

Finite Cardinality. The cardinality of the set $$\mathbb{N}_k = { n | n \in \mathbb{N} \wedge n < k }$$ is $k$. If there is a bijection between two sets, they have the same cardinality. (Class 9)

Does this definition tell us the cardinality of $\mathbb{N}$?

###

Definition. A set $C$ is infinite if there is no bijection between $C$ and any set $\mathbb{N}_k$ (as defined above).

Dedekind-Infinite. A set $A$ is Dedekind-infinite if and only if there exists a strict subset of $A$ with the same cardinality as $A$. That is, $$\exists B \subset A \ldotp \exists R \ldotp R\ \text{is a bijection between}\ A\ \text{and}\ B.$$

Are the definitions of (standard) infinite and Dedekind-infinite equivalent?

##

Definition. A set $C$ is countable if and only if there exists a surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow out from $\mathbb{N}$, $ge 1$ arrow in to $C$.)

Definition. A set $C$ is countably infinite if and only if there exists a bijection between $C$ and $\mathbb{N}$.

Must a countable set that is Dedekind-infinite be countably infinite?

Prove that these sets are countable: $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$ (rationals), $\emptyset$, $\mathbb{N} \cup (\mathbb{N} \times \mathbb{N}) \cup (\mathbb{N} \times \mathbb{N} \times \mathbb{N})$, all finite sequences of elements of $\mathbb{N}$.

Problem Set 6 Comments (Tue, 1 Nov 2016)

The solutions and comments for PS6 are now posted in collab: PDF.

Problem Set 8 (Fri, 28 Oct 2016)

Problem Set 8 is now posted, and is due on Friday, 4 November at 6:29pm.

Class 17: Structural Induction (Thu, 27 Oct 2016)

### Schedule

Problem Set 7 is due tomorrow at 6:29pm.

Next week Friday, 4 November at 11am, Steve Huffman (BSCS 2005, co-founder and CEO of Reddit) will give a Computer Science Distinguished Alumni talk in the Rotunda. If you would like to meet with Steve (either at a lunch after the talk or a meeting with students later that afternoon), send me an email with a good reason why you should be invited (only a very limited number of spaces available).

# Lists

Definition. A list is an ordered sequence of objects. A list is either the empty list ($\lambda$), or the result of $\text{prepend}(e, l)$ for some object $e$ and list $l$.

\begin{equation} \begin{split} \text{\em first}(\text{prepend}(e, l)) &= e
\text{\em rest}(\text{prepend}(e, l)) &= l
\text{\em empty}(\text{prepend}(e, l)) &= \text{\bf False}
\text{\em empty}(\text{\bf null}) &= \text{\bf True}
\end{split} \end{equation
}

Definition. The length of a list, $p$, is: \begin{equation} \begin{split} \begin{cases} 0 & \text{if}\ p\ \text{is \bf null}
\text{\em length}(q) + 1 & \text{otherwise}\ p = \text{\em prepend}(e, q)\ \text{for some object}\ e\ \text{and some list}\ q
\end{cases} \end{split} \end{equation
}

def list_length(l):
if list_empty(l):
return 0
else:
return 1 + list_length(list_rest(l))



Prove: for all lists, $p$, list_length(p) returns the length of the list $p$.

## Concatenation

Definition. The concatenation of two lists, $p = (p_1, p_2, \cdots, p_n)$ and $q = (q_1, q_2, \cdots, q_m)$ is $$(p_1, p_2, \cdots, p_n, q_1, q_2, \cdots, q_m).$$

Provide a constructuve definition of concatenation.

# ##

Prove. For any two lists, $p$ and $q$, $\text{length}(p + q) = \text{length}(p) + \text{length}(q)$.

# ##

## Induction Summary

\begin{center} \begin{tabular}{lccc} & {\bf Regular Induction} & {\bf Invariant Principle} & {\bf Structural Induction} \ \hline Works on: & natural numbers & state machines & data types
To prove $P(\cdot)$ & {\em for all natural numbers} & {\em for all reachable states} & {\em for all data type objects}
Prove {\bf base case(s)} & $P(0)$ & $P(q_0)$ & $P(\text{base object(s)})$
and {\bf inductive step} & $\forall m \in \mathbb{N} \ldotp$ & $\forall (q, r) \in G \ldotp$ & $\forall s \in \text{\em Type} \ldotp$
& $P(m) \implies P(m+1)$ & $P(q) \implies P®$ & $P(s) \implies P(t)$
& & & $\quad \forall t\ \text{constructable from}\ s$ \ \end{tabular} \end{center}

# Challenge-Response Protocols

1. Verifier: picks random challenge, $y$.

2. Prover: proves knowledge of $x$ by revealing $f(x, y)$.

3. Verifer: can verify prover knows $x$ from response, but learns nothing (useful) about $x$.

How can you know the website you are sending your password to is what you think it is?

Class 16: Recursive Data Types (Tue, 25 Oct 2016)

### Schedule

You should read MCS Chapter 7 this week.

Problem Set 7 is due 28 October (Friday) at 6:29pm.

Python code from class and list definitions: pairs.py

# Structural Induction

We can show a property holds for all objects of a data type by:

1. Showing the property holds for all base objects.

2. Showing that all the ways of constructing new objects, preserve the property.

What is the difference between scalar data and compound data structures?

#

# Pairs

Definition. A $\text{\em Pair}$ is a datatype that supports these three operations:
\begin{quote} $\text{\em make_pair}: \text{\em Object} \times \text{\em Object} \rightarrow \text{\em Pair}$
$\text{\em pair_first}: \text{\em Pair} \rightarrow \text{\em Object}$\
$\text{\em pair_last}: \text{\em Pair} \rightarrow \text{\em Object}$\
\end{quote} where, for any objects $a$ and $b$, $\text{\em pair_first}(\text{\em make_pair}(a, b)) = a$ and $\text{\em pair_last}(\text{\em make_pair}(a, b)) = b$.

# Lists

Definition (1). A List is either (1) a Pair where the second part of the pair is a List, or (2) the empty list.

Definition (2). A List is a ordered sequence of objects.

## List Operations

\begin{equation} \begin{split} \text{\em first}(\text{\em prepend}(e, l)) &= \fillin
\text{\em rest}(\text{\em prepend}(e, l)) &= \fillin
\text{\em empty}(\text{\em prepend}(e, l)) &= \text{\bf False}
\text{\em empty}(\fillin) &= \text{\bf True}
\end{split} \end{equation
}

Definition. The length of a list, $p$, is: \begin{equation} \begin{split} \begin{cases} 0 & p\ \text{is \bf null}
\bigfillin %\text{\em length}(q) + 1 & p = \text{\em prepend}(e, q)\ \text{for some object}\ e\ \text{and some list}\ q
\end{cases} \end{split} \end{equation
}

Unique Construction property:

\begin{equation} \begin{split} \forall p \in \text{\em List} - { \text{\bf null} } \ldotp \exists q \in \text{\em List}, e \in \text{\em Object} \ldotp p = \text{\em prepend}(e, q) \; \wedge
(\forall r \in \text{\em List}, f \in \text{\em Object} \ldotp p = \text{\em prepend}(f, r) \implies r = q \wedge f = e) \end{split} \end{equation
}

Why is this necessary for our length definition?

##

def list_prepend(e, l):
return make_pair(e, l)

def list_first(l):
return pair_first(l)

def list_rest(l):
return pair_last(l)

def list_empty(l):
return l == None

def list_length(l):
if list_empty(l):
return 0
else:
return 1 + list_length(list_rest(l))



Prove: for all lists, $p$, list_length(p) returns the length of the list $p$.

Problem Set 7 - Revised (Sun, 23 Oct 2016)

A revised version of Problem Set 7 is now posted. The change is that an additional constrait was added to the state machine transitions (G):

bB . (ai, b) ∉ pairings

This constraint is needed since without it, a member of A might give up a better match for a worse one!

(Thanks especially to Luke Botti for noticing this problem.)

Problem Set 7 (Fri, 21 Oct 2016)

Problem Set 7 is now posted, and is due on Friday, 28 October at 7:29pm.

Class 15: Stable Matchings (Tue, 18 Oct 2016)

### Schedule

There is no class Thursday (Oct 20). Please use the class time to do something worthwhile and fulfilling, preferably outdoors.

Problem Set 6 (is posted now) is due 21 October (Friday) at 6:29pm.

We didn’t get to talk about Secure Stable Mathing today, but will in a future class. (For now, feel free to read the links, of coure.)

How Game Theory Helped Improve New York City’s High School Application Process, New York Times, 5 December 2014.

National Resident Matching Program (how medical school graduates are matched to residency programs)

Can anyone else see my rank order list (ROL)?
Your rank order list is confidential. Program rank order lists can be seen only by the program director and coordinator, the institutional official and administrator, and NRMP staff (unless you give your username and password to someone else, which is a violation of the Match agreement). (Frequently Asked Question on NRMP)

Secure Stable Matching: Jack Doerner (UVA BSCS and Studio Art, 2015), David Evans, abhi shelat. Secure Stable Matching at Scale. In 23rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. 24-28 October 2016.

# Stable Matching

Definition. $M = { (a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n) }$ is a stable matching between two sets $A = { a_1, \cdots, a_n }$ and $B = { b_1, \cdots, b_n }$ with respective preference orderings $\prec_A$ and $\prec_B$ if there is no pair $(a_i, b_j)$ where $bi \prec{a_i} b_j$ and $aj \prec{b_j} a_i$.

How do we know there is always a stable matching between any two equal-size sets?

##

# Gale-Shapley Algorithm

def gale_shapley(A, B):
pairings = {} # dictionary b: a pairings
unpaired = set(a for a in A.keys()) # unpaired a's
proposals = {a: 0 for a in A.keys()} # keep track of who gets next proposal

while unpaired:
a = unpaired.pop()
ap = A[a] # a's preference list
assert proposals[a] < len(ap)
choice = ap[proposals[a]]
proposals[a] += 1
if choice in pairings: # a's choice already has a match
amatch = pairings[choice]
bp = B[choice]
if bp.index(a) < bp.index(amatch):
pairings[choice] = a
else:
else:
pairings[choice] = a
return [(a, b) for (b, a) in pairings.items()]

A = {"Anna": ["Kristoff", "Olaf"], "Elsa": ["Olaf", "Kristoff"]}
B = {"Kristoff": ["Anna", "Elsa"], "Olaf": ["Elsa", "Anna"]}
gale_shapley(A, B)


## Modeling the Gale-Shapley program as a state machine

$S =$

$G =$

$q_0 =$

Prove termination. The Gale-Shapley program, modeled by the state machine, eventually returns.

#

#

Prove correctness. The Gale-Shapley program returns a stable matching of the two input sets and preferences.

Problem Set 6 (Fri, 14 Oct 2016)

Problem Set 6 is now posted, and is due on Friday, 21 October at 6:29pm.