Prelim 2 Review Questions

Prelim 2 will be Tuesday, April 12th in the evening 7:30-9 pm in Upson B17.

This is a closed notes, closed book test!

Those with conflict with an other prelim should let us know ASAP, by sending email to eva@cs.cornell.edu. Those with conflict will be allowed to take the exam early. Exact arrangements (time and room) will be emailed to you shortly.

I will hold a review session on Monday's class, April 11th. We will also rearrange office hour for the week to help prepare for the prelim. Please check the Web for the schedule.

The topics for the prelim cover the material of problem sets 6-8. You need to know:

combinatorics and counting
The pigeon hole principle
Permutations and Combinations
Identities using Binomial coefficients
Counting subsets with replacement
Inclusion-Explusion principle
Market basket data
Probability, sample spaces,
Conditional probability, independence, Bayes rule
expectations,
union bound
applications of probability to contention resolution, coupon collection. max-SAT

These topics are covered in Rosen 5th edition sections 4.1-4.5 , 6.5 and 5.1-5.2 + expectation from 5.3 (or from the 4th edition sections 4.1-4.6 and 5.5), plus handout on Kleinberg-Tardos: Algorithms Design, sections 13.1, 13.3, 13.4 and 13.12. Nothing will be tested that we did not have in class or homeworks. So your notes from class and the homework is a better guide than the book.

Here are a few questions from the book that would be useful for review. These are not meant to be handed in, and solutions will not be handed out (though some solutions are available at the back of the book). Feel free to ask about them during any office hours or the review session.

Questions

Question in 4th edition	Question in 5th edition	Statement of the question
Chapter 4 in edition V
Review 23	Review 13
Supplementary 13		Show that there are at least 2 different 5 element subsets of a set of 10 positive integers not exceeding 50 that sum to the same sum.
29	Supplementary 27
	29,	show that if n is an integer then S_k C(n,k)3^k=4^k , where the sum ranges for k=0,...,n
45	33,
46	34,
47	35
Chapter 5 in edition V
Review 18	Review 6
	9	(a) What does linearity of expectation of a random variable mean? (b) How can the linearity of expectation help us to find the expected number of people who receive the correct hat when a hatcheck person returns hats at random.
	Supplementary 11	Suppose n people play odd person out: The n people flip a coin, and if all but one come out the same, the one that is different looses. Otherwise they repeat again, till someone looses. (a) What is the probability that the odd person out is decided in one round? (b) What is the probability that the odd person out is decided in k round? (c) What is the expected number of rounds needed to decide the odd person out with n people?
	17	What is the probability that a randomly selected bit string of length n is a palindrome (same backwards as forwards)
	20	Suppose n balls are tossed in b bins so that each ball is equally likely to fall into each bin independently. (a) Find the probability that a particular ball falls in a particular bin. (b) What is the expected number of balls that land in one particular bin? (c) What is the expected ball tossed until a particular bin contains a ball? (d) What is the expected number of balls tossed till all bins contain a ball? (Hint: Let Xi denote the number of tosses required till a ball lands in the i^th bin, once i-1 bins already contain a ball.
	26	A space probe near Neptune communicates with Earth using bit strings. Suppose that in its transition it sends 1 one-third of the time, and 0 two-third of the time. When 0 is sent, the probability that it is received correctly is 0.9, and with probability 0.1 it is received incorrectly as a 1. When a 1 is sent, the probability of it being received correctly is 0.8, and it is received incorrectly as a 0 with probability 0.2. (a) Find the probability hat 0 is received. (b) Use Bayes formula to find the probability that 0 was sent, given that 0 was received.
		In class, we designed an approximation algorithm to within a factor of 7/8 for the MAX 3-SAT problem, where we assumed that each clause has terms associated with 3 different variables. In this problem we will consider the analogous MAX SAT problem: given a set of clauses C₁, . . . ,C_kover a set of variables X = {x₁, . . . , x_n}, find a truth assignment satisfying as many of the clauses as possible. Each clause has at least one term in it, but otherwise we do not make any assumptions on the length of the clauses: there may be clauses that have a lot of variables, and others may have just a single variable. (a) First consider the randomized approximation algorithm we used for MAX 3-SAT, setting each variable independently to true or false with probability 1/2 each. Show that the expected number of clauses satisfied by this random assignment is at least k/2, i.e., half of the clauses is satisfied in expectation. Give an example to show that there are MAX SAT instances such that no assignment satisfies more than half of the clauses. (b) If we have a clause that consists just of a single term (e.g. a clause consisting just of x₁, or just of x₂), then there is only a single way to satisfy it: we need to set the corresponding variable in the appropriate way. If we have two clauses such that one consists of just the term x_i, and the other consists of just the negated term x_i, then this is a pretty direct contradiction. Assume that our instance has no such pair of �conflicting clauses�; that is, for no variable x_i do we have both a clause C = {x_i} and a clause C' = {�x_i}. Modify the above randomized procedure to improve the approximation factor from 1/2 to at least a .6 approximation, that is, change the algorithm so that the expected number of clauses satisfied by the process is at least .6k.