Algorithms and Data Spring 2011 Homework 5 Due date: February 17, 2011 At beginning of lecture Polynomial Time Algorithms with High Exponent Design a polynomial-time algorithm for the restricted LeafCovering problem described below. What this demonstrates: When a big structure is implicitly represented succinctly we may be able to work with the succinct representation to invent a polynomial-time algorithm. Terminology: Ti=(Vi,Ei) is a tree with nodes Vi and edges Ei. (view the i as subscripts) DAG = directed acyclic graph Definition: Graph Cartesian product Given n directed trees T1, ..., Tn, where Ti=(Vi,Ei), the graph Cartesian product is a DAG TT(T1, ..., Tn) that has as nodes the tuples (v1, ... ,vn) where vi in Vi and the following edges: Node (v1, ..., vi, ..., vn) has as children all nodes (v1, ..., vi', ..., vn), where vi' is a child of vi in Ti, and all other components are the same. The LeafCovering Problem ------------------------- INSTANCE: Given n directed trees T1, ..., Tn defining the graph Cartesian product TT(T1, ... .Tn), and a set of nodes, M, in TT(T1, ... .Tn). We assume that M only contains 2 elements. QUESTION: Does each leaf in TT(T1, ..., Tn) have some ancestor in M? The answer is either "yes" or "no". As a connection to your Theory of Computation course: LeafCovering is co-NP hard(when M may be arbitrary, not of size 2). Example of graph Cartesian product: Tree T1 Baum : Node | Leaf. Tree T2: Exp : Lit | Bin. Bin : Add | Sub. TT(T1,T2): /home/lieber/.www/courses/algorithms/cs4800/sp10/homeworks/hw3/graphCartesianproduct1.png http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp11/homeworks/hw5/graphCartesianproduct1.png This looks like a rather abstract problem but it has a very useful application: It is a type checking problem that multiple dispatch programming systems must answer. Can you avoid an explicit representation of the graph Cartesian product which would clearly lead to an exponential algorithm? How would you solve the problem if |M|=3? ====================== To test your algorithm involve your partner through the game. In this case you exchange algorithms and proofs. The claim is LeafCovering(2): I have a polynomial-time algorithm that solves the LeafCovering Problem for |M|=2. Refutation protocol: Alice claims LeafCovering(2). Bob tries to refute. Alice provides her algorithm as source code. Bob analyzes the algorithm and finds an input where the algorithm is wrong or Bob proves that Alice' algorithm is not polynomial. Take turns. ============ A better, alternative playground definition: The GRAPH ALGORITHM / LEAF COVERING PLAYGROUND We not only focus on the decision problem but also on constructing an uncovered leaf in case there is one. Instance = (set of trees. Set M which is a subset of the nodes of the Graph Cartesian Product (GCP) of the trees) Solution = (Boolean: all leaves are covered/not all leaves are covered). If not all leaves are covered an uncovered leaf must be provided as witness. valid = if witness is given, the witness must not be covered by (reachable from) a node in M. quality = 0 (all solutions have quality 0). Quality is irrelevant. Claims are of the form: k-LeafCovering(O(n^(k+1), n0, C). The instances that are legal for this claim are instances where M contains at most k elements. n is the number of trees. For simplicity, each tree is a binary tree with 2 leaves. The meaning of the claim is: for all instances where M contains at most k elements the solution can be found in time O(n^(k+1)), more precisely: the running time is <= C * n^(k+1) for n > n0. The use of the Landau notation in this context requires some thought. The C and the n0 must be provided as part of the claim. This information could be used for strengthening so that a claim with a smaller constant would be stronger. But for now, the strengthening relation is always false. =========================== What to turn in: Play the game with the alternative, better playground definition. Focus on claim: 2-LeafCovering(O(n^3)) and find an algorithm to defend it. Your algorithm with an argument of correctness and the game history which shows how you tested the algorithm.