Exam 1- Ch. 1, 2, 6 & 7

Consider the situation where we want to transmit a sequence of symbols from the alphabet {A,B,C,D}, with frequencies given byA: 0.16, B: 0.34, C: 0.33, D: 0.17In an optimal encoding (as produced by Huffman’s algorithm), how many bits will be used to represent

For the various knapsack problems, we have considered the greedy strategy G of first picking as much as allowed of the most precious item (the one with highest value/weight ratio), next picking as much as allowed of the second most precious item, etc, etc.  Match each version with the outcome guaranteed:

We shall consider the general method, employed by an adversary,  to prove that no algorithm can always decide a given problem X using less than M questions. For that purpose, the adversary maintains Q, and R_1 … R_M, such that : 1. X(Q) is true2. X(R_i) is false for all i \in 1 … M and such that after k questions from the algorithm:3. Q is consistent with all k answers from the adversary 4. for all i in 1 … M, except for at most k such, it holds that R_i is consistent with all k answers from the adversary.For each declaration from the algorithm, how should the adversary respond?

Assume that X can be polynomially reduced  to Z, in that there exists a function f such that     forall  x,   x in X   iff   f(x) in Zand f can be computed in time polynomial in the size of x. Which inferences are then valid?

Consider how we could decide the 3COL problem:  generate one color map, and check if it is a valid coloring;  if not, then reuse the space to generate a second color map,  and check if it is a valid coloring; if not,  then reuse the space to generate a third color map, etc, etc,  until either some color map has been found valid,  or all color maps have been found invalid. Observe that a color map can be generated and checked in polynomial time. What can we then say about each of the below claims (where PSPACE are the problems that can be decided in polynomial space)?   

Finally, some questions about a probabilistic problem. Given a sequence of coin flips, we define a doubleton as two consecutive Hs with no H immediately before or after, or two consecutive Ts with no T immediately before or after. For example, the sequence TTHTTTHHHHTTHTHHThas 3 doubletons (boldfaced). Assume that we toss a fair coin n times (n  >= 3). With X a random variable denoting the number of doubletons in the resulting sequence, we want to calculate E.  For that purpose, for each i in 1..n we define an indicator random variable X_i for the event that toss i starts a doubleton; thus E = 0 andX = \sum_{i=1}^n X_i.(Observe that when n = 3 we have E =  4/8 = 1/2 since each of the sequences HHT and TTH and HTT and THH has 1 doubleton, while each of the sequences HHH and TTT and HTH and THT has 0 doubletons.)

Exam 4- Chapters 14, 15, &16

Exam 1- Chapters 6, 17 & 18

Henry’s duties include mixing a variety of chemicals for the products and treatment ointments and mixtures they use on clients. When mixing these chemicals, Henry should avoid all EXCEPT which of the following?