[SOLVED] Cs240 algorithm design and analysis problem set 3

Problem 1:
Given a network G(V, E, s, t), give a polynomial time algorithm to determine
whether G has a unique minimum s − t cut.Problem 2:
We are given an n × m array of cells. Denote the cell in the r’th row and the
c’th column as (r, c), where 1 ≤ r ≤ n and 1 ≤ c ≤ m. A robot is at cell (1, 1)
and wants to reach cell (n, m). From cell (x, y), the robot can only move to
(x, y + 1) or (x + 1, y). In addition, some cells contain impassable obstacles and
the robot cannot move to these cells. Your goal is to put additional obstacles
in the minimum number of cells (other than cell (n, m)) such that the robot
cannot reach (n, m). Find an algorithm based on max flow.Problem 3:
Consider a restaurant with m different menu items. Each customer to the
restaurant want to order one item, and each of them has a set of items they are
willing to order from. The restaurant makes di amount of item i, for 1 ≤ i ≤ m,
so that at most di customers can order item i. Given n customers, where the
j’th customer has a list Cj of items they are willing to order, design an efficient
algorithm to maximize the number of customers you can serve.Problem 4:
Consider an n × n grid containing n rows and n columns of vertices. Each
vertex (i, j) has edges to four neighbors (i − 1, j), (i + 1, j), (i, j − 1), (i, j + 1),
except for the boundary vertices, which have edges to two or three neighbors.Each vertex and edge also has a positive integer capacity. We are given m
start vertices, and for each vertex we want to find a path which connects the
vertex to an arbitrary vertex on the grid’s boundary. Furthermore, we need to
ensure that the number of paths which pass through each vertex or edge does
not exceed its capacity. Give an algorithm to determine whether this is possible.
Hint: First transform the graph to convert the vertex capacities to edge capacities.Problem 5:
Given a set C, a collection D of subsets of C, and a value k, the k-SETPACKING problem asks if there exist k subsets from D which are mutually
disjoint, i.e. no two of the subsets share an element. Show that the SETPACKING problem is in NP.Problem 6:
Consider the following problem about scheduling courses. The problem is defined by 3 sets C, S and R. Here, C represents a set of courses, S repreesents
the available time slots for the courses, and R contains a collection of course
requests from students, where each request is a subset of C representing the the
courses that a particular student wishes to take. The goal is to schedule all the
courses without any conflicts.For example, if C = {a, b, c, d}, S = {1, 2, 3}, R = {{a, b, c}, {a, b, d}, {b, d}},
then it is possible to schedule the courses without conflicts by assigning course
a to time slot 1, b to slot 2 and c, d to slot 3. However, if C = {a, b, c, d}, S =
{1, 2, 3}, R = {{a, b, c}, {a, c}, {b, c, d}}, then it is not possible to schedule the
courses without any conflicts. Prove that the problem of determining whether
a conflict-free schedule exists is NP-complete.
Hint: Use a reduction from the 3-COLOR problem.