CS 70 Discrete Mathematics and Probability Theory
Spring 2018 Ayazifar and 1 Solutions
PRINT Your Name: Oski Bear SIGN Your Name: OS K I
Do not turn this page until your instructor tells you to do so.
Copyright By PowCoder代写 加微信 powcoder
CS 70, Spring 2018, Midterm 1 Solutions 1
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!
Answer: Note that the answers provide explanations for your understanding, even though no such justifica- tion was required
1. (¬(P∧¬Q)) ≡ (P =⇒ Q)
Answer: True. (¬(P∧¬Q)) ≡ ¬P∨Q ≡ (P =⇒ Q).
2. ∀n∈N,∃n′ ∈N, n′ >n.
Answer: True.Foreverynaturalnumberthereisabiggernaturalnumber.
For the following, assume Q(x, y) and P(x) are predicates over the domain of x, y.
3. (∀x,∃y,Q(x,y)∧P(x)) =⇒ ∀x,P(x)
Answer: True. One can pull P(x) outside of the exists to obtain (∀x,P(x)∧∃y,Q(x,y) and obtain ∀x, P(x) ∧ R(x) which implies ∀x, P(x).
4. (∀n ∈ N,¬P(n+1) =⇒ ¬P(n)) =⇒ (¬P(0)∨∀n ∈ N,P(n)).
Answer: True.Thisisthewellorderingprincipleformoftheprincipleofinduction.
For the next two parts, we consider two pairings S and T for a stable marriage instance and form a graph as follows; We take the vertices to be the people and the edges connect a man m, and woman w, if the pair (m,w) is in S or T (or both).
5. For any cycle in the graph for two pairings S and T , either all the men in the cycle prefer S or all the men in the cycle prefer T .
Answer: True. This is implied by the homework on Stable Marriage. A quick proof is that for if one man prefers S, his partner must prefer T for it to be stable, and her partner must then prefer S. This process continues around the cycle till one gets back to the original man. Thus, if one man prefers S than they all do.
6. If S is the male-optimal pairing, and T is the female-optimal pairing, and the graph of S and T consists of a single cycle then there are exactly two stable pairings.
Answer: False. Consider the 3-men, 3-women example, where each man has a different favorite woman for whom they are the least favorite man, and each woman has a different favorite man for whom they are the least favorite woman. All 3 pairings in this instance are stable.
7. In a stable marriage instance with n men and n women, let M be every woman’s last choice. For all 1 ≤ i ≤ n, there is a set of preference lists where M can end up with his ith choice after running the traditional stable marriage algorithm.
Answer: True, let all the other n−1 men have distinct first choices, all of which are not M’s ith choice. Then M will get rejected i − 1 times and the algorithm will terminate as soon as he reaches his ith choice (since no one else proposed to her).
8. For every n, there is a stable marriage instance with a stable pairing where every man and woman is paired with their least favorite in the preference list.
Answer: False. Every non-paired couple is rogue!
9. No woman can have her optimal partner in the traditional marriage algorithm.
Answer: False. There could be only one stable pairing in which case everyone gets their optimal partner.
10. There are at most 2 stable pairings for any stable matching instance: the male optimal one and female optimal one.
Answer: False. One can construct a solution by putting together two instances of stable marriage problems with a different male optimal and female optimal pairings. We augment the preference lists in each instance where the people don’t like the people in the other instance at all. There are at least four stable pairings now as each instance can either be male or female optimal for those in that instance.
11. There is no stable pairing for any stable roommates instance with 2n people. Answer: False.Therearepreferencesliststhatwouldallowforstablepairings.
12. Say I take a walk in any connected undirected graph, making sure I only traverse edges I haven’t traversed before. Suppose I get stuck at a vertex v because there are no unused edges I can use to leave v. If I never see the same vertex twice in the walk, v must have degree 1.
Answer: True. Since there is no cycle in the graph it is a simple path whose endpoints are degree 1.
13. For a directed graph, the sum of the outdegrees equals the sum of indegrees.
Answer: True. Each arc contributes one to the total outdegree and one to the total indegree.
14. Recall, adding an edge to a tree creates a cycle. Is it true or false that adding an edge to a tree also ensures that there are two different simple paths between any pair of vertices in the tree?
Answer: False. Consider a path, and add an edge between the first and third vertex. There is still a unique path between the fourth and fifth vertex.
15. Any graph where every vertex has degree at least 2 is connected.
Answer: False.Twodisjointcyclesisnotconnected.
16. A graph where every vertex has degree at least d requires at least d colors to vertex color it.
Answer: False.Anybipartitegraphistwocolorable.
17. Any connected graph with average degree strictly less than 2 is a tree.
Answer: True. If it is connected and has average degree less than 2 it must have |V | − 1 edges exactly. This means it is a tree.
18. If gcd(x,y) = d and gcd(a,b) = d′, then gcd(ax,by) = dd′
Answer: False. Consider a = y and b = x, then gcd(ax,by) = xy even if d = d′ = 1.
19. If m is not prime, then for every x there is no multiplicative inverse for x (mod m).
Answer: False. There is an inverse for any x where gcd(x, m) = 1. For example, m − 1 = −1 (mod m) and −12 = 1 (mod m) for every m regarding of whether m was prime.
20. If m > n, then gcd(m,n) = gcd(m−n,n).
Answer: True. This is the gcd mod theorem, which suggests that d|x and d|y, then d|x − y and vice versa, and then observing the two sets of divisors are the same and thus have the same maximum value.
21. For a prime p, any a that is relatively prime has {a,a2,…,ap−1} being all distinct modulo p. Answer: False. Consider a = 1 or a = m−1.
2. An expression or number: 3 points each. Clearly indicate your correctly formatted answer: this is what is to be graded. No need to justify!
1. Let P= “We should be honest.”, and Q = “We should be dedicated.”, and R =”We should be over- confident.” How should one write “We should be honest or dedicated, but not overconfident.” as an expression involving P,Q and R.
Answer: (P∨Q)∧¬R
2. How many faces are in an n-vertex planar graph with n + 10 edges? Answer: 12.v+f=e+2,sowehaven+f=n+12.
3. Consider a planar graph that has 30 faces. Add a vertex of degree 3 to the graph such that the resulting graph is planar as well. How many faces does the resulting graph have?
Answer: 32.Theadditionwillcutafaceintothree,soitaddstwofaces.OruseEuler.
4. What is the minimum number of leaves in an n-vertex tree? Answer: 2. A path has two leaves.
5. Consider a bipartite planar graph G that has v vertices, for v > 2. What is the maximum number of edges, expressed in terms of v, that G could have? (Answer is an expression or number.)
Answer: Euler’s formula: v+ f = e+2. If every face has length 4, we have that 2e = 4f, so v + e/2 = e + 2 or e = 2v − 4.
To achieve this, we consider K2,3, here the number of edges is 6 = 2(5) − 4.
6. What is the maximum number of connected components that can result from removing the edges in a length-k cycle from a connected graph?
Answer: k. Each vertex could be in a different connected component. In particular, the graph could be a cycle of length k. Also, the first edge removal cannot disconnect the graph, and each subsequent edge removal can split at most one connected component, thus the maximum number is 1 + k − 1 = k.
7. What time is 1000 hours after 1:00 PM? (You should include AM/PM.)
Answer: 5 AM. 1000 = 16 (mod 24) and 16 hours from 1:00 PM is 5:00 AM.
8. How many edges does one need to remove from a 4-dimensional hypercube to get a tree? (Answer is a number.)
Answer: 17.Thereare4(23)=32edgesinthehypercubeand16vertices,thusoneneedstoremove 17 edges to get to the 15 edges that a tree would have.
9. What is the length of the shortest path (in number of edges) from the vertex 0101 to the vertex 1001 in a hypercube?
Answer: 2. One has to correct 2 bits.
10. What is the maximum number of edges in a disconnected graph on n vertices?
Answer: (n−1)(n−2) . This is the case where we have a complete graph of n − 1 vertices, and one vertex
In general if a graph is not connected, there are at least two components. If one of the components has
k vertices and the other n − k, the maximum number of edges is k(k−1) + (n−k)(n−k−1) . 22
11. What is the smallest number of edges one needs to add to a graph on k vertices of odd degree such that it has an Eulerian tour? (You can use parallel edges if needed. For example, a two-vertex Eulerian graph must consist of at least two edges between the same two vertices.)
Answer: k/2. There are an even number of odd vertices, and pairing them up and adding an edge between them makes the degree even.
12. What is ∑70 i2 (mod 5)? i=1
Answer: 0. 12 + 22 + 32 + 42 + 52 ≡ 0 (mod 5). Every subsequent chunk of five, therefore, will also be divisible by 5.
13. How many solutions are there to 5x = 5 (mod 10)? (Answer is a number) Answer: 5.5xiseither0or5 (mod10).Itis0forhalfthepossiblevaluesof10.
that has no edges to any other vertex.
14. How many solutions are there to 5x = 2 (mod 10)? (Answer is a number.) Answer: 0. 5x is a multiple of 5 which cannot be 2 (mod 10).
For the following 3 parts, consider that ax+bm = d, where gcd(x,m) = d, and d may be larger than 1.
15. Consider the equation xu = v (mod m). It has a solution for u if and only if v is a . (Your answer may involve the variables a,b,x,m and d.)
Answer: v is a multiple of d. If not, there is no solution, if yes there is a solution, as specified in the next problem.
16. If u is a solution to the equation xu = v (mod m) as above, write an expression for u in terms of possibly a,b,x,v,d,m and possibly including the mod function.
Answer: u = av/d (mod m/d).
17. Again consider the equation xu = v (mod m). How many solutions are there (mod m) if there is at least one? (Answer is an expression in terms of possibly a,b,x,v,d. )
Answer: d. Given a solution u, we have that u+i(m/d) is also a solution, and there d solution modulo m.
3. Make 3 Friends! (2/3/3/3/5)
Consider a process of building a n-vertex undirected graph with n > 3. Begin with a triangle, and then repeatedly add a vertex and 3 edges from that new vertex to 3 different previous vertices. Note that many different graphs can be generated by this process as the choice of which previous vertices to add edges to is unspecified. (Perhaps think of a party, where people arrive and choose 3 previous people to befriend. This would be the resulting undirected friend graph.)
1. True/False Any graph generated by this process is connected.
Answer: True. The graph is connected at time 3, and remains connected as one has to add an edge to some vertex in the graph.
2. What is the maximum possible degree of a vertex in some n-vertex graph generated by this process? Answer: n − 1. Every new vertex can be connected to vertex 1.
3. What is the minimum number of colors needed to color any n vertex graph generated in this fashion? (The next two answers depend on this so if you skip this, also skip them, though reading them may help.)
Answer: 4. See next two questions for reasoning.
4. Give an example of a graph that can be generated by this process that takes at least this many colors.
Answer: K4. The fourth vertex connects to the first three and K4 requires 4 colors.
5. Give an algorithm to generate an coloring that achieves your answer for part 3 for any graph generated according the process above. (You will recieve no credit if your answer is wrong for part 3 of this question. Apologies.)
Answer: Color vertices in the order they are added. With four colors, since each vertex connects to 3 previous ones, there is always a color available so that the vertex is colored differently than previous ones.
4. Some Proofs.(5/5/5/6)
1. Prove:Ify