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 acknowledge 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. Warmup, Propositions, Proofs

1.  Vx,y e R, 3z e R ((x > y) =÷ x > z > y)

Answer: True. For every two reals, there is real that is between them.

2.  3z e R, Vx,y e R ((x > y) =÷ x > z > y).

Answer: False.  There is no real that is between every pair of reals.  It is true that for every pair of reals there is another real.

3.  For a function f (x), Consider X = f _ 1 (A u B) and Y = f _ 1 (A)u f _ 1 (B). (Recall that f (X ) = {y|y =

f (x) for some x e X } and f _ 1 (Y ) = {x|f (x) e Y }. )

Is X C Y , Y C X, or both?

Answer: X = Y . If x e f _ 1 (A uB), then f (x) e A uB 4 f (x) e A or f (x) e B 4 x e f _ 1 (A)u f _ 1 (B).

4.  If one has n ＋1 pigeons distributed into n holes, there always exist a hole with at least X pigeons. What is the largest value of X where the statement is true?

Answer: 2. At least two pigeons must be in the same hole.

5.  If 2n ＋1 pigeons are placed in an n holes numbered 0 to n _ 1, there always exists a pair of holes numbered i and i ＋1  (mod n) with a total of at least X pigeons in the two holes. What is the largest value of X where the statement is true?

Answer: 5. If one sums the occupancy for holes i and i ＋1  (mod n) for all the i pairs, each pigeon is counted twice, so the total of the counts is 4n＋2. Dividing by the n possibilities for i pairs, we get 4＋2/n, and thus we can conclude that the count is at least 5 for one i.

6.  The equation x5 = 16 has a rational solution

Answer: False. Assume not, consider a/b with no common factors, a5  = 16b5  which implies 16|a5 and a = 2k for some integer k, which yields 16b5 = (32k5 ), and then b is even. This is a contradiction of the reduced form of the fraction a/b.

3. Stable Matchings. 2 points/part.

In the following “favorite” partner means first on preference list, “optimal” partner means the most preferred partner in any stable pairing.

1.  There is a stable pairing where no job is paired with the first candidate on their list.

Answer: True.  The candidate optimal pairing in a 2 by 2 instance which is different from the job optimal pairing works. The 2 by 2 instance where jobs A,B have 1, 2 first respectively and candidates

1, 2 have jobs B,A respectively, is an example.

The pairings (A, 1), (B, 2) and (B, 1), (A, 2) are both stable.

2.  If there is a stable pairing where a job j is paired with its pessimal candidate, then all jobs are paired with their pessimal candidate in that stable pairing.

Answer: False.  Consider two instances with different optimal/pessimal pairings.  Combine the in- stances so that entities in the other instances are later in the preference lists and one can use the optimal pairing in the first (sub)instance and the pessimal pairing in the (other).

3.  No job can improve their final outcome in the jobs propose matching algorithm by submitting a false preference list.

Answer: True.  Say job j gives a fake preference list, and c is the result of the algorithm with the correct order, and c\ is the result of the algorithm in the incorrect order. If c\ is preferred to c then job j would have proposed to c\ in the original algorithm and was rejected due to some j\ . That j\ would ask c\ in this situation as well since their preference list remained the same, and if they were rejected from by a previous candidate, cp, due to j who no longer asks, and since j was ultimately rejected by that previous candidate due to some j\\ then j too would be rejected by that candidate due to j\\ . So j\ would ask c\ which would cause j to be rejected in this run as well.

4.  No collection of jobs can conspire to improve the outcome of any job j in the jobs propose matching algorithm by jointly submitting false preference lists.

Answer: False.

Consider the following true preference lists, with Jobs 1,2,3 and Candidates A,B, and C.

Job 1 ends up with Candidate B, Job 2 with A, and Job 3 with C. Now see what happens when all the Jobs conspire.

Job 3 going straight for Candidate C means they gets the same outcome but now Job 1 and Job 2 get their top picks. The key is realizing jobs can’t lie to improve their own outcome but can for others.

5.  If in a run of a jobs propose algorithm, job j is rejected by candidate c because of job j\ then job j\ can never be rejected by a candidate c\ because of job j.

Answer: False. Consider a three job example, where A and B proposes to 1, and C proposes to 2. B gets rejected by 1 and proposes to 2 who then rejects C.  Then C proposes to 1, who rejects A who proposes to 2 who then rejects B.

4. Graphs

1.  What is the least number of edges whose removal splits a 4 dimensional hypercube into two compo- nents of equal number of vertices?

Answer: 8. It has 16 vertices, and there are 8 that connect two subcubes with 8 vertices each.

2.  What is the least number of edges whose removal splits K6  into two components of equal number of vertices?

Answer: 9. Consider splitting the graph into two groups of size 3, the edges between the groups form K3,3 with these vertices. That has 9 edges, three incident to each of 3 vertices on one side.

3.  There is an even number of odd degree vertices in any graph.

Answer: True. The sum of degrees is 2|E| and thus there must be an even number of vertices with odd degree.

4.  A graph for which the average degree of vertices is an odd integer must have an odd number of vertices.

Answer: False.  If the average degree is some odd integer 2k ＋1, then the total degree must be (2k ＋1)v = 2kv ＋v (where v is the number of vertices). We know that the sum of degrees of a graph must be even, so v must be even.

5.  What is the length (in edges) of an Eulerian tour of G = (V, E)?

Answer: |E|. It visits every edge once.

6.  For a planar graph where every face is bounded by at least 4 edges, derive an upper bound on the number of edges e in terms of v, the number of vertices.

Answer: 2v _ 4. Euler’s formula states v ＋f = e ＋2, and each face touches > 4 edges and each edge touches 2 faces, so 2e > 4f and v ＋e/2 < e ＋2 which implies e < 2v _ 4.

7.  For a planar graph with v vertices where every face is bounded by at least 4 edges, there must be a vertex of degree less than or equal to X . What is the minimum value of X where the statement is true? (You may use U, the answer for part 6, or just state the correct number.)

Answer: 3 or「2U/v|. Since sum of degrees is 2e, and the formula from the previous part can be used to say the sum of degrees is 4v _ 8 and the average degree is at most 4 _ 8/v, and therefore there must be a vertex of degree at most 3.

8.  For a connected graph with exactly 3 disjoint cycles, what is the minimum number of components in the graph if one removes 5 edges?

Answer: 3. One can remove an edge in each cycle, and then removing each additional edge increases the number of components by 1.

9.  If a graph does not have an Eulerian tour it does not have a Hamiltonian tour.

Answer: False. The 3 dimensional hypercube has a Hamiltonian tour and it is not Eulerian.

5. Modular Arithmetic

1.  For x,y e N, with x < y, what is the smallest M, where y (mod x) < M. (Your expression should be in terms of y only.)

It should be as tight as possible though within 1 of the correct answer is fine.

Answer: y/2. If x > y/2, than y (mod x) = y _ x < y/2, and otherwise y (mod x) < x < y/2. Tech- nically「y/2| works.

2.  If gcd(a, m) = x and gcd(b, m) = y, and gcd(x,y) = z, what is gcd(ab, m)?

Answer: xy/z. You use the fact that each is the product of primes and m contains the primes in x and y and where the common primes in z are double counted.

3.  If m and n have gcd(m, n) = 1, and n = m ＋5, there is a unique x (mod mn) where x = 5  (mod m) and y = 0  (mod n).

Answer: True. This is CRT. The equation y = 0  (mod n) should have been x = 0  (mod n). We gave everyone full credit due to this.

4.  If m and n have gcd(m, n) = 1, and n = m＋5, find one x (mod mn) where x = 5  (mod m) and y = 0

(mod n). (Expression can possibly use m and n and should be as simple as possible for full credit.)

Answer: n or m＋5. This x satisfies the two equations. One could try CRT explicitly, but we expected this to be by inspection from our practice with modular arithmetic concepts.   The equation y = 0 (mod n) should have been x = 0  (mod n). We gave everyone full credit due to this for any x where x = 5  (mod m) regardless of whether x = 0  (mod n).

5.  How many values of a e {0, . . . , 9} is f (x) = ax (mod 10) a bijection?

Answer: 4.They have to have gcd(a, 10) = 1

6.  Calculate the last digit of 72021 .

Answer: 7. It is 74*505＋1 = (74)505 * 7 = 7

7.  If x = y32 , and z = y1 , give an expression for y65 in terms of positive powers of x and z with minimum power of z.

Answer: x2z.

For the following two questions. Consider m, n e N where m, n > 2. Consider the graph G on mn vertices labeled V = {0, . . . , mn _ 1}, with edges {(i, i ＋m (mod mn)) and (i, i ＋n (mod mn)) : i e V }.

8.  Credit only awarded if both answers are correct.

(a)  If gcd(m, n) = 1, what is the maximum degree of a vertex in G?

Answer: 4. Each node appears in a cycle of vertices of length m uses edges of the form (i, i＋n). Similarly it appears in a cycle of vertices of length n.

(b)  If gcd(m, n) = 1, what is the number of connected components of G?

Answer: 1. Using the equation an ＋bm = 1, one can use a edges of the form (i, i ＋n (mod n)) and b edges to get to the next higher numbered vertex. This implies that the graph is connected. It is degree 2 in each cycle and the cycles cover all incident edges.

9.  Credit only awarded if both answers are correct.

(a)  If gcd(m, n) = d, what is the maximum degree of a vertex in G?

Answer: 4. Each node appears in a cycle of vertices of length m uses edges of the form (i, i＋n). Similarly it appears in a cycle of vertices of length n. It is degree 2 in each cycle and the cycles cover all incident edges.

(b)  If gcd(m, n) = d, what is the number of connected components of G?

Answer: d. A node v = i (mod d), can only reach other nodes with the same modulus i. There are d such categories. For the nodes where v = i mod d, one can use the equation an＋bm = d to use a combination a type edges of type (i, i ＋n (mod mn)) and b edges of type (i, i ＋m (mod mn)) to change the value of v by an additive d. Thus there is a path between any pair of vertices that has the same modulus   (mod d).

6. RSA

1.  For the RSA scheme where p = 3 and q = 11, choose an appropriate e and d to complete the construc- tion.

Answer: e = 3, d = 7. 7 = 3_ 1   (mod 20).

2.  For the RSA scheme with p and q, we have that for an integer x.

Which of the following statements are always true? If none, state none.

(a) p|(xe _ x)

(b) p|(xed _ x)

(c) p|xed

(d) p|xe

Answer: (b). If x = 0, this is true. Otherwise xed = xk(p_ 1)(q_ 1)＋1 = (xp_ 1 )k(q_l)x = x (mod p). The last inequality uses Fermat’s theorem.

3.  Given x,y, and an RSA encryption scheme with public key where N = pq, what is the encryption of E(xy) in terms of E(x) and E(y)?

Answer: E(x)E(y) (mod N).

4.  To check a signature y of a message m (that is, y = md (mod N)), for an RSA public key (N, e), how do you recover m? (Answer is expression involving y,N, e.)

Answer: Compute ye (mod N).

7. Modular Arithmetic: Something new.

Define the order of a modulo p to be the smallest positive integer n such that an = 1  (mod p). Assume p is prime for this problem.

1.  Compute the order of 2 modulo 7.

Answer: 3. Note that 21 = 2  (mod 7), 22 = 4  (mod 7), and 23 = 1  (mod 7), so the order of 2 modulo

7 is 3.

2.  Let d be the order of a modulo p, and suppose that an = 1  (mod p). Compute the value of n (mod d). (State a value between 0 and d _ 1.)

Answer: 0. Suppose for the sake of contradiction that d { n. Then we can write n = qd ＋r for integers

q and r, where r is the remainder, so 0 < r < d. Note then that we can express

1 = an = aqd＋r = ar(ad )q = ar . 1q = ar (mod p),

so we have found a positive integer r less than d such that ar = 1  (mod p), contradicting the minimality of d. Thus, our initial assumption was incorrect, and d | n.

3.  If d is the order of a modulo p, then (a) d|p

(b) d|(p _ 1)

Answer: (b). d|n for any n where an = 1  (mod p) and ap_ 1 = 1  (mod p) by FLT.

4.  At most how many integers in the range {0, 1, 2, . . . , p _ 1} have order 3 modulo p? (Hint: Consider the polynomial X3 _ 1. Note that X = 1 is a solution but 1 has order 1 modulo p.)

Answer: 2. The roots of the polynomial X3 _ 1 are the values a such that a3 = 1  (mod p). From part b, the order of a modulo p divides 3. Thus, the order of a modulo p is 1 or 3. Thus, the roots of the polynomial X3 _ 1 are the values a such that have order 1 or 3. Thus, we need to remove the values

that have order 1.

The values that have order 1 are those such that a1  = 1  (mod p); in other words, a = 1, and there is

one integer in the range that has order 1. Thus, all the other roots of the polynomial X3 _ 1 have order 3.

Since X3 _ 1 is of degree 3, it has at most 3 roots modulo p. One of these roots has order 1, so thus, there are at most 2 values modulo p that have order 3 modulo p.

8. Polynomials.

All the polynomials are over a field GF(p) for a prime p > d where d is the degree of the polynomial unless otherwise specified.

1.  Given three points P(1) = 1, P(2) = 0, P(3) = 0, what is the polynomial P(x) modulo 5. (Hint: this is a △1 (x) in Lagrange interpolation.)

Answer: 32x＋3. (x _ 2)(x _ 3)(1 _ 2)_ 1 (1 _ 3)_ 1 = (x2＋1)(_ 1)(2) = 32x＋3

2.  If P(x) is a polynomial modulo 5 of degree (at most) 1, and P(0) = 1 and P(1) = 2, what is P(x)?

Answer: x ＋1. inspection.

3.  Factor x3 ＋4  (mod 5) as completely as possible.  (Hint:  what’s the relationship between roots and factors?)

Answer: (x _ 1)(x2 ＋x＋1). The idea here is to notice that the only root is 1. Thus one only needs to divide by x _ 1. To be sure, the previous problem is supposed to be helpful.

4.  Every polynomial of degree exactly 1 has exactly 1 root.

Answer: True. A degree 1 polynomial has form a1x＋a0 and a root is at x = _a0 (a1 )_ 1 and since we are working over a field a1 has an inverse.

5.  If a polynomial of degree exactly d has at least d _ 1 roots, it has exactly d roots.

Answer: True.  There are d _ 1 factors of the form (x _ r1 ) ... (x _ rd _ 1 ).  What’s left is a degree 1 polynomial which always has a root.

6.  How many packets do you need to send to recover your original message if the length of your message is 5;

When the channel has a max of 3 erasure errors?

Answer: 5＋3 = 8

(b)  When the channel has a max of 3 general errors?

Answer: 5＋2 * 3 = 11

(c)  When the channel has a max of 2 erasure errors and 2 general errors?

Answer: 5＋2＋2 * 2 = 11

7.  Given n points, what is the maximum value of d such that there is at most one degree d polynomial that passes through at least n _ k of the given points?

Answer: d = n _ 2k _ 1. This is the idea that if a polynomial of degree m _ 1 is consistent with m＋k points out of m＋2k points it must be unique.

8.  Consider a degree 1 polynomial P(x) = p1x ＋p0 , and receiving four points R(0),R(1),R(2),R(3) on P(x) with possibly one error. (Recall that Q(x) = P(x)E(x) for an error polynomial E(x) in the Welch- Berlekamp scheme.)

(a)  If the error polynomial E(x) is x _ e and Q(x) = q2x2＋q1x＋q0 , what is q1 in terms of p0 , p1 and e?

Answer: _ep1 ＋p0 . Just multiply out (x _ e)(p1x ＋p0 ).

(b)  Working modulo 5, given that E(x) = x _ 1 and Q(x) = 2x2 _ x _ 1, what is P(x)?

Answer: 2x ＋1. Long division. Checking (x _ 1)(2x＋1) = 2x2 _ x _ 1.

9. Counting

1.  How many anagrams of the word “SUSPICIOUS” are there?