cs2102: Discrete Math (Fall 2016)

Problem Set 8 Revisions (Thu, 3 Nov 2016)

There are three important revisions to Problem Set 8:

The definition of

*height*for Problem 4 should have included that the height of the**null**tree is 0.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**.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).

# Links

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

**Verifier:**picks random challenge, $y$.**Prover:**proves knowledge of $x$ by revealing $f(x, y)$.**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**.

# Structural Induction

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

Showing the property holds for all base objects.

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*):

*b*∈

*B*. (

*a*,

_{i}*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**.

# Links

Download the full matching code: matching.py (assertions and comments removed here for space)

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 *23 ^{rd} 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 $b*i \prec*{a_i} b_j$ and $a*j \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
unpaired.add(amatch) # lost match
else:
unpaired.add(a)
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**.