CS 70 Discrete Mathematics and Probability Theory
Remote Proctoring Instructions.
• On questions 1-14: You need only give the answers on the “Final (Short Answers)” gradescope
assignment within the 3 hour time period of the exam. (No justification is required.)
Copyright By PowCoder代写 加微信 powcoder
• On questions 15-20, the answers should be written on one side of one page per question including all subparts. Therefore, you will need to scan 6 sheets of paper to a separate gradescope assignment called Final (PDF and long answers.). You are welcome to write directly on a copy of the exam for questions 15-20 if you wish. The solutions are short, so one page per question is a hard limit.
• The short answer assignment contains the questions. For the long answer questions download the PDF from the Final (PDF and long answers) gradescope assignment.
• Bothgradescopeassignmentswillbeavailableat3:00PMandthePDFfortheentireexamincluding short answers will be available on the “Final(PDF and long answers)” assignment.
• There will be no clarifications. If a problem part has an error, we will remove it from the exam.
• Youhave180minuteswhichincludesthetimetofillouttheanswersintheFinal(ShortAnswers) gradescope assignment and then an extra twenty minutes to scan your paper solutions to the Final (PDF for long answers) assignment.
• For long answers with boxes, the answers must be in the boxes for any credit.
• The questions vary in difficulty. In particular, some of the long answers at the end are quite accessible, and even those are in not necessarily in order of difficulty. Also points (pts) are indicated in each problem heading in the pdf. So do really scan over the exam a bit.
• The question statement is your friend. Reading it carefully is a tool to get you to your “rational place”.
• You may consult only three sheet of notes on both sides. Apart from that, you may not look at books, notes, etc. Calculators, phones, computers, and other electronic devices are NOT permitted.
• You may, without proof, use theorems and lemmas that were proven in the notes and/or in lecture, unless otherwise stated.
Major Gradescope Issues. If there is a global issue and it is not affecting you, please continue. If you are experiencing difficulties with gradescope, you may check your email, we will post a global message on piazza and bypass email preferences to inform you of what to do.
In particular, if the short answer gradescope becomes widely problematic we will ask you to scan one page per question with your answers so keep paper available, one page for each of 13 short answer questions in addition to the 6 pages for the long questions or 19 pages in total.
Please do not email in this global crash as we will not be able to deal with individual issues, just continue with your exam and write your answers on paper; one question per page for short answers, and one part per page for long answers.
CS 70, Fall 2020, Final 1
Some Latex Commands for Gradescope.
You can (if you choose) use latex. It is fairly easy and satisfying.
Surround an expression by “$$ … $$” on gradescope and you will be in latex. Examples: “$$ A+B*D $$” will give: A + B ∗ D.
There are useful commands:
1. “$$ Aˆ2 $$” yields A2
2. $$ \frac{a}{b} $$ yields ab .
3. “\max ” yields max.
4. “a\b”yieldsa≥b.
5. “$$ (qˆ {-1} \pmod{p} )$$” yields (q−1 (mod p)).
6. “{n \choose k-1}” yields n . k−1
7. Grouping with “{ }”: “$$6 {ˆG * H}$$” yields 6G∗H.
1. Pledge.
Berkeley Honor Code: As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others.
In particular, I acknowlege that:
• I alone am taking this exam. Other than with the instructor and GSI, I will not have any verbal, written, or electronic communication about the exam with anyone else while I am taking the exam or while others are taking the exam.
• I will not have any other browsers open while taking the exam.
• I will not refer to any books, notes, or online sources of information while taking the exam, other than what the instructor has allowed.
• I will not take screenshots, photos, or otherwise make copies of exam questions to share with others. Signed:
2. Long Ago. Pts: 2/2/2/2/3/3/3
1. A∨¬(B∧C) ≡ A∨(¬B∨¬C)
2. ¬∀x,∃y,Q(x,y)≡∃x,∃y,¬Q(x,y)
3. P =⇒ Q is logically equivalent to ¬Q ∨ P.
4. Consider a stable matching instance where S is the job optimal stable pairing. Consider a run of the job-propose matching algorithm, where one candidate c rejects a job j that they should not have in one step. That is, c recieves an offer from j and j′ and chooses j′ instead of j, when j was ahead of j′ in their preference list.
Let P be the resulting pairing.
(a) For every instance, job j cannot do better in P than in S. (Better means get a partner who they
prefer more.)
(b) Every candidate other than c does as well or better in P than in S.
(c) Every job other than j does as well or better in P than in S.
hTrue hTrue hTrue
hFalse hFalse hFalse
3. Graphs: Pts: 3/3/3/2
1. Consider a graph on n vertices with exactly one cycle and m edges. What is the number of connected components? (Hint: m ≤ n.)
2. For a tree on n vertices, what is the expected number of connected components if each edge is deleted with probability 1/3?
3. Ifwedeleteeveryedgewithprobability1/2fromanEuleriangraphonnvertices,whatistheexpected number of odd degree vertices in the remaining graph?
4. Every simple cycle is 2-colorable.
hTrue hFalse
4. Mostly Modular.Pts: 2/2/2/2/3/3/3/3/3/3/3
1. ∀ nonzero x,y ∈ N gcd(x,y mod x) = gcd(x,y).
2. ∀ nonzero x,y ∈ N, gcd(x,x mod y) = gcd(x,y).
3. Give an example of positive integers for a and n where (1·2···(n−1))an−1 ̸= (1·2···(n−1))
4. Let S = {x : x ∈ {1,…,34} and gcd(x,35) = 1}?
(a) What is the size of the set S?
(b) What is a|S|+1 (mod 35) for a ∈ S? (c) What is a|S|+1 (mod 35) for a ̸∈ S?
5. What is 18−1 (mod 13)?
hTrue hTrue
hFalse hFalse
6. Ifx=1 (mod13)andx=0 (mod18)thenwhatisx (mod234)?(Note:234=18×13)
7. For primes, p and q, where e = d−1 (mod (p−1)(q−1))?
(a) What is aed (mod q)? (Answer cannot use e or d, but may use numbers, a,p or q.)
(b) Find an x ≤ pq, where p|(aed − x). (Answer is an expression that may use a, p, and q.)
5. Polynomials.Pts: 3/3/3
1. Given a polynomial, x3 + a2x2 + a1x + a0 modulo 7 with roots at 3, 1, and 6. What is a0? (Notice that the coefficient of x3 is 1.)
2. Working (mod 5), find a polynomial modulo 5 of degree 2 that has roots at 0 and 3, and goes through point (2,3)
3. Consider that one encodes a message of n numbers (mod m), by forming a degree n − 1 polynomial using the numbers as coefficients, and sending 2n − 1 points. If each point is erased with probability 1/2, what is the probability that the original message can be reconstructed? (Hint: each pattern of erasures is equally probable.)
6. Countability/ : 2/2/2/2/2/2
1. For every pair of distinct rational numbers there is a rational number in between them.
hTrue hFalse
2. The rational numbers are uncountable.
hTrue hFalse
3. There is a program that takes a program P, an input x, and a number n and determines whether P run
on input x ever writes to memory location n.
hTrue hFalse
4. There is a program that takes a program P, an input x, and a number n and determines whether P run
on input x ever writes to any memory location i ≥ n.
hTrue hFalse
5. A program “knows” a real number if it takes an integer n and outputs the nth bit of the real number.
(Note: positive values of n signify to the left of the decimal point, and negative ones to the right.) (a) There is a program that knows π.
(b) For every real number x, there is a program that knows x.
7. A little counting.Pts: 3/3/3/3
hTrue hTrue
hFalse hFalse
1. What is the number of ways to have k strictly positive numbers that add up to n?
2. Whatisthenumberofwaystoproduceasequenceofnumbers0