Homework Assignments

Note: When you describe an algorithm, do not just use code or pseudocode. Write in clear English paragraphs that describe the high-level strategy of your algorithm. Pictures are often very helpful. You may, of course, use pseudocode, but this is in addition to your English explanation not instead of it.

Homework 1

Due Thursday Wednesday, September 14

  1. A directed graph is acyclic if it has no cycles.
    1. Show that any acyclic graph has a source (a node with no incoming edges).
    2. Show that a graph with \(n\) nodes is acyclic if and only if its nodes can be numbered 1 to \(n\) so that all edges go from lower to higher numbers (use the property in part A repeatedly).
    3. Describe a polynomial-time algorithm that decides whether a graph is acyclic (use the idea from part B).
  2. Prove by induction on \(|x|\) that the following Turing machine computes the function \(f(x) = \sqcup x\), where \(x\) is a finite string of \(0\) and \(1\) characters. You may assume that the string \(x\) is followed by a space, i.e. the input to the machine is "\(\triangleright x \sqcup\)". $$ \Sigma = \{0, 1, \sqcup, \triangleright\} $$ $$ K = \{s, q, q_0, q_1\} $$
    \(\sigma\in\Sigma\) \(p\in K\) \(\delta(\sigma, p)\)
    \(0\)\(s\)\((0, s, \rightarrow)\)
    \(1\)\(s\)\((1, s, \rightarrow)\)
    \(\sqcup\)\(s\)\((\sqcup, q, \leftarrow)\)
    \(\triangleright\) \(s\) \((\triangleright, s, \rightarrow)\)
    \(0\)\(q\)\((\sqcup, q_0, \rightarrow)\)
    \(1\)\(q\)\((\sqcup, q_1, \rightarrow)\)
    \(\sqcup\) \(q\) \((\sqcup, q, \leftrightarrow)\)
    \(\triangleright\) \(q\) \((\triangleright, h, \rightarrow)\)
    \(0\)\(q_0\)\((0, s, \leftarrow)\)
    \(1\)\(q_0\)\((0, s, \leftarrow)\)
    \(\sqcup\) \(q_0\) \((0, s, \leftarrow)\)
    \(\triangleright\) \(q_0\) \((\triangleright, h, \rightarrow)\)
    \(0\)\(q_1\)\((1, s, \leftarrow)\)
    \(1\)\(q_1\)\((1, s, \leftarrow)\)
    \(\sqcup\) \(q_1\) \((1, s, \leftarrow)\)
    \(\triangleright\) \(q_1\) \((\triangleright, h, \rightarrow)\)

    Note: here \(\leftrightarrow\) represents no movement of the machine.

  3. Provide a full description of a two-string Turing machine for the palindrome decision problem. Your machine should execute in \(O(n)\) steps where \(n\) is the length of the input string (not including \(\triangleright\) and the terminating \(\sqcup\)). Specify the sets \(\Sigma\) and \(K\) and give the full table representation for the transition function \(\delta\). Demonstrate your machine on two examples, one that halts with "yes" and another that halts with "no."
  4. In class, I stated without proof that, given any \(k\)-string Turing machine \(M\) operating within time \(f(n)\), we can construct a single-string Turing machine \(M'\) operating within time \(O(f(n)^2)\) such that for any input \(x\), \(M(x) = M'(x)\).
    1. Give a simple counterexample demonstrating that the converse is false.
    2. In the case of the palindrome decision problem, we saw that the converse does hold: the single-string Turing machine is \(O(n^2)\) but the two-string machine is \(O(n)\). What property of the single-string machine allows for a speed-up when using multiple tapes?

Comments on Solutions

Solutions to Homework 1 were presented in class. However, there are a couple points that deserve some follow-up.

(1.c) The algorithm I presented constructs the labeled graph by selecting a source, labeling it, removing it to create a subgraph, then repeating the process on the subgraph. As a last step, I stated that you should check that the labeling has the desired property, that edges always go from lower-labeled vertices to higher-labeled vertices. It was pointed out that this last step is not really necessary because if the graph has a cycle, there will be an iteration in which we can not find a source in the subgraph.

Although this is true, the exercise does not have you prove the result you would need to establish this. Although we have shown that if a graph is acyclic, then it has a source, the converse is certainly false: it is easy to exhibit a graph with a source that is not acyclic. In order to conclude that the last step in my algorithm is not necessary, you need to show that if a graph is acyclic, we will fail to find a source at some iteration. This is not difficult to prove. Suppose \(G\) has a cycle $$ v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n \rightarrow v_1. $$ For any of the \(v_i\) to become a source, and thus be removed, its predecessor must be removed previously. That is, \(v_i\) will become a source and be removed only if \(v_i\) became a source and was removed on a previous iteration. This is clearly, nonsense, leading to the conclusion that \(v_i\) can only become a source if it was a source originally.

Two students suggested ways to reduce the asymptotic running time to \(O(n^2)\) from \(O(n^3)\). The suggestion I remember was just to compute the in-degrees of all the vertices so that identification of a source is \(O(n)\).

Homework 2

Due Wednesday, September 21

  1. Complete the RAM implementation of integer multiplication using the approach discussed in class: to multiply \(x\) and \(y\), write \(y = y_n 2^n + y_{n-1} 2^{n-1} + \cdots + y_1 2 + y_0\) where \(y_i\) is \(0\) or \(1\) so that $$ x \cdot y = y_n (x\cdot 2^n) + y_{n-1} (x\cdot 2^{n-1}) + \cdots + y_1 (x\cdot 2) + y_0 x. $$ This sum of products can be computed using repeated doubling of \(x\) and halving of \(y\). The full RAM instruction set is given below.
    Instruction Operand Description
    READ \(j\) \(r_0 \leftarrow i_j\)
    READ \([j]\) \(r_0 \leftarrow i_{r_j}\)
    STORE \(j\) \(r_j \leftarrow r_0\)
    STORE \([j]\) \(r_{r_j} \leftarrow r_0\)
    LOAD \(x\) \(r_0 \leftarrow x\)
    ADD \(x\) \(r_0 \leftarrow r_0 + x\)
    SUB \(x\) \(r_0 \leftarrow r_0 - x\)
    HALF \(r_0 \leftarrow \lfloor r_0 / 2 \rfloor\)
    JUMP \(a\) \(\kappa \leftarrow a\)
    JPOS \(a\) if \(r_0 > 0\) then \(\kappa \leftarrow a\)
    JZERO \(a\) if \(r_0 = 0\) then \(\kappa \leftarrow a\)
    JNEG \(a\) if \(r_0 < 0\) then \(\kappa \leftarrow a\)
    HALT \(\kappa \leftarrow 0\)

    In the LOAD, ADD, and SUB instructions, \(x\) represents any one of the following operands:

    • a register address \(j\),
    • an indirect register address \([j]\), or
    • an integer literal \(=j\).
    Thus there is a slight abuse of notation in the description of these instructions. If, for example, in the SUB instruction \(x\) is the indirect address \([j]\), then SUB will compute \(r_0 \leftarrow r_0 - r_{r_j}\). To subtract an integer literal, for example, to compute \(r_0 \leftarrow r_0 - 1\) we would use the literal operand "\(=1\)".

    \(\kappa\) is the program counter, which initially has the value 1. It is incremented by every instruction, except for the jump and HALT instructions which set the value of \(\kappa\) explicitly.

  2. Our first implemenation of PALINDROME used a single tape holding \(n+1\) symbols: the start symbol and \(n\) symbols of the string to be tested. (We consider all unused cells as having value \(\sqcup\), so we do not need to count the terminating \(\sqcup\).) Thus it uses \(O(n)\) storage.

    Our two-string implementation of PALINDROME copied the entire input string to a second string, and the first string was used in a read-only fashion. With multi-string machines, it is common practice to not count the first string as storage so long as it is not written to. Nonetheless, the copy of the input requires \(n+1\) storage cells and so the two-string implementation also uses \(O(n)\) storage.

    Show that there is a three-string Turing Machine for PALINDROME with \(O(\lg n)\) storage, not counting the input string.

  3. CLRS, Problem 16-5 (Off-line caching)

Homework 3

Due Wednesday, September 28

  1. Recall that in the activity selection problem, we are given a list of activities \(\langle a_1, a_2, \ldots, a_n\rangle\) along with their start and finish times \((s_i, f_i), i = 1, 2, \ldots n\). We only have a single room available and we wish to schedule as many activities as possible. Let \(S\) consist of the \(n\) activities \(a_1, a_2, \ldots, a_n\) and let \(\mathcal{I}\), the family of independent sets, consist of all sets of mutually compatible activities. Is \(M = (S, \mathcal{I})\) a matroid? Why or why not?
  2. A cycle \(C\) of a matroid \((S, \mathcal{I})\) is a setwise minimal dependent set. By "setwise minimal dependent set," we mean that \(C\) is dependent but no proper subset of \(C\) is dependent. Let \(A\in\mathcal{I}\) be a maximal independent set and \(x\notin A\). Prove that there is a unique cycle contained in \(A\cup \{x\}\).
  3. CLRS, Exercise 16.5-2

Homework 3 Solutions

  1. The answer is "No." Show by counterexample that the exchange property does not hold.
  2. Suppose \(A\) is maximal. Then \(A \cup \{x\}\) must be dependent since \(| A \cup \{x\} | > | A |\). Therefore, there is a minimal dependent set in \(A \cup \{x\}\), which is by definition a cycle. To prove that the cycle is unique, suppose to the contrary that there are two cycles \(C_1\) and \(C_2\) in \(A \cup \{x\}\). Let \(y \in C_1 \setminus C_2\), i.e. \(y\) is an element in \(C_1\) that is not in \(C_2\), which must exist if \(C_1 \neq C_2\) and \(C_2\) is minimal. Then the set \(C_1 \setminus \{y\}\) is independent since \(C_1\) is a minimal dependent set. Also, \(C_1 \cup C_2 \setminus \{x\}\) is independent since it is contained in \(A\) and, moreover, \(| C_1 \cup C_2 \setminus \{x\} | \geq | C_1 \setminus \{y\} |\). Therefore, by the exchange property, we can copy elements from \(C_1 \cup C_2 \setminus \{x\}\) to \(C_1 \setminus \{y\}\) until the sets are the same size. The resulting set is independent and can not contain \(y\), because then it would contain all of \(C_1\), which is dependent. So the set must be \(C_1 \cup C_2 \setminus \{y\}\). But this contains \(C_2\), which is dependent, making the whole set dependent. This is a contradiction since, by the exchange property, \(C_1 \cup C_2 \setminus \{y\}\) is independent.

  3. I replaced the previous solution with a better one. This is a slight modification to a solution submitted by a student.

    Key observation: Any deadline in \(A\) can occur at most \(|A|\) times. Therefore, we can ignore all deadlines \(d\) in \(A\) such that \(d > |A|\).

    Let \(m = |A|\). Create an \(m\)-long array \(c\) and initialize it to all zeroes. We will use the array \(c\) to count the number of occurrences of each deadline \(d\) such that \(1 \leq d\leq m\). Make one pass through \(A\), incrementing the appropriate entry in \(c\) for each item, ignoring any deadlines that are greater than \(m\). Now, make one pass through \(c\) to compute the accumulated counts (we need to do this because \(N_t(A)\) is the number of deadlines in \(A\) less than or equal to \(t\)): 

          for i = 2 to |A|
         c[i] = c[i] + c[i-1]
    Now we just need to check that \(c[i] \leq i\), which is one more loop of length \(m = |A|\). The final algorithm is \(O(|A|)\) since each of the loops has at most \(|A|\) iterations.

Homework 4

Due Wednesday, October 5

  1. CLRS, Exercises 17.1-2, 17.2-1, and 17.4-3.

Homework 5

Due Wednesday, October 12

  1. CLRS, Exercises 6.5-5 and 6.5-9; Problem 6-2.

Homework 6

Due Monday, October 24
(extended due date due to OS exam)

  1. CLRS, 19.2-1, 19.3-2, Problem 19-3 (a).
  2. We defined the link procedure for binomial heaps: we link two binomial trees of rank \(k\), that is, two \(B_k\)'s, by making the root node of one \(B_k\) a child of the root node of the other \(B_k\); we make sure we choose the \(B_k\) to be the child that preserves the min-heap property. Furthermore, we described how this procedure is used to "clean-up" a binomial heap so that there is at most one tree of each rank. Show that this same linking procedure works for trees in a Fibonacci heap, that it preserves the property that the size of a tree is exponential in its rank, and that we can use it in a similar way to clean-up a Fibonacci heap.

Homework 6 Solutions

  1. (19.2-1) See scanned diagrams, below. In my solution, I didn’t worry much about the order of the trees in the root list.
  2. (19.3-2) Any call to Fib-Heap-Decrease-Key on node \(p\) that does not cause a cascade of cuts is \(O(1)\). These are calls that either do not break the min-heap property for \(p\) and its parent \(p’\) or, if it does break the min-heap property, is not the second child to be cut from \(p’\). Consider a call to Fib-Heap-Decrease-Key on node \(p\) that causes an \(l\)-long cascade of cuts. Then each of the nodes (parent, grandparent, etc.) in the \(l\)-long cascade must previously have had a first child cut. That is, there must have been at least \(l\) calls to Fib-Heap-Decrease-Key that were \(O(1)\). The total cost of the \(l+1\) operations, that is \(l\) \(O(1)\) operations followed by an \(l\)-long cascade operation, is \(2l\), or \(O(l)\). The amortized cost is therefore \(O(l)/(l+1) = O(1)\).
  3. (19.3) (a) If \(k < x.val\), Fib-Heap-Change-Key is the same as Fib-Heap-Decrease-Key, which we have seen has \(O(1)\) amortized cost. If \(k = x.val\), there is nothing to do, and the operation is trivially \(O(1)\). Consider the case where \(k > x.val\). Then \(k\) may be larger than the value of one or more of \(x\)’s children, and these children will need to be cut from the tree and added to the root list in order to maintain the min-heap property. However, if a second child is cut from \(x\), then \(x\) itself should be cut and added to the route list, which could cause a cascade of cuts up the tree (as in 19.3-2). Using the accounting approach discussed in lecture, the cascading cuts are paid for by the 2 credits previously set aside for a node when it had its first child cut. However, this still leaves the cost of cutting \(O(\lg n)\) children of \(x\). Thus, with no modifications to the accounting, Fib-Heap-Decrease-Key is \(O(\lg n)\) in this case.

    [I haven’t thought too hard about whether there is a change to the accounting method that can make this last case \(O(1)\). Perhaps by charging an extra credit every time trees are linked, and keeping the credit with the root of the subordinate tree. Then every child cut due to Fib-Heap-Change-Key would have a credit saved to pay for its own cut.]
  4. (#2) This is actually pretty easy. We showed in class that for any node \(p\) in a Fibonacci heap, if we order its children \(y_1, y_2, \ldots, y_k\) in the order they were added as children, then the \(i\)th child has rank at least \(i-2\). The smallest trees that satisfy this condition are the “Fibonacci trees” \(F_0, F_1, F_2, \ldots\) whose sizes \(f_0, f_1, f_2, \ldots\) satisfy the Fibonacci recursion. \(F_n\) has rank \(n\) and the sizes \(f_n\) are exponential in \(\phi = (1 +\sqrt{5})/2\) (the golden ratio), \(f_n \geq\phi^n\). Now suppose in my Fibonacci heap I have two trees of rank \(k\). Whichever has the larger root value is linked as a child of the other tree, preserving the min-heap property. Each of the trees had size \(\geq \phi^k\), so the linked tree has rank \(k+1\) and size \(\geq 2\phi^k > \phi^{k+1}\) since \(2 > \phi\). Therefore, the exponential size property is preserved in the new tree. The procedure to clean-up the heap, then, is to start with the rank-0 trees, combining to form rank-1 trees, leaving at most one rank-0 tree; then combining rank-1 trees to produce rank-2 trees, etc., until there is at most one tree of any rank.

Homework 7

Due Monday, October 31

  1. Let \(f\) be a flow in \(G\). Prove the following:
    1. For any \(s,t\)-cut \(A, B\), \(|f| = f(A,B)\).
    2. Let \(G_f\) be the residual graph. If \(f^*\) is a max flow in \(G\), then the value of a max flow in \(G_f\) is \(|f^*| - |f|\).
  2. Given a flow \(f\) on a directed graph \(G\) with positive edge capacities:
    1. Show how to construct the residual graph \(G_f\) in \(O(m)\) time.
    2. Using (A), show how to modify Dijkstra's algorithm to efficiently calculate an agumenting path of maximum bottleneck capacity.
  3. CLRS, 26.1-7

Homework 8

Due Monday, November 7

  1. CLRS, Exercises 27.1-3, 27.1-6, and 27.1-7.

Homework 9

Due Wednesday, November 16

  1. Let \(G\) be a finite directed graph with adjacency matrix \(A\) to which we have added all self-loops, i.e. \(A_{ii} = 1\). The adjacency matrix of the transitivive closure of \(G\) is \(B = A^{2^{\lceil \lg n\rceil}}\). Vertex \(j\) is reachable from vertex \(i\) in \(G\) iff \(B_{ij} \neq 0\). Determine the parallel running time and total work to compute \(B\); conclude that graph reachability is in NC.
  2. Compute the Fourier expansions of the following functions:
    1. \(min_2 : D_2 \rightarrow \{-1, 1\}\), the minimum of the two inputs.
    2. The indicator function \(1_{a} : D_n \rightarrow \{-1, 1\}\) where \(a \in D_n\). \(1_{a}(x) = -1\) if \(x = a\) and is \(1\) if \(x\neq a\).
  3. How many boolean functions \(f : D_n \rightarrow \{-1, 1\}\) have exactly one non-zero Fourier coefficient?
  4. Prove that \(f : D_n \rightarrow \{-1, 1\}\) has at most one Fourier coefficient with magnitude exceeding \(1/2\).

Homework 9 Hints

(2.b) You need to find the Fourier coefficients of the indicator function. The indicator function is 1 for all \(x\neq a\) and is -1 only when \(x = a\), where \(x, a \in D_n\). What can you say about the inner product \(\langle 1_a, \chi_S\rangle\)?

Note: \(\sum_{x\in D_n} \chi_S(x) = 0\) for \(S\neq\emptyset\). This follows from the fact that \(\{\chi_S : S \subseteq [n]\}\) is an orthonormal basis for the vector space of boolean functions.

(3) Write \(f = \sum_{S\subseteq [n]} \hat{f}(S) \chi_S\). What does it mean to say that only one of the coefficients \(\hat{f}(S) \neq 0\)? How many distinct functions can have this property?

(4) I gave a hint for this one in class on Monday. Notice that \(\langle f, \chi_S\rangle\) is the normalized number of agreements between \(f\) and \(\chi_S\) minus the number of disagreements: $$ \langle f, \chi_S\rangle = 2^{-n} (|\{ x\in D_n : f(x) = \chi_S(x)\}| - |\{ x\in D_n : f(x) \neq chi_S(x)\}|) $$ Suppose there are two Fourier coefficients greater than \(\frac{1}{2}\). Then for two different sets \(S, T \subseteq [n]\), \(\langle f, \chi_S\rangle > \frac{1}{2}\) and \(\langle f, \chi_T\rangle > \frac{1}{2}\). For how many \(x\in D_n\) must \(f\) and \(\chi_S\) agree to give \(\langle f, \chi_s\rangle > \frac{1}{2}\)? If \(f\) agrees with both \(\chi_S\) and \(\chi_T\) for some large number of \(x\in D_n\), what can you conclude about \(\langle \chi_S, \chi_T\rangle\)? You should get a contradiction.

Homework 10

Due Monday, November 28 Wednesday, November 30

  1. Show directly from the definition that the convolution operator is associative and commutative.
  2. The exponential distribution with rate \(\lambda > 0\) is a continuous distribution defined by the probability density function (pdf) $$ f(x) = \lambda \exp(-\lambda x) $$ where \(0 \leq x < \infty\). Compute the moment generating function for the exponential distribution use it to determine the mean and variance of a exponentially-distributed random variable \(X\).

Ungraded Practice Problems

  1. Compute the Fourier expansion of the selection function \(Sel : D_3 \rightarrow \{-1,1\}\) which outputs \(x_2\) if \(x_1 = -1\) and outputs \(x_3\) if \(x_1 = 1\).
  2. Compute the Fourier expansion of the sortedness function \(Sort_4 : D_4 \rightarrow \{-1, 1\}\) defined by \(Sort_4(x) = -1\) if and only if \(x_1 \leq x_2 \leq x_3 \leq x_4\) or \(x_1 \geq x_2 \geq x_3 \geq x_4\).

Complexity Exercises

  1. CLRS, Exercises 34.1-1 and 34.1-5.
  2. A hamiltonian path from \(u\) to \(v\) in an undirected graph \(G = (V, E)\) is a simple path from \(u\) to \(v\) that visits each vertex in \(V\) exactly once. The decision problem HAM-PATH is: given \(G = (V, E)\), \(u\), and \(v\), is there a hamiltonian path from \(u\) to \(v\)? Show that HAM-PATH is in NP.
  3. Let \(G = (V, E)\) be an undirected graph. A set of vertices \(S\) contained in \(V\) is independent if no two vertices in \(S\) are joined by an edge. The decision problem INDEPENDENT-SET is: given \(G = (V, E)\) and a positive integer \(k\), does \(G\) contain an independent set of size at least \(k\)? A set of vertices \(T\) contained in \(V\) is a vertex cover if every edge \(e\in E\) has at least one end in \(T\). The decision problem VERTEX-COVER is: given \(G = (V, E)\) and a positive integer \(k\), does \(G\) contain a vertex cover of size at most \(k\)? Prove that, given a graph \(G = (V, E)\), \(S\) is an independent set if and only if \(T = V - S\) is a vertex cover. Conclude that INDEPENDENT-SET can be reduced to VERTEX-COVER and vice versa.