This is version 3.1.

All work is to be done individually.

You can turn your answers in by sliding them under my office door (4101 APM) if I'm not in.

Algorithms may be described at a ``high level'' without actual code. You should also justify informally that they are correct. You may use any lower bound, algorithm, theorem, or data structure from the text or in class, but be careful. For example, if you construct a graph with n² nodes and n³ edges and then run Dijkstra's algorithm on the resulting graph, the total run-time is O(n³ lg n), because Dijkstra's algorithm is O(E lg V). Also, to use Dijkstra's algorithm on the graph, you must establish that edge weights are non-negative, since otherwise the proof that Dijkstra's algorithm gives shortest paths does not go through.

If you use a standard algorithm or data structure (e.g. Dijkstra's algorithm or Red-Black trees), there's no need to explain how they work.

If a problem has multiple size parameters, you should express the runtime as a function of all relevant parameters; e.g., saying maximum bipartite matching takes time O(|V||E|) is more accurate than saying it takes time O(V³), although both are correct.

For some problems, correctness may be trivial; for others the analysis may be trivial. If it is trivial, you do not need to go into detail, but you should at least give a one or two line explanation. (Conversely, if you only give a one or two line explanation, I will view this as implicitly claiming that it is trivial.)

For all problems that ask you to find an algorithm, your goal is to find the algorithm with the smallest asymptotic worst-case complexity that you can.

The only references you should use are the textbook and class notes. If you happen to stumble across a solution (or partial solution) in some book/paper/discussion/whatever, please cite the reference. (For question 5, you can of course use the web page mentioned there also.)

Answer any four of the following.

1. Maximum likelihood failure. A network is described as a directed graph, with a specified source s and destination t. A set of nodes F (not including s or t) is a failure set if deleting those nodes (and the edges they are part of) disconnects t from s. For each node of the graph, i, there is a failure probability p_i with 0 < p_i < 1. It is assumed that nodes fail independently, so the failure probability for a failure set F is the product of the failure probabilites of the nodes in F.

   Give an algorithm which finds the failure set F with the maximum failure probability.

2. K largest elements. The phone company wants to keep track of which numbers are called most often. It wants an efficient data structure that keeps track, for each phone number p, of the number of times the number has been called, c(p). Thus, it needs to perform the following operations efficiently:
   • NewPhone(p): initialize new phone number p with c(p) = 0.
   • Call(p): increment c(p) by 1.
   • Top(k): output the k phone numbers with the largest value of c(p), breaking ties arbitrarily.
   Let n be the total number of NewPhone, Call, and Top operations.

   (a) Give a data structure that supports NewPhone and Call in O(lg n) time or better for each operation, and Top in time O(lg n + k) or better.

   (b) Give a data structure that supports NewPhone and Call in O(lg n) time or better for each operation, and the Top in time O(k lg k) or better. (This might be better than your solution to part (a) when k is really small compared to n. [Note: Your answer to both parts canconceivably be the same.)

3. Course Assignment. Online University charges each student $1000 per course. Each student submits a list of all the courses he/she might want to take next term, and says how much money he/she can spend. The University then assigns students to courses. To keep the professors from being overloaded, it assigns at most 100 students per course. (Because all the courses are online, there are no conflicts about courses meeting at the same time.) The Course Assignment problem is to assign students to courses in a way that maximizes the amount of money that the University will take in.

   (a)Describe how you can encode an instance of the Course Assignment problem as a Max Flow problem. (This doesn't need to be a "reduction" in the strict sense used in the definition of NP-complete problems. In other words, it's OK if, after a Max Flow algorithm is run on the encoded problem instance, there is a little post-processing to give the answer to the Course Assignment instance.) (b)The University, in a attempt to cut down on cheating, decides it will never assign students who have the same address to the same course. Describe how this additional constraint can be accommodated in the Max Flow formulation.

4. Teacher Assignment. Online University now needs to find teachers for its courses. There are n courses; the i-th course has an enrollment of E(i). There is also a list of m teachers (with m>n), each of whom is willing to teach one course. These are very versitile teachers - any teacher can teach any course.

   The teacher list has two numbers for each teacher: L(k) is the maximum number of students that teacher k is willing to have in the course, and S(k) is salary that teacher k charges. [The amount the teacher is paid doesn't depend on the number of students.]

   A legal assignment is a function t that maps courses to teachers, subject to the constraints:

   • t is one-to-one (that is, no teacher gets more than one course).
   • for all i = 1, ... , n, E(i) <= L(t(i)) (that is, number of students in each course is at most the number that the teacher is willing to teach.

   Find an efficient algorithm that minimizes the total amount of salaries that the University pays. Explain why it is correct and give its complexity.

5. Establishing NP-Completeness The two problems listed below are slightly disguised versions of (different) NP-Complete problems. Your job is to establish that they are indeed NP-complete by finding them in this list of NP-Complete problems . For each of Problem X and Y, you should tell which problem in the publish list can be reduced it, and how to translate the notation given in the published list to the terminology in Problem X or Y. Remember - since you are trying to show that X and Y are NP-complete, you must show how to reduce every instance of a known NP-complete problem to some instance of the problem below. To try to make this clearer, I've given a sample question and answer.

   (sample) Problem Z: Given an array S[1], S[2], ... S[n] of integers, and two integers P and Q, is there a subset of the elements of S has at most P elements and they add up to exactly Q?

   (answer to sample) Problem 42, Subset Sum, can be reduced to this problem as follows: given any instance [A, size, K] of Subset Sum, number the elements of A arbitrarily as a₁, a₂, ..., a_n. Construct the instance of Problem Z with S[i] = size(a_i), P = n, and Q = K.

   Aside (not part of the answer): Notice I'm not asking you to prove anything. But be very careful to get the notation right! Incidentally, even though Problem Z allows you to limit the size of the subset to P elements, but the Subset Sum problem doesn't, and even though in Subset Sum, the sizes must be positive (but not in Problem Z), the reduction is still valid, even though it isn't a one-to-one correspondence between problem instances.

   Problem X: (also known as the Airlines Luggage Routing Problem) Given a positive integer L, a list of n airports, and a zero-one matrix M where M[i,j] = 1 if there is a flight from airport i to airport j, and M[i,j] = 0 otherwise. (Note that M[i,j] and M[j,i] aren't necessarily equal.) Is there a route that starts from airport 1, ends up at airport n, and goes through at least L airports without going through any airport more than once?

   Probem Y: (Party Planning) You have n friends, some of whom get along with each other and some who don't. Let K[i,j] = 1 if i and j get along with each other, K[i,j] = 0 otherwise. (In this problem, K[i,j] = K[j,i].) You've decided to hold L parties. Can you find a set of people to invite to each party so that no party ever has two people who don't get along with each other, but for every pair i,j who do get along, there will be at least one party that both are invited to? [Note: you are allowed to invite people to more than one party.]