cs2102: Discrete Math

Fall 2017 Course (Fri, 17 Mar 2017)

cs2102 will be offered again in Fall 2017, co-taught by Mohammad Mahmoody and David Evans.

Some things about the course are likely to change substantially for Fall 2017, but you can see what was done in the Fall 2016 course here.

Final Exam Solutions (Thu, 15 Dec 2016)

The solutions to Final Exam are here: Final Exam Solutions. (I promise, no Harambe mentions, other than in quotes.)

Problem Set Omega Highlights (Wed, 14 Dec 2016)

Here are some interesting submissions for Problem Set Omega (roughly grouped by topic). Thanks for all the entertaining and illuminating submissions!

# Logic

Logical Operators

**Helen Simecek**

Carlos Goes Birdwatching (A story about binary operations for middle school students)

**Derrick Chien Huang, Andrea Chang, Jennifer Qian**

Binary Relation Properties (comics)

**Lalita Mallapragada**

Logic Game [JAR]

**Temuulen Khurelbaatar**

**Yiming Wang, Mike Wang, Yingqing Huang**

# Set Theory

Sets and Superheroes

**Matt Huo, Joe Karaki**

Angry Birds: Set Relations

**Brian Li**

To Infinite Sets and Beyond!

Justin Barry, Monique Mezher, Robert Klemchek, Ayman Mobin

Call of Duty and Countable Infinities

**Aarron Braxton, Shreyas Hirway **

# Induction

Induction Rap

**Milan Bharadwaj**

Recursive Nesting Dolls

**Casey Bowler**

Six Degress of Separation [PPTX]

**Fan Feng**

Tracy’s Christmas Question [PDF]

**Ryann Consalo, Megan Greatorex**

Basketball Induction

**Josh Davis**

**Muhammad Sareini**

# State Machines

Baseball Game State Machine

**Mason Au, Bobby Stephens, and Kevin Warshaw**

A Beginner’s Manual to Dust Cultivation

**Jessica Emmons**

Echo Chamber: The Greatest Model of 2016 Voter Behavior

**Neel Kaushal and Arpit Rupakhetee**

Gumball State Machine

**Priya Nakhre**

Modeling Mario Party with State Machines

**Benjamin Fuhrman**

State Machines and Breakdancing

**Kenny Le**

Java Knights (code in Word document)

**Connor Albrecht, William Brayshaw, Matthew Anderson**

Halted (Lyrics for *Pieces* by Sum 41)

Rick Yanhao Zhao

# Recursive Datatypes

Recursive Data Types for Introductory CS Students

**Matthew Keitelman**

Recursive Music

Jiahong Chen, WenBin Qi

Bifurcating Trees

Youbeen Shim, James Mekavibul

# Stable Matching

The Bachelor (Stable Matching Dating Show!)

**Samantha Chu, Nicole Pope, Nancy Lee**

5 Disney Princesses (to the tune of “5 Little Monkeys”)

Nirali Shah

Pokemon: I Choose You (A Beginner’s Guide to the Gale-Shapely Algorithm) [Slideshow]

**Ying Lai, Chris Fassoth, Barry Chin, Rachel Yi**

Stable Marriage: Harry Potter Edition (Game)

Utkarsha Bhave, Anne Marie Lee, Jessica Virden

Gingerbread Matching

**Baylor Towne**

Stable Matchmakers (Comic) [PDF]

**Lauren Phan, Grace Harders**

Gale-Shapley’s Hotline Bling [PDF]

**Karan Dhillon, Bennett Clougherty, Jessica Ewing**

Anna Wu, Lan Jiang

A Millennial’s Guide To Discreet Stable Matching (as explained with Tinder)

Fazlah Rahaman

Harry Potter house matching [Code]

Mengjia Luo, Allison Chow

Gale-Shapley Comic

Meeka Meng

Stable Matching [Taxman Lyrics]

Sahan Pandey

# Proof Methods

Santa Claus: [PPTX]

**Winston Frick**

Phenomenal Proof (based on Maya Angelou’s *Phenomenal Woman*)

**Zeeshan Mir**

# Unclassifable

Discrete Dubs (W’s) (Rap Song)

Nicholas Georgiou, Melony Bennis, Noah Harlow, Justin Mooney, Amelia Naegele, Emma Bono

Nancy Zhang, Peter Cybriwsky, Sohum Sontakke

Class 26: Wrap-Up (Tue, 6 Dec 2016)

### Schedule

Your final (optional) submission for **Problem Set Omega**
is due by **11:59pm** tonight (**Tuesday, 6 December**). You may
revise and update earlier submissions until this deadline.

The **final exam** is scheduled by the registrar for **Saturday, 10
December, 9am-noon** in our normal classroom. See the Final Exam
Preparation handout for more information and some
**practice problems**.

## Links

Here’s Jeremy Kun’s essay on *Habits of Highly Mathematical People* (to re-read from the beginning of class)

Helen Simecek,

*Logical Operators*

Milan Bharadwaj,

*Induction Rap*

(More psO submissions will be posted on the course site later…)

Practice Problems Solutions (Fri, 2 Dec 2016)

After you have tried to solve the practice
problems on your own, you can obtain solutions
to them using this form:
*https://goo.gl/forms/qZVZJD8HHMc2C5XQ2*.

Class 25: Cryptography (Thu, 1 Dec 2016)

### Schedule

*Lighting of the Lawn* is **tonight**! (Starts around 7pm)

If you would like to present something to the class, you need to
submit **Problem Set Omega** by **Sunday, 4 December** at
**6:29pm**. Your submission should include an answer to “Presentation
option” question:

Presentation option: if you would like to present in class Tuesday, write a brief explanation of what you would like to do and how much time you are requesting for it. You can also include anything you want to make a compelling case for why your project should be selected (depending on how many requests for presentation their are, it may be necessary to select only as many as fit into the class).

Your final (optional) submission is due **Tuesday, 6 December**. You
may revise and update earlier submissions until this deadline.

The **final exam** is scheduled by the registrar for **Saturday, 10
December, 9am-noon** in our normal classroom. See the Final Exam
Preparation handout for more information and some **practice problems**.

# Symmetric Cryptography

Correctness: $D(K, E(K, M)) = M$

Security: without $K$, it is hard to learning anything interesting about $M$ from $E(K, M)$.

Why is $\oplus$ (xor) such a useful operator for cryptography?

#

**Perfect cipher** (Claude Shannon, 1940s). The ciphertext reveals no
information (other than maximum length) about the plaintext.

Why must a perfect cipher have $|K|\, \ge\, |M|$? ($K$ is the set of possible keys, $M$ is the set of plaintext messages)

#

Why is a one-time pad impractical for most purposes? How do you break a “two”-time pad?

# Asymmetric (Public Key) Cryptography

\small

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.

Whit Diffie and Martin Hellman,New Directions in Cryptography, November 1976

\normalsize

**Primitive root.** $\alpha$ is a primitive root of $q$ if $\forall 1 \le n < q \ldotp \exists m, 1 \le m < q\ \text{such that}\ \alpha^m = n \mod q$. All prime numbers have primitive roots.

### Diffie-Hellman-Merkle Key Agreement

**Goal:** Alice and Bob agree on a secure key $K$, over an insecure channel with no prior agreement.

**Assumption:** Discrete log problem is hard (for sufficiently large inputs).

Choose and public the public parameters:

$q$, large prime number $\alpha$, primitive root of $q$Alice generates random $X_A$.

Alice sends $Y_A = \alpha^{X_A} \mod q$.

Bob generates random $X_B$.

Bob sends $Y_B = \alpha^{X_B} \mod q$

Alice computes $K = (Y_B)^{X_A} \mod q$ / Bob computes $K = (Y_A)^{X_B} \mod q$.

How do we know Alice and Bob will agree on the same key, $K$?

##

What would an eavesdropper need to do to learn $K$?

##

# Secure Multi-Party Computation

How can we compute a stable matching without revealing sensitive preferences?

Class 24: Halting Problems (Tue, 29 Nov 2016)

### Schedule

**Problem Set Omega** is due on **Sunday, 4 December** or
**Tuesday, 6 December** (see problem set for details). It is not like
the others, and counts as a “bonus” optional assignment.

The **final exam** is scheduled by the registrar for **Saturday, 10
December, 9am-noon** in our normal classroom. See the Final Exam
Preparation handout for more information on the final and
some **practice problems**.

## Links

Ali G on Science (possibly offensive, watch at your own risk!)

Numberphile on the Halting Problem (HT: John Fry)

## Turing Machine Definitions

$$
TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)
$$

$S$ is a finite set (the “in-the-head” processing states)

$\Gamma$ is a finite set (symbols that can be written on the tape)

$\text{\em dir} = { \text{\bf Left}, \text{\bf Right}, \text{\bf Halt} }$ is the direction to move on the tape.

An *execution* of a Turing Machine, $TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)$, is a (possibly infinite) sequence of **configurations**, $(x_0, x_1, \ldots)$ where $x_i \in \text{\em Tsil} \times S \times \text{\em List}$ (elements of the lists are in the finite set of symbols, $\Gamma$), such that:

- $x_0 = (\text{\bf null}, q_0, \text{\bf input})$
- and all transitions follow the rules (need to be specified in detail).

# Recognizing Languages

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **accepts** a string *x*, if there is an execution of *M* that
starts in configuration $(\text{\bf null}, q_0, x)$, and terminates in
a configuration, $(l, q_f, r)$, where $q*f \in q*{Accept}$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **recognizes** a language $\mathcal{L}$, if for all strings $s
\in \mathcal{L}$, $M$ accepts $s$, and there is no string $t \notin L$
such that $M$ accepts $t$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **decides** a language $\mathcal{L}$, if for all strings $s \in
\mathcal{L}$, $M$ accepts $s$, and for all strings $t \notin L$, $M$
*terminates* in a non-accepting state.

A language $\mathcal{L}$ is **Turing-recognizable** if there is some
Turing Machine that recognizes it. A language $\mathcal{L}$ is
**Turing-decidable** if there is some Turing Machine that decides it.

Are all Turing-decidable languages Turing-recognizable?

##

Are all Turing-recognizable languages Turing-decidable?

# Undecidable Languages

$$ \text{SelfRejecting} := { w \in \Sigma^{*} \, | \, w \notin \mathcal{L}(M(w)) } $$ where $M(w)$ is the Turing Machine described by string $w$ if $w$ describes a valid Turing Machine, otherwise, a $M(w)$ is a machine that rejects all inputs.

Is there a $M*{SR} = M(w*{SR})$ that recognizes the language $\text{SelfRejecting}$?

#

$$ A_{TM} = { (w, x) \, | \, M(w)\ \text{accepts on input}\ x } $$

Is the language $A_{TM}$ Turing-recognizable?

#

Is the language $A_{TM}$ Turing-decidable?

#

#

#

$$ Halts_{TM} = { (w, x) \, | \, M(w)\ \text{terminates on input}\ x } $$

#

```
def paradox():
if halts('paradox()'):
while True:
pass
```

Final Exam Preparation (Mon, 28 Nov 2016)

## Final Exam

The final exam is scheduled by the registrar for **Saturday, 10
December, 9am-noon** in our normal classroom. The final will cover
everything in the course, with an emphasis on the most important
concepts that have appeared in at least two places.

Most of the questions on the final will be small variations on problems you have already seen on previous exams or problem sets. Doing well on these questions will make a strong case for earning at least a B in the class. A few of the problems will be designed to see how well you can use concepts you have learned in the class to solve problems unlike ones you have already seen. Doing well on many of these questions will make a strong case for earning an A in the class.

The format will be fairly similar to Exam 1 and Exam 2, but because of the extended time for the final, and the desire to give as much opportunity as possible for students to demonstrate what you can do, will be a bit longer than those exams.

As with Exam 1 and Exam 2, you will be permitted to use a **single
paper page of notes that you prepare and bring to the exam**, but no
other resources. 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.

**Unlike the previous exams, you must turn in your notes page with
your exam.** If you would like to keep your own copy of it, you should
make a copy to save before the exam.

## Expected Problems

Although the exam covers the whole class, you should not be surprised if it includes problems for you to demonstrate:

Your understanding of

**logical formulas**,**inference rules**, and an ability to reason about and manipulate formulas using**quantifiers**.Your fluency with standard proof techniques including

**proof-by-contradiction**.Your understanding of

**well-ordering**and how to construct proofs using the**well ordering principle**.Your understanding of

**sets**, how the set operators are defined, and what they mean.That you can do a

**regular induction**proof similar to ones you have seen on previous exams*very well*. That you can do an induction proof that requires some creativity to**define a good induction predicate**and then to complete the proof.Your understanding of

**state machines**, and ability to use the**invariant principle**to prove a property of the reachable states for a given state machine.Your understanding of

**recursive data types**, ability to define functions on recursive data types, and to use**structural induction**to prove a property about all objects of a recursive data type.Your understanding of infinite cardinalities including the ability to determine if a set is

**countable**or**uncountable**, and to support your answer with a convincing proof.Your understanding of

**Turing Machines**and**computability**. (See practice problems.)

## Practice Problems

Since there was no problem set covering Classes 23–25, here are some practice problems to help you prepare for the final. You do not need to turn in your solutions to these problems, but it is highly recommended that you approach them similarly to a problem set to be well prepared for the final. You should not be surprised to see problems similar to these on the final exam.

Prove that all well-ordered sets are countable.

The way we defined an execution of a Turing Machine in Class 23 suggested that there could be more than one execution of a Turing Machine, $TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q

*0 \in S, q*{Accept} \subseteq S)$, on a given input $I$. What property of $T$ would ensure that there is only a single execution possible?

For the following questions, a *deterministic* Turing Machine is a
Turing Machine that for every possible input has a single execution.
That is, there is no input for which the Turing Machine has more than
one possible execution.

Describe a deterministic Turing Machine that never halts but never repeats a configuration.

Prove that a deterministic Turing Machine that repeats a configuration never halts.

Consider the Turing Machine, $M_X$, defined below. (The $\text{\bf -}$ symbol denotes a blank square, which may not appear in the input. Every square to the right of the last input symbol is initially blank.) Hint: for questions 5 and 6 you should be able to use similar techniques to how we reasoned about state machines, but need to also take into account the tape (so instead of using the invariant principle for states as before, now you need to consider it for full machine configurations).

\begin{equation*}
\begin{split}
M_X = ( & S = { A, B, C, D },
& T = { (A, \text{\bf 0}) \rightarrow (B, \text{\bf X}, \text{\bf R}), (A, \text{\bf -}) \rightarrow (D, \text{\bf -}, \text{\bf Halt})
& \qquad \;\,\, (B, \text{\bf 0}) \rightarrow (B, \text{\bf 0}, \text{\bf R}), (B, \text{\bf -}) \rightarrow (C, \text{\bf -}, \text{\bf L}),
& \qquad \;\,\, (C, \text{\bf 0}) \rightarrow (C, \text{\bf 0}, \text{\bf L}), (C, \text{\bf X}) \rightarrow (A, \text{\bf X}, \text{\bf R}) }, \
& q*}

*0 = A, q*{Accept} = { D } ) \end{split} \end{equation

Prove that $M_X$ running on any initial tape with finite input (that is, the number of non-blank squares is $k \in \mathbb{N}$) always terminates.

Prove that $\mathcal{L}(M_X) = \text{\bf 0}^*$ (that is, the language recognized by $M_X$ is the set of all strings of zero or more $\text{\bf 0}$ symbols).

Trees Challenge (Mon, 28 Nov 2016)

Henry Spece has solved Challenge 7:

**Challenge 7.**From Class19: Determine the carinality of the set of all

*Tree*objects (as defined on PS8), and provide a convincing proof supporting your answer.

Henry’s proof is below:

The set of *Tree* objects is *countable*.

The following already proven theorems are used:

- The set of all strees is countably infinite.
- the set of all finite sequences of natural numbers is countable.
- The cartesian product of two countable sets is also countable.
- The sub-set of a countable set is countable.

We prove that the set of all trees with natural number labels is countable by finding a total injective mapping between the set of all trees and a set which is known to be countably infinite.

The set to which we are mapping the trees is the cartesian product of the set of finite sequences of natural numbers and the set of all strees. We already know that the set of all strees is countable, as well as the set of all finite sequences of natural numbers. Because the cartesian product of two countable sets is also countable, the cartesian product of these two sets must be countable, and a total injective mapping between the trees and this set would prove the set of all trees to also be countably infinite.

It is possible to imagine a mapping that links a tree to a stree, representing its structure, and a list of its labels, “in-order.” This is effectively “breaking apart” the tree into its components, resulting in two more manageable data types, or one element of the set defined above.

The function is defined more rigorously below, in two parts:

*Part 1* (helper function):

getStree := tree -> stree getStree(null) = null getStree(combine(t1,N,t2)) = combine(getStree(t1),getStree(t2))

*Part 2* (helper function):

getSequence := tree -> sequence getSequence(null) = empty sequence getSequence(combine(t1,N,t2)) = concatenate(getSequence(t1),N,getSequence(t2))

*Combined* (the relation being defined for the proof):

splitTree := tree -> (stree, sequence) splitTree(t) = (getStree(t),getSequence(t))

This relation is defined for all trees, making it total, and produces a unique stree-sequence combination for each tree, making it injective.

Because we have defined a total injective relation between the trees and another set which is known to be countable, the set of all trees must be countable.

Problem Set 9 Solutions and Comments (Sun, 27 Nov 2016)

The Problem Set 9 solutions are now posted: [PDF]

Its a good idea, of course, to read this carefully and ask questions about anything that is unclear.