[SOLVED] CS CS 70 Spring 2019

CS 70 Spring 2019
PRINT Your Name:
SIGN Your Name:
PRINT Your Student ID:

Copyright By Assignmentchef assignmentchef

PRINT Your Exam Room:
Name of the person sitting to your left:
Discrete Mathematics and Probability Theory Ayazifar and Rao
Name of the person sitting to your right:
After the exam starts, please write your student ID (or name) on every odd page (we will remove the staple when scanning your exam).
We will not grade anything outside of the space provided for a problem unless we are clearly told in the space provided for the question to look elsewhere.
The questions vary in difficulty, so if you get stuck on any question, it might help to leave it and try another one.
On questions 1-2: You need only give the answer in the format requested (e.g., true/false, an expres- sion, a statement, a short argument.) Note that an expression may simply be a number or an expression with a relevant variable in it. For short answer questions, correct clearly identified answers will receive full credit with no justification. Incorrect answers may receive partial credit.
On question 3-6, do give arguments, proofs or clear descriptions if requested. If there is a box do use it for your answer.
You may consult only one sheet of notes. Apart from that, you may not look at books, notes, etc. Calculators, phones, computers, and other electronic devices are NOT permitted.
There are 14 single sided pages including the cover sheet on the exam. Notify a proctor immediately if a page is missing.
You may, without proof, use theorems and lemmas that were proven in the notes and/or in lecture.
You have 120 minutes: there are 6 questions (with 47 parts) on this exam worth a total of 140 points. The first is true/false and has 24 points, the second is short answer and has 57 points, the third has 15 points, the fourth has 12 points, the fifth has 14 points, and the sixth has 18 points. They are not necessarily in order of difficulty.
Graphs are simple and undirected unless we say otherwise.
CS 70, Spring 2019, Midterm 1 1

Do not turn this page until your instructor tells you to do so.

1. TRUE or FALSE?: 2pts each
For each of the questions below, answer TRUE or FALSE. No need to justify answer.
Please fill in the appropriate bubble!
1. (PQ)(P = Q) is true for all P and Q.
2. nN,yZ,n>y.
3. (nN,P(n)) = nN,P(n).
4. (A = B)(A = B).
hTrue hFalse
hTrue hFalse
hTrue hFalse
hTrue hFalse
5. For n > 2, there is a stable marriage instance of n men and n women in which the traditional marriage algorithm takes at least n2 days.
hTrue hFalse
6. If a stable pairing P has a pair (m, w) where P is optimal for both m and w, then every stable pairing is optimal for both m and w.
hTrue hFalse
7. If at any point in the traditional marriage algorithm a womans optimal partner proposes to her, then every stable pairing is optimal for her.
hTrue hFalse
8. There is an n-edge, n-vertex connected graph where each pair of vertices is connected by 2 disjoint paths. (Paths are disjoint if they do not share an edge.)
hTrue hFalse

9. Consider a function f :AB, where |A|=|B|. An inverse function for f is a function g:BA where x A, (g( f (x)) = x f (g(x)) = x). f () is a bijection if there is an inverse function.
10. f(x) = ax (mod m) is a bijection if and only if m is prime.
11. Any graph that is a simple cycle can be vertex colored with 2 colors.
12. For a hypercube of dimension 3, there is an edge between vertex 000 and 111.
hTrue hFalse
hTrue hFalse
hTrue hFalse
hTrue hFalse

2. Short Answer. 3 pts each.
Write your answer in the simplest form possible. You should use only the variables in the question unless otherwise specified.
1. Write a logical formula that describes the proposition: the square of any natural number is a natural number.
2. What is the number of edges in an n-vertex acyclic graph having k connected components?
3. What is the number of edges in a planar graph where every face has five sides? (Answer in terms of v, the number of vertices.)
4. Iftherearen/2leavesinann-vertextree,whatistheaveragedegreeoftheothern/2vertices?(Assume n is even.)
5. For a hypercube of dimension 4, how many edges (u, v) are there where u has a leading 0 and v has a leading 1?
6. What is the longest simple cycle in a d-dimensional hypercube, for d > 1?

7. For positive x,y, 2x = 1 (mod n) and 2y = 1 (mod n) what is 2gcd(x,y) (mod n)?
8. If xy < x/2, then y > . (The answer should be in terms of x.)
9. The least common multiple of two positive numbers m and n is the smallest positive number that is a multiple of both. What is the least common multiple of m and n in terms of m, n and d = gcd(m,n)?
10. What is the maximum number of solutions in {0,1,,n 1} to the equation ax = b (mod n) if gcd(n,a) = d? (Answer in terms of n and d.)
11. Whatisthesizeoftherangeofthefunction f(x)=ax (mod n)wherex{0,1,,n1}ifgcd(n,a)= d?
12. For a prime p, how many numbers in {0,1,,p2 1} have an inverse modulo p2? (Answer in terms of p.)
13. Givenxandmwithgcd(x,m)=d,andd=ax+bm,whatisavalueofzwherezx=5d (modm)?(In terms of some subset of the variables x,m,a,d and b.)

14. What is 275 (mod 73)?
15. Let p > 2 be prime. What is 2k(p1) (mod p)?
16. Find x (mod 20) that satisfies the equations: x = 2 (mod 4) and x = 4 (mod 5)?
17. If gcd(m,n) = 1, let x = a+km, what should k be to satisfy x = b (mod n)?
18. What are the last two digits of 4919? (Hint: gcd(4,25) = 1 and 24 = 1 (mod 25).)
19. A fixed point of a function is a value x where f (x) = x. Consider the function f (x) = x3 (mod mn) forrelativelyprimem>2andn>2. Notethatx=1,x=0,andx=1arefixedpointsforx3. Find another fixed point of f (). (Your answer can include m, n and their inverses.)

3. Short Proofs. 5 pts each.
1. Provethatifd| n2 thend| n.(d| nmeansnisnotamultipleofd.)
2. Prove by induction that (1x)n 1nx for any natural number n 1 and 0 < x < 1. 3. Prove that x2 = 7 has no rational solutions. 4. Sleepiness.1. (5 pts) Consider a set of intervals [s1,e1],…,[sn,en] where si is the start time and ei is the end time of an interval. The associated interval graph has a vertex for each interval and an edge between any pair of intervals that overlap; for example, if i1 = [3, 5] and i2 = [4, 6] and i3 = [6, 7], there are edges (i1 , i2 ), and (i2,i3) but no edge between i1 and i3.Prove that if there is a cycle in an interval graph then there is a point in time where at least 3 intervals overlap.2. (3 pts) Argue that for a graph G = (V,E), if |E| |V|, then G has a cycle.3. (4 pts) Seven students each fall asleep three times during CS 70 lecture. Furthermore, for every two of these seven students, there exists a time when both of them are sleeping. Prove that there must be some time when at least three students were sleeping at once. 5. Colorings.Define exploding a graph G as making a copy of it called G, and then adding an edge between each vertex v G and its copy v G. Note that exploding a graph doubles the number of vertices. So, exploding an (n 1)-dimensional hypercube gets us an n-dimensional hypercube.Jonathan has a graph G and wants to destroy all edges. At each step, he can choose to perform one of the following operations: Remove an odd-degree vertex and all its incident edges. Explode the graph.Prove to Jonathan that no matter what graph G he starts with, he can get rid of all edges in a finite number of operations.To help you out, we will break this down into parts. Define f (G) as the smallest number of colors needed to vertex-color G.1. (4 pts) Prove that exploding a graph where f (G) > 1 does not increase f (G).
2. (4 pts) Suppose every vertex in G has even degree, and let Gboom be its exploded graph. Given a coloring of Gboom, prove that you can remove all vertices of a particular color in Gboom. (Potentially in multiple steps.)

3. (2 pts) Prove that if f (G) = 1, then Jonathan is done.
4. (4 pts) Now finish the proof: prove that there exists a finite sequence of operations for Jonathan to destroy all edges. (You may use results from previous parts.)

6. Chicken Nuggets.
In this problem, we explore the conundrum that Jonathan and Emaan face when they visit McDonalds. The chicken nuggets are sold in boxes of two different quantities, and theyre interested in which quantities of chicken nuggets can be bought.
1. (3 pts) Find (x, y) that satisfy the equation 7x + 11y = 53, where x and y have to be non-negative integers, and y is as small as it can be. Hint: try taking mods of both sides to eliminate a variable first
2. (3pts)Explainwhy7x+11y=59hasnonon-negativeintegersolutionsfor(x,y).
3. Consider a store where chicken nuggets are sold in boxes of m and n with gcd(m, n) = 1. Buying x boxes of m chicken nuggets and y boxes of n chicken nuggets yields xm + yn chicken nuggets.
(a) (2 pts) For any solution to xm+yn = mnmn, what is x (mod n)?
(b) (4 pts) Argue that there is no solution for xm+yn = mnmn where x and y are both non- negative integers.

4. The following two parts will prove that mn m n is the largest number of chicken nuggets that cannot be bought.
(a) (3 pts) Prove that for any integer z, there is a solution to xm+yn = z where 0 x n1.
(b) (3 pts) Argue that for any z > mnmn, there is a solution to xm+yn = z where x and y are non-negative.

CS: assignmentchef QQ: 1823890830 Email: [email protected]