Algorithms and Data Fall 2010 Homework 5 Due date: October 13, 2010 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/f10/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. What to turn in: Your algorithm with a proof of correctness and the game history which shows how you tested the algorithm.