Sample problems for tutorial week #5

  1. Each of the following problems presents a scenario and a statement about that scenario. For each one, fill the circle by the best of these choices:
    • The statement is ALWAYS true, i.e., true in every instance matching the scenario.
    • The statement is SOMETIMES true, i.e., true in some instance matching the scenario but false in another instance matching the scenario.
    • The statement is NEVER true, i.e., true in none of the instances matching the scenario.

    Then, briefly justify your answer as follows:

    • Justify an ALWAYS answer by giving a small instance that fits the scenario for which the statement is true and then briefly sketching the key points in a proof that the statement is true for all instances that fit the scenario.
    • Justify a NEVER answer by giving a small instance that fits the scenario for which the statement is false and then briefly sketching the key points in a proof that the statement is false for all instances that fit the scenario.
    • Justify a SOMETIMES answer by giving two small instances that fit the scenario: one for which the statement is true and one for which the statement is false. (Indicate which is which!)

    Here are the problems:

    1. Scenario: Any SMP instance in which the men’s preferences are a copy of the women’s preferences (with each $m_i$ replaced by $w_i$).

      Statement: The Gale-Shapley algorithm run with men proposing terminates with precisely the same solution as the Gale-Shapley algorithm run with women proposing.

    2. Scenario: A directed graph G = (V, E) with |V| ≥ 2 .

      Statement: The out-degree of each vertex is larger than its in-degree.

  2. In this question we consider two problems:
    • The Emergency Distribution Problem (EDP) consists of a an undirected, unweighted graph G = (V, E) plus a set of distribution points D = { d1, d2, .., dk }, each a vertex in V and a single aid location a ∈ V that is not in D. The output is the number of non-overlapping (edge-wise distinct) paths leading from some di to a. (Multiple paths may lead from a single distribution point, and paths may lead from different distribution points.)
    • You have an efficient algorithm to solve the “network bandwidth problem” (NBP). NBP’s input is a weighted, directed graph G = (V, E) (where the tuple (u, v, w) ∈ E represents a directed edge from u to v with integer weight w and designated source and target vertices s and t). A node in the graph is a server and an edge is a network link between servers, weighted by its bandwidth—the maximum number of bytes per second the link can carry. (A weight of ∞ is also allowed, indicating unlimited bandwidth.)

      NBP’s output is the maximum bandwidth that can be carried from s to t.

      Notes: The bandwidth on any link cannot exceed that link’s weight. The bandwidth coming out of s is unlimited but none can go in, while unlimited bandwidth can go into t but none can come out. Otherwise, for any node v, the bandwidth coming into the node must equal the bandwidth coming out. Assume only integral (or infinite for links with weight ∞) amounts of bandwidth can be used on each edge.

    Consider the following incorrect reduction from EDP to NBP:

    • For each node v ∈ VEDP, generate a corresponding node v in VNBP.
    • For each undirected edge (u, v) ∈ EEDP, generate two edges (u, v, 1) and (v, u, 1) in ENBP.
    • Generate one additional vertex v’ in VNBP.
    • For each distribution point d ∈ D, generate an edge (v’, d, 1) ∈ ENBP.
    • Finally, let s = v’ and t = a.

    Now do the following:

    • Give a good counterexample to the correctness of this reduction. (A drawing of the counterexample instance is an excellent way to express it.)
    • Give the instance of NBP produced by the reduction from your counterexample. (Again, a drawing works well.)
    • Give and very briefly explain the incorrect solution to the original instance produced by the reduction (paired with an arbitrary solution to the underlying problem).
    • Give and very briefly explain the correct solution to the original instance.
  3. [IF TIME PERMITS] In the Exhibition Guarding Problem, we are given a line L that represents a long hallway in a show room. We are also given an unordered set X = { x0, x1, … xn-1 } of real numbers that represent the positions of precious objects or sculptures in this hallway. Suppose that a single guard can protect all the objects within distance at most d of his or her position, on both sides.
    • Design an algorithm for finding a placements of guards that uses the minium number of guards to guard all the objects with positions in X.
    • Analyze the running time of your algorithm as a function of n, the number of objects that need guarding.
    • Sketch a proof that your algorithm works.

Spam prevention powered by Akismet