All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

  1. Suppose you are given a string of n characters. Design an O(n2) algorithm to find the shortest subsequence which does not appear anywhere else in the string.

    The usage of the word "anywhere else" is taken to mean that the subsequences are totally non-intersecting. So for the string "ababa" the sequence "aba" is a valid solution because even though it is repeated, there is a partial intersection.

    This means the maximum length of a non-repeating substring is n2.

    One approach to this problem is one that is commonly used when attempting to avoid duplicated effort: dynamic programming.

    Create a heap with all substrings of length 1. For each substring keep a list of indices in the string where this substring starts. If, after generating all strings, this list is length 1 then this is a non-repeated substring.

    Note that can be no more than n2. unique characters in the string or one will not be repeated (and will be a unique substring).

    If no unique substring of length 1 is found, generate all substrings of length 2 by appending the character after the index to the string. Continue with increasing lengths until a unique string is found. A hashing algorithm such as Rabin-Karp that allows generating a composite hash in constant time (f(a + b) = g(f(a), b)) should be used.

    There are n2. iterations of this algorithm that each perform cn operations which is O(n2) overall.

  2. A set of items is donated to charity. Each item is to be sold for one dollar. A set of people comes to the auction. Each person fills out a piece of paper saying the number of dollars s/he wants to spend, and a list of items they would be willing to buy. Either give an algorithm to determine whether all the buyers can be satisfied, or show that the problem is NP-complete. Note that the number of dollars a buyer wants to spend and the number of items they are willing to buy are not necessarily equal.

    Representing this as a max flow problem is fairly straightforward.

    The edges from the source to the producers (buyers) are weighted according to the amount of money each is willing to spend. The center links simply represent the preferences of the buyers for objects. The links from the objects to the terminal are equally weighted (since all objects are equally weighted.

    The preference links used as max flow through this graph represent a set of purchases the buyers should make to maximize the money going to the charity. An augmenting path algorithm should be able to find an optimal solution in O(mn) time.

  3. You are given a directed graph of precedences between jobs. Jobs are of two types:

    • Type 1 can run when at least one of its predecessors has finished
    • Type 2 can run once all its predecessors have finished

    Design and analyze an efficient algorithm to determine whether all jobs in the system can run. Note that these graphs can have cycles and still run to completion.

    Represent the graph as an adjacency matrix or other form that allows the easy identification of nodes with no incoming edges. Nodes with incoming edges are inherently runnable.

    • For each node that is inherently runnable process each edge that is going out of that node.
      • If the edge goes into a Type 1 node then that edge is sufficient to allow running that node, so delete all edges incoming to that node.
      • If the edge goes into a Type 2 node then that edge does not constrain running, so it may be deleted.
    • Repeat for each node with no incoming edges until all edges are deleted or there are no unexamined nodes with no incoming edges.

    If all edges are deleted then all nodes are runnable. Any nodes with remaining edges have unsatifiable constraints.

    Each node is examinined once and each edge is deleted once, so the running time is O(n + m).

  4. In the double cover problem, the input is a set of subsets over a universe, U. The question is whether you can choose a set of subsets such that each element of U is in exactly two subsets. Show that the double cover problem is NP-complete. (Hint: look for similar covering problems.)

    I posit there exists some configuration of clauses such that if I can solve the double cover problem I can also solve the three satisfiability problem, but I have not been able to find the proper configuration of clauses for the reduction.