CS 70 Spring 2018
PRINT Your Name:
SIGN Your Name:
PRINT Your Student ID:
PRINT Your Exam Room:
Name of the person sitting to your left:
Discrete Mathematics and Probability Theory Ayazifar and Rao
,
Midterm 1
(last)
(first)
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 12 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 54 parts) on this exam worth a total of 152 points.
Do not turn this page until your instructor tells you to do so.
CS 70, Spring 2018, Midterm 1 1
SID:
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. (¬(P∧¬Q)) ≡ (P =⇒ Q)
2. ∀n∈N,∃n′ ∈N, n′ >n.
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)
4. (∀n ∈ N,¬P(n+1) =⇒ ¬P(n)) =⇒ (¬P(0)∨∀n ∈ N,P(n)).
hTrue hFalse hTrue hFalse
hTrue hFalse
hTrue
hFalse 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 .
hTrue hFalse
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.
hTrue hFalse
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.
hTrue hFalse
2
SID:
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.
9. No woman can have her optimal partner in the traditional marriage algorithm.
hTrue hFalse
hTrue hFalse
10. There are at most 2 stable pairings for any stable matching instance: the male optimal one and female optimal one.
11. There is no stable pairing for any stable roommates instance with 2n people.
hTrue hFalse
hTrue hFalse
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.
13. For a directed graph, the sum of the outdegrees equals the sum of indegrees.
hTrue hFalse
hTrue hFalse
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?
15. Any graph where every vertex has degree at least 2 is connected.
hTrue hFalse
hTrue hFalse
16. A graph where every vertex has degree at least d requires at least d colors to vertex color it.
hTrue
hFalse
3
SID:
17. Any connected graph with average degree strictly less than 2 is a tree.
18. If gcd(x,y) = d and gcd(a,b) = d′, then gcd(ax,by) = dd′
19. If m is not prime, then for every x there is no multiplicative inverse for x (mod m).
20. If m > n, then gcd(m,n) = gcd(m−n,n).
hTrue hFalse
hTrue hFalse
hTrue hFalse
hTrue hFalse
21. For a prime p, any a that is relatively prime has {a,a2,…,ap−1} being all distinct modulo p.
hTrue
hFalse
4
SID:
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.
2. How many faces are in an n-vertex planar graph with n + 10 edges?
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?
4. What is the minimum number of leaves in an n-vertex tree?
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.)
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?
5
SID:
7. What time is 1000 hours after 1:00 PM? (You should include AM/PM.)
8. How many edges does one need to remove from a 4-dimensional hypercube to get a tree? (Answer is a number.)
9. What is the length of the shortest path (in number of edges) from the vertex 0101 to the vertex 1001 in a hypercube?
10. What is the maximum number of edges in a disconnected graph on n vertices?
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.)
6
SID:
12. What is ∑70 i2 (mod 5)? i=1
13. How many solutions are there to 5x = 5 (mod 10)? (Answer is a number)
14. How many solutions are there to 5x = 2 (mod 10)? (Answer is a number.)
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.)
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.
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. )
7
SID:
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.
hTrue hFalse
2. What is the maximum possible degree of a vertex in some n-vertex graph generated by this process?
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.)
4. Give an example of a graph that can be generated by this process that takes at least this many 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.)
8
SID:
4. Some Proofs.(5/5/5/6)
1. Prove:Ify