cs2102: Discrete Math

Final Exam Solutions (Sat, 16 Dec 2017)

Here are some comments on the Final Exam: PDF (and the Original Exam).

We hope everyone found the class worthwhile and enlightening. Have a great break!

Problem Set Omega Highlights (Tue, 12 Dec 2017)

Here are some of our favorite Problem Set Ω submissions (mostly in no particular order).

Max Rifkin

Evariste Galois Rap

Lindsey Shavers, Danielle Newman, Esther Boachie

Galois’s life Rapped

Megha Batra, Cathy Chang

Beauty of bijection, Leo Wang, Caroline Zhao

Learning relations through game of thrones, Yaxin Ren

Fun with sets, set operations and sequences

Sherry Li

Recursive Life

Wenjie Liu, Jia Tang, Yuxin Ji

Choosing the right door (game’s code) - for David Bowie fans, Samuel McBroom, Saeed Razavi, Jake Smith, James Chen, Daniel Zarco

Diffie Hellman key exchange explained

Taylor Rohrich, Cam Lloyd

A great site about soccer skills (approved by Dave and Mohammad), Angel Lam, Neely Egan

Learning number theory through comics, Arty Kosolwattana

Logical Operators, Sets, and Harry Potter

Taylor Rauch

Finite state Coca Cola machine, Thomas Shust

Teaching logical operators to local (UVa) people

Stephen Palathingal

Proof by contradiction vs. proof by contrapositive

Stephanie Tran, Arushi Kumar

A Discrete Mathematicians Guide to Dating

Sarah Lei, Bhavana Channavajjala, Regina Yap

A rap song on state machine

Surbhi Singh, Raghava Pamula, Anoop Sana

Playing the game of NIM against computer, Steve Phan, Aidan Barnes

Induction Rocks

Selwyn Hector

Project Name, Siddharth Ghatti

Jim, the farmer, learns logical operators

Reeya Rabena

007 using WOP

Rahat Maini, Sean Wolfe, John Watkins

Symmetric Key vs. Asymetric Key Encryption, Renee Mitchell

Song (Havana) about logical operations, Peter Tran, Tiffany Nguyen, Jazlene Guevarra, Victor Shen

Role of Induction in Star Wars

Phillip LeMaster

Binary operations for UVa students, Nitika Kataria, Vivian Pham

Cooking cardinality, Nick Van Dyke, Trey Nicholls

Rap about Logical expressions

Neha Chopra, Sanjana Hajela, Kajal Sheth

Explaining discrete math over Thanksgiving dinner

Matthew Jordan

Beethoven knew discrete math.

Makonnen Makonnen

Logical operators animated

Matthew Han

Learning discrete math through basketball, Mick O’Hanlon

The dude from discrete math learns about induction, Michael Wood

Defending earth using discrete intelligence!, Matthew Cockrell

Well Ordering Principle vs. WOP

Meghan Tonner

Binary Relations: An Interactive Diagram, Christopher Geier, Hamza Ilzyas

Sets using the Animal Kingdom

Charles “Michael” Chang

*If
I had a Proof* (A Song about Proofs and the Wizard of Oz), Avery Burton.

*Alice in LogicalOperatorLand*, Annie Sharkey.

Well-Ordering Principle is Hard

Devin Kim

The Story of Goldilocks and the Three (Boolean) Bears

Arjun Iyer, Abhishek Shinde, Chiraag Umesh, Vineeth Gaddam

Logical Operators for Kids!

Cory Ayers, Peter Worcester

Super Mario Sunshine and Sets

Elizabeth Henning

Well-Ordering Mystery

Eimara Mirza

Well-Ordering Principle (in terms of Food)

Emily Zou

Discrete Math in Everyday Life

Franklin Amaya and Aiden Smith

Handsome squidward (as a state machine), Gia-Han Nguyen

Proven: A Murder Mystery (Galois Musical!), Jared Taylor

The Infinite Dorm: The Ordering of Countably Infinite Sets EXPLAINED

Grace Wu, Sandy Gould, Kelly Xie, Helen Lin, Ryan Yi, Ruolin Chen

Logical Operators: A guide for current and prospective Feline owners, Helen Lim, Angelica Lavan

Hopscotch State Macine

Kelly McKee

Logical Operators in the Constitution

Habib Karaky, Kunal Chandak, Rishabh Nagpal, Shivani Saboo

State Machines

Isabel Kershner, Emily Roberts

Set Relations

Isaac Roberts, Siddhant Goel

Stall Seat Journal, Jessica Kain

Discrete Mario

James Hamil

Finite State Machines, Jack Workman

Rock Paper Scissors State Machines

Juan Palacio, Halsing Nordin

*The Fault in the Math: John Green and Infinity*, Joseph Kim

Rosie Learns Recursion, Jillian DeWoody

Boolean Operators

John Perez

Recursive Radio

Marcha Kiatrungrit, Cal Ries

Basketball and State Machine

Terry

Cartesian Products, Kelsey Irwin

Inference Rules: A Guide to Soundness

Carl Zhang, Peter Felland

Relations and Music

Daniel Seymour

Discrete Math Jeopardy, Anna Davis, Lavonte Brown

Lieutenant Confusion

Andrew Zhang

Recursive Hershey Bars

Bailey Snead

Chess App, Branden Kim, Shirley Wang

Escaping the Monster, by induction! , Joseph Park, Conner Hutson, Jared Tufts

Trump-Putin Key Exchange

Carter McGhee

A Guide to Writing Proofs for Discrete Math

Kaelyn Carroll, Joshua You

A Night On the Corner State Machine

Kristina Colevas

Relatable State Machines

Luke Emanuel, William Tonks

Class 27: Conclusion (Tue, 5 Dec 2017)

# Schedule

The **Final Exam** is this Thursday, 7 December, 9am-noon in the
normal classroom. See Final Exam Preparation for advice
on preparing for the final.

Prof. Evans will have his usual office hours tomorrow (2:30-3:30pm), and most of the TA office hours schedule for Wednesday will be held (but check the Slack group for any updates since some TAs may not be able to hold office hours tomorrow).

More of the PS Ω submissions will be posted on the course site later.

Problem Set 9 Comments (Sat, 2 Dec 2017)

The Problem Set 9 solutions and comments are now posted in collab: PDF

Final Exam Preparation (Fri, 1 Dec 2017)

The *Final Exam* will be Thursday, 7 December, 9am-noon in the 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. (Of course, we will also take into account your performance on other parts of the class including the exams and problem sets.)

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 x 11 inches), and you may write (or print) on both sides
of the page.

## 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

**number theory**, including the ability to reason about properties of prime and composite numbers, Abelian groups and fields.

## Practice Exam

The exam from last year’s course is available here: [PDF]. All of the questions from last year’s final would be reasonable questions for this year’s final except for 6d (we did not cover Turing machines this year) and 12. Last year’s final doesn’t include any questions on number theory since we didn’t cover that enough last year, but your final is likely to include a few number theory questions that you will be well-prepared for if you understand PS9. Otherwise, the content and format of this final is similar to what you should expect on your final.

You are strongly encouraged to try to solve the problems yourself, before consulting the Practice Final Solutions.

Problem Set Omega Submission (Fri, 1 Dec 2017)

The submission form for Problem Set Ω is here:

Submissions are due on **Monday, 4 December** at **11:59pm**. If you
would like to present something in class on Tuesday, 5 December,
please send your request (see the problem set page for
details) by **5:559pm** on **Monday, 4 December**.

Class 26: Counting and Probability (Thu, 30 Nov 2017)

# Recall

Last time, we went tover two basic counting problems. In both problems, we counted how many ways we can choose $k$ elements from ${1,\dots,n}$ whe the order of selection does matter; namely, we counted \emph{sequences} of length $k$. If repetition was allowed, the answer was $n^k$ (using the product rule) and if the repetition was not allowed, the answer was $n (n-1) \dots (n-k+1) = n!/(n-k)!$ using the generalized product rule.

Today, we will focus on a similar counting problem but in a scenario in which order does not matter. Before that, let’s recall the division rule.

**Division Rule**. If $f \colon A \to B$ is a $k$ to $1$ (total surjective) function, and if $A,B$ are finite sets then, $|A| = k \cdot |B|$.

# Counting when order does not matter

The number of subsets of size $k$ of ${1,\dots,n}$ captures a counting problem in which the order of the $k$ selected elements does not matter. This is denoted by ${n \choose k}$ and as we show, is equal to ${n \choose k} = \frac{n!}{k! (n-k)!}$.

The proof uses the division rule. Suppose $S_k$ is the set of all subsets of ${1,\dots,n}$ of size $k$ and let $T_k$ be the set of all \emph{sequences} of length $k$ using ${1,\dots,n}$ (where repetition is not allowed). As we saw before, we know that $|T_k|=n!/(n-k)!$. Now, we show a $\ell$-to-1 mapping from $T_k$ to $S_k$, for $\ell=k!$ which, by the division rule will imply that $|S_k|=\frac{n!/(n-k)!}{k!} = \frac{n!}{(n-k)! k!}$.

$\ell$-to-1 mapping from $T_k$ to $S_k$: Map any sequence $(a_1,\dots,a_k)$ to the set ${a_1,\dots,a_k}$. First note taht this is a total surjective function from $T_k$ to $S_k$. Furthermore, for any set $A={a_1,\dots,a_k}$ there are $k!$ permutations like $(b_1,\dots,b_k)$ of the same set $A$ (we proved that already!). Therefore, the mapping is $\ell$-to-1 for $\ell=k!$.

**when repetition is allowed**. Note that in the problem above, we cannot select the same element $i$ from ${1,\dots,n}$ more than once, but suppose we consider the selections to be “multi-sets” where the order of elements do not matter, but they could be selected more than once. This is a way to model the example problem from last class about donuts.

Give a bijection between the sets that model the following two counting problems: \begin{itemize} \item Selecting $k$ elements from ${1,\dots,n}$ as a “multi-set”; namely, the order of selection does not matter, but we \emph{can} select an element more than once. \item Number of sequences using elements from ${0,1}$ with exactly $k$ ones, and exaclty $n-1$ zeros. \end{itemize}

Using the above bijection, show that selecting $k$ donuts frm $n$ different varieties is possible in a total of ${n+k-1 \choose n-1}$ many ways.

#

## Basics of Probability

Probability theory is one of the richest and most beautiful mathematical theories with enormous applications. Here we take a very brief look at it, by using our counting techniques for estimating the “chance” of certaing “outcomes”.

Some of the basic questions we deal with in probability theory look like the following examples. \begin{itemize} \item Suppose a bag contains $10$ donuts and $5$ bagles. If we pick one of the items in the bad \emph{uniformly} (at random), what is the \emph{probability} that we pick a bagel. \item Suppose we do not put back the item that we selected in the previous example. Now, if we take another item, what is the chance that it is a donut \emph{conditioned} on the first item being a bagel? \end{itemize}

# Sample Space and Event

The sample space $\Omega= {x_1,\dots,x_n }$ includes all the possible outcomes and their own specific probability $\Pr[x*i]$, while the total summation is $1=\sum*{x\in \Omega} \Pr[x*i]$. An Event $E$ is simply a subset of the sample space $E \subseteq \Omega$, and its probability is defined to be $\Pr[E] = \sum*{x \in E} \Pr[x]$.

When we draw one item from a bag of $10$ donuts and $5$ bagles: \begin{itemize} \item What is the sample space? \item What is the probabilty of each outcome? \item What is the Event $B$ that we draw a bagel? \item What is the probability of $B$? \end{itemize}

# Conditional Probability

For two events $E,C$, the probability of $E$ hapenning \emph{conditioned} on $C$ happenin is denoted by $\Pr[E \mid C]$ and equal to $$\Pr[E \mid C] = \frac{\Pr[E \cap C]}{\Pr[C]}.$$

For example, for any non-empty $E$, we have $\Pr[E \mid E] = 1$, and for any disjoint events $E,C$ we have $\Pr[E \mid C]=0$.

What is the probability space of taking two items (without repetition) from the same basket of $10$ donuts and $5$ bagles? What is the formal definition of the event $B$ that the first item is a bagel? What is the formal definition of the event $D$ that the second item is a donut? What is the probability of $D$ conditioned on $B$?

Class 25: Counting (Tue, 28 Nov 2017)

### Schedule

Reminder for the schedule for the rest of the semester:

**Problem Set 9**: due on Friday, 1 December at 6:29pm.**Problem Set Omega**: due on Monday, 4 December at 11:59pm. See the Problem Set Omega description for examples from previous students.**Final Exam**: Thursday, 7 December, 9am-noon (in the normal lecture room)

Most of today’s class is covered in Chapter 15 of the MCS book.

# Examples

Today, we want to be able to answer the following questions. The first two are already discussed in class, but we will study them more generally. \begin{enumerate} \item How many subsets does $S$ have if $|S|=n$? \item How many numbers are there that can be represented with (at most) $n$ bits (in base 2) ? \item How many (at most) 16-bit numbers with exactly 4 ones? \item How many ways to choose 12 doughnuts from 5 varieties? \end{enumerate}

The first two questions have the same answer: $2^n$. In fact, because there is a bijection between the sets described in problem 1 and problem 2, then we already know that their answers must be the same.

More generally, all counting problems of today’s class could be described as “what is the size of a set $A$?” We use the definition of finite cardinality from Class 9, to study these questions. Namely, we try to find another set $B$ whose cardinality is known, and that there is a bijection between $A$ and $B$.

# Why Counting?

Being able to count (exactly or even approximately) is important for many reasons, some of which are: \begin{itemize} \item Estimating the “cost” of an algorithm, this could be time, space, etc. This comes up when we try to analyze the “efficiency” of an algorithm. \item Estimating the “security” of a cryptographic algorithm. Basically, we would like to know how big is the “space of keys” from which the adversary has to “guess” the correct one. \item Counting is the fundamental to probability theory. \end{itemize}

# Counting Rules

**Product Rule** If $A_1,\dots,A_n$ are finite sets, then the size of their cartesian product is
$$|A_1 \times \dots \times A_n| = |A_1| \cdot |A_2| \dots |A_n| $$

We previously saw this rule in Class 7, but we will use it more heavily today, and we will see some extensions of it.

Using the product rule, formally prove that the answer to the first two example problems are both $2^n$. (Hint, let $S={a_1,\dots,a_n}$ and let $A_i = {a_i,0}$.)

# # #

**Sum Rule**. If $A_1,\dots,A_n$ are finite \emph{disjoint} sets, then the size of their \emph{union} is
$$|A_1 \cup \dots \cup A_n| = |A_1| + |A_2| \dots +|A_n|.$$

The sum rule is even simpler than the product rule, but together with the product rule, they become very powerful.

Using the product and sum rules, count how many passwords of 6 to 8 characters exist if the first character can be an english letter (upper or lower case, so $26 \times 2$ possibilities) and the rest of the characters are either a letter or digit ($(26 \times 2) + 10$ possibilities).

#

**Generalized product rule.** Suppose $S$ is a set containing length-$k$ sequences like $(a_1,\dots,a_k)$. If there are $n_i$ possibilities for $i^{\text th}$ entry $a_i$ for any possible prefix $a*1,\dots,a*{i-1}$, then $|S|=n_1 \cdot n_2 \dots n_k$.

Using the generalizd product rule, prove that the number of permutations over any set $S={s_1,\dots,s_n}$ is $n!$. A permutation is simply a sequence $(a_1,\dots,a_n)$ where each $s_i$ appears in that sequence exactly once.

# # #

**Division Rule**. If $f \colon A \to B$ is a $k$ to $1$ (total surjective) function, and if $A,B$ are finite sets then, $|A| = k \cdot |B|$.

# Counting when order does not matter

The number of subsets of size $k$ of ${1,\dots,n}$ captures a counting problem in which the order of the $k$ selected elements does not matter. This number is so important that has its own notation ${n \choose k}$.

Using the division rule, prove that ${n \choose k} = \frac{n!}{k! (n-k)!}$

Class 24: Return of ROCA (Tue, 21 Nov 2017)

### Schedule

Happy Thanksgiving! (There is no class on Thursday.)

Here’s the updated (and final) schedule for the rest of the semester:

**Problem Set 9**: due on Friday, 1 December at 6:29pm.**Problem Set ω**(this is optional, and not like the others, hence it uncountable number): due on Monday, 4 December at 11:59pm. See the Problem Set ω description for examples from previous students.**Final Exam**: Thursday, 7 December, 9am-noon (in the normal lecture room)

## Links

Ron Rivest, Adi Shamir, and Leonard Adleman. *A Method for Obtaining Digital Signatures and Public-Key Cryptosystems*, 1977.

ROCA Attack: Paper PDF, Slides

Problem Set 9 (Sun, 19 Nov 2017)

**Problem Set 9** [PDF] is now posted and
is due **Friday, 1 Dec at 6:29:00pm**. Please read the
collaboration policy carefully.