CompSci 263, Winter 2017, Homework 1

  1. Suppose we could solve 4SUM in time $O(n^c)$ for some $c<2$. What would that imply about the time to solve subset sum?

    1. Suppose we have an unbalanced instance of 3SUM where the three input lists of numbers $A$, $B$, and $C$ have different lengths $l$, $m$, and $n$ respectively, with $l < m < n$. Recall that the 3SUM algorithm described in class sorted $B$ and $C$, and then looped through the elements of $A$. For each $a_i\in A$ it solves a 2SUM instance in the sorted lists $B$ and $C$ to find $b_j$ and $c_k$ with $b_j+c_k=a_i$. What is the time for this algorithm as a function of $l$, $m$, and $n$ (using $O$-notation)?

    2. Can you find an algorithm with a better dependence on $l$, $m$, and $n$? For the purposes of this question, to compare two time bounds, ignore any logarithmic or word-size factors in the time bounds, in order to simplify them to polynomials of $l$, $m$, and $n$. You can express this simplification by using $\tilde O$ instead of $O$ when writing a time bound.

    1. Suppose that we are given as input a directed acyclic graph, with $m$ edges and $n$ vertices, and we wish to determine for every pair $(v,w)$ of vertices whether the graph has a path from $v$ to $w$. This can be done, for instance, in time $O(mn)$ by doing a breadth-first search from each vertex $v$ to find all of the vertices $w$ that it can reach. Describe an algorithm that, on a computer with constant-time bitwise operations on $w$-bit words, can solve this problem in time $O(mn/w)$.

    2. Can you achieve the same speedup for finding all reachable pairs on a directed graph that is not acyclic?