Computer Science 70: Discrete Mathematics

Midterm II Review

For midterm II, you should be familiar with the following concepts, and you should be able to do the following problems. We will discuss the solutions to some of these problems in the discussion sections of March 29 and the review session that evening.

We will update this sheet regularly, so you should check that you have the most recent copy. Last updated: 1pm, March 28

• Algebra (lectures 9 and 10, homeworks 4, 5, and 6): (1) Finite fields

(2) (Univariate) Polynomials

(3) Secret sharing schemes

(4) Error correcting codes (including the Berlekamp-Welch algo-

rithm)

• Graph theory (lectures 11 and 13, homeworks 6 and 7)

(1) Definition of Eulerian paths and circuits, necessary and sufficient conditions for existence (with proofs)

Question 1. Let G = (V, E) be a graph with n vertices and e edges. Suppose that G has exactly two vertices, v_{1} and v_{2}, of odd degree, and suppose that the length of the shortest path between v_{1} and v_{2} is s. What is the length of the shortest (i.e., with the fewest number of edges crossed) cycle in G that passes over each edge at least one? Express your answer as a function of n, e, and s.

(2) Definition of Hamiltonian paths and circuits

(3) Standard and recursive definition of the hypercube, expansion property of the hypercube

Question 2. Recall that the standard n-hypercube consists of 2^{n} vertices, labelled by n-bit binary strings, with edges between vertices whose labels differ in exacty one bit position. We can define a ternary n-hypercube, which consists of 3^{n} vertices, each labelled by an n-bit ternary string (cf. question 4 below), and has edges between vertices whose labels differ in exactly one position by one: in the ternary 2-hypercube, for instance, the vertices are (00), (01), (02), (10), (11), (12), (20), (21), (22) and there are edges between (00) and (01) and between (11) and (12), e.g., but not between (10) and (12).

(a) List all the edges in the ternary 2-hypercube.

(b) Find a recursive definition of the ternary n-hypercube (i.e., show how to construct the ternary n-hypercube from ternary n − 1-hypercubes).

• Basic Combinatorics (lecture 14, homeworks 7 and 8)

(1) Counting rules: permutations, combinations, counting with and without replacement (i.e., distinguishable vs. indistinguishable balls in bins)

Question 3. Recall that an anagram of a word is a string made up from the letters of that word, in any order. (For instance, there are exactly three anagrams of EYE: namely EEY, EYE, and YEE. Note that anagrams need not form legal words.) How many different anagrams of “DISCRETEMATHEMATICS” are there?

Question 4. A ternary string is a sequence of digits, where each digit is either 0, 1, or 2. For the following, give a general answer in terms of n, and simplify your expression as much as possible:

(a) Count the number of ternary strings of length n whose longest all-zeros prefix is of odd length. (For instance, for n = 5, 00000 and 01202 qualify but 21001, 00201, and 00002 do not.)

(b) Count the number of ternary strings of length n whose digits are in non-increasing order. (For instance, for n = 5, 00000, 21100, and 22210 qualify, but 21101 does not.)

Question 5. Count the number of 2004-bit binary strings that don’t contain 01 as a substring. Simplify your expression as much as possible.

(2) Combinatorial proofs

• Probability Theory (lectures 15, 16, 17, and 18, homeworks 7, 8, and 9)

(1) Probability spaces

Quesion 6. Suppose a certain theory TA has a crack habit and tries to smuggle in to the US 5 ounces of crack, each disguised as a vitamin pill. To get past customs, the TA puts the 5 pills into a container of 400 vitamin tablets. Assuming that the customs officer randomly checks 10 tablets, what is the probability that the TA gets caught?

Question 7. Suppose this year’s ALCS is very evenly matched, with the better team having a probability of 0.55 of winning each game. Given that the ALCS is a 7-game series, what is the probability that the better team wins the series? (Hint: think about tosses of a biased coin.)

(2) Union Bound

(3) Conditional Probability and Bayes’ Rule

Question 8. We say that two events A and B in a sample space Ω are positive correlated if Pr[A|B] > Pr[A]. Prove or disprove: if Pr[A|B] > Pr[A] holds, then Pr[B|A] > Pr[B] also holds. (You may assume that Pr[A|B] and Pr[B|A] are well defined, i.e., neither Pr[A] nor Pr[B] is zero.)

Question 9.

(a) Consider a collection of families, each of which has exactly two children. Each of the four possible combinations of boys and girls, bg, gb, bb, gg, occurs with the same frequency. A family is chosen uniformly at random, and we are told that it contains at least one boy. What is the (conditional) probability that the other child is a boy? Justify your answer with a precise calculation.

(b) On the same probability space as in part (a), let A be the event that the chosen family has children of both sexes, and B the event that the family has at least one girl. Are the events A and B independent? Justify your answer carefully.

(c) Consider now the probability space of families with three children, with each of the eight possible combinations of boys and girls equally likely. Define the events A and B as in part (b). Are these events independent? Again, justify your answer carefully.

(4) Random Variables

(5) Expectation, linearity of expectation

Question 10. We say that a string of bits has k quadruplyrepeated ones if there are k positions where four consecutive 1’s appear in a row. For example, the string 0100111110 has two quadruply-repeated ones. What is the expected number of quadruply-repeated ones in a random n-bit string, when n ≥ 3 and all n-bit strings are equally likely? Justify your answer.