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:

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 Sk C(n,k)3k=4k , 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 ith 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 C1, . . . ,Ck over a set of variables X = {x1, . . . , xn}, 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 x1, or just of x2), 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 xi, and the other consists of just the negated term xi, then
this is a pretty direct contradiction.

Assume that our instance has no such pair of “conflicting clauses”; that is, for no
variable xi do we have both a clause C = {xi} and a clause C' = {¬xi}. 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.