Chapter 0: Prologue

There are many variants of Rudrata’s problem, depending on whether the graph is undirected or directed, and whether a cycle or path is sought. Reduce the DIRECTED RUDRATA PATH problem to each of the following.(a)The (undirected) RUDRATA PATH problem.(b) The undirected RUDRATA PATH problem, which is just like RUDRATA PATH except that the endpoints of the path are specified in the input.

The $\mathbf{k}\mathbf{-}$SPANNING TREE problem is the following.Input: An undirected graph $\mathbf{G}\mathbf{=}\left(V,E\right)$ Output: A spanning tree of $\mathbf{G}$ in which each node has degree $\mathbf{\le }\mathbf{k}$, if such a tree exists.Show that for any $\mathbf{k}\mathbf{\ge }\mathbf{2}$:

1. $\mathbf{k}\mathbf{-}$ SPANNING TREE is a search problem.
2. $\mathbf{k}\mathbf{-}$ SPANNING TREE is NP-complete. (Hint: Start with $\mathbf{k}\mathbf{=}\mathbf{2}$ and consider the relation between this problem and RUDRATA PATH.)

Consider the following game. A “dealer” produces a sequence ${\mathit{s}}_{\mathbf{1}}\mathbf{}\mathbf{·}\mathbf{}\mathbf{·}\mathbf{}\mathbf{·}\mathbf{}{\mathit{s}}_{\mathbf{n}}$ of “cards,” face up, where each card ${\mathbf{s}}_{\mathbf{i}}$ has a value ${\mathbf{v}}_{\mathbf{i}}$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume $\mathbf{n}$ is even. (a) Show a sequence of cards such that it is not optimal for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal. (b) Give an $\mathbf{O}\left(n^2\right)$ algorithm to compute an optimal strategy for the first player. Given the initial sequence, your algorithm should precompute in $\mathbf{O}\left(n^2\right)$ time some information, and then the first player should be able to make each move optimally in $\mathbf{O}\left(1\right)$ time by looking up the precomputed information.

A vertex cover of a graph $\mathbf{G}\mathbf{=}\left(V,E\right)\mathbf{}$is a subset of vertices $\mathbf{S}\mathbf{\subseteq }\mathbf{V}$that includes at least one endpoint of every edge in E. Give a linear-time algorithm for the following task.

Input: An undirected tree $\mathbf{T}\mathbf{=}\left(V,E\right)\mathbf{}$.

Output: The size of the smallest vertex cover of T. For instance, in the following tree, possible vertex covers include$\left\{A,B,C,D,E,F,G\right\}$and$\left\{A,C,D,F\right\}$but not$\left\{C,E,F\right\}\mathbf{.}$The smallest vertex cover has size 3: $\left\{B,E,G\right\}\mathbf{.}$

$\mathbf{|}\mathbf{\psi }\mathbf{›}\mathbf{}\mathbf{=}\frac{\mathbf{1}}{\sqrt{\mathbf{2}}}\mathbf{|}\mathbf{00}\mathbf{›}\mathbf{+}\frac{\mathbf{1}}{\sqrt{\mathbf{2}}}\mathbf{|}\mathbf{11}\mathbf{›}$is one of the famous “Bell states,” a highly entangled state of its two qubits. In this question we examine some of its strange properties. (a) Suppose this Bell state could be decomposed as the (tensor) product of two qubits (recall the box on page ), the first in state ${\mathit{\alpha }}_{\mathbf{0}}\mathbf{|}\mathbf{0}\mathbf{›}\mathbf{+}{\mathit{\alpha }}_{\mathbf{1}}\mathbf{|}\mathbf{1}$and the second in state${\mathit{\beta }}_{\mathbf{0}}\mathbf{|}\mathbf{0}\mathbf{›}\mathbf{+}{\mathit{\beta }}_{\mathbf{1}}\mathbf{|}\mathbf{1}$. Write four equations that the amplitudes ${\mathit{\alpha }}_{\mathbf{0}}\mathbf{,}{\mathit{\alpha }}_{\mathbf{1}}\mathbf{,}{\mathit{\beta }}_{\mathbf{0}}\mathbf{}\mathit{a}\mathit{n}\mathit{d}\mathbf{}{\mathit{\beta }}_{\mathbf{1}}$must satisfy. Conclude that the Bell state cannot be so decomposed.

(b) What is the result of measuring the first qubit of $\mathbf{|}\mathit{\psi }\mathbf{⟩}$?

(c) What is the result of measuring the second qubit after measuring the first qubit? (d) If the two qubits in state$\mathbf{|}\mathit{\psi }\mathbf{⟩}$ are very far from each other, can you see why the answer to (c) is surprising?

Question: 0.1. In each of the following situations, indicate whether $\mathbf{\text{f=O(g),orf=Ω(g),}}$or both (in which case $\mathit{f}\mathbf{}\mathbf{=}\mathbf{\odot }\mathbf{\left(}\mathit{g}\mathbf{\right)}\mathbf{)}$

Mean and median. One of the most basic tasks in statistics is to summarize a set of observations ${\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{x}}_{\mathbf{n}}\mathbf{\subseteq }\mathbf{R}$ by a single number. Two popular choices for this summary statistic are:

• The median, which we’ll call${\mathit{\mu }}_1$

• The mean, which we’ll call${\mathit{\mu }}_{\mathbf{2}}$

(a) Show that the median is the value of $\mathit{\mu }$that minimizes the function

$\mathbf{\sum }_{\mathbf{i}}\mathbf{|}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }\mathbf{|}$

You can assume for simplicity that is odd. (Hint: Show that for any , the function decreases if you move either slightly to the left or slightly to the right.)

(b) Show that the mean is the value of $\mathit{\mu }$ that minimizes the function

$\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }{\mathbf{)}}^{\mathbf{2}}$

One way to do this is by calculus. Another method is to prove that for any $\mathbf{\mu }\mathbf{\in }\mathbf{R}$,

$\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }{\mathbf{)}}^{\mathbf{2}}\mathbf{=}\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}{\mathbf{\mu }}_{\mathbf{2}}{\mathbf{)}}^{\mathbf{2}}\mathbf{+}\mathbf{n}\mathbf{(}\mathbf{\mu }\mathbf{-}{\mathbf{\mu }}_{\mathbf{2}}{\mathbf{)}}^{\mathbf{2}}$

Notice how the function for ${\mathbf{\mu }}_{\mathbf{2}}$ penalizes points that are far from much more heavily than the function for ${\mathbf{\mu }}_1$ . Thus ${\mathbf{\mu }}_{\mathbf{2}}$ tries much harder to be close to all the observations. This might sound like a good thing at some level, but it is statistically undesirable because just a few outliers can severely throw off the estimate of ${\mathbf{\mu }}_{\mathbf{2}}$ . It is therefore sometimes said that ${\mathbf{\mu }}_1$ is a more robust estimator than ${\mathbf{\mu }}_{\mathbf{2}}$ . Worse than either of them, however, is ${\mathit{\mu }}_{\mathbf{\infty }}$ , the value of $\mathit{\mu }$that minimizes the function

$\underset{\mathbf{i}}{\mathbf{max}}\mathbf{|}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }\mathbf{|}$

(c) Show that ${\mathit{\mu }}_{\mathbf{\infty }}$ can be computed in O(n) time (assuming the numbers are ${\mathbf{x}}_{\mathbf{i}}$small enough that basic arithmetic operations on them take unit time).

The tramp steamer problem. You are the owner of a steamship that can apply between a group of port cities V . You make money at each port: a visit to city i earns you a profit of ${\mathit{p}}_{\mathbf{i}}$ dollars. Meanwhile, the transportation cost from port i to port j is ${\mathit{c}}_{\mathbf{i}\mathbf{j}}\mathbf{>}\mathbf{0}$ .You want to find a cyclic route in which the ratio of profit to cost is maximized.

To this end, consider a directed graph $\mathit{G}\mathbf{=}\left(V,E\right)$ whose nodes are ports, and which has edges between each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is

role="math" localid="1658920675878" $\mathit{r}\mathbf{\left(}\mathbf{c}\mathbf{\right)}=\underset{}{\frac{\sum \left(i,j\right)ic\mathit{P}\left({}_{ij}\right)}{\sum \left(i,j\right)ic{\mathit{C}}_{ij}}}$

Let r' be the maximum ratio achievable by a simple cycle. One way to determine r' is by binary search: by first guessing some ratio r , and then testing whether it is too large or too small. Consider any positive $\mathit{r}\mathbf{>}\mathbf{0}$ . Give each edge $\left(i,j\right)$ a weight of ${\mathit{w}}_{\mathbf{i}\mathbf{j}}\mathbf{=}\mathit{r}{\mathit{c}}_{\mathbf{i}\mathbf{j}}\mathbf{-}{\mathit{p}}_{\mathbf{j}}$ .

1. Show that if there is a cycle of negative weight, then .
2. Show that if all cycles in the graph have strictly positive weight, then $\mathit{r}\mathbf{<}{\mathit{r}}^{\mathbf{*}}$.
3. Give an efficient algorithm that takes as input a desired accuracy $\mathbf{\in }\mathbf{>}\mathbf{0}$ and returns a simple cycle c for which $\mathit{r}{\left(C\right)}^{\mathbf{3}}{\mathit{r}}^{\mathbf{*}}\mathbf{-}\mathbf{\in }$ Justify the correctness of your algorithm and analyze its running time in terms of $\left|V\right|\mathbf{,}\mathbf{\in }$ and $\mathbf{R}\mathbf{=}{\mathbf{max}}_{\left(i,j\right)\mathbf{iE}}\left(\frac{P_J}{C_{\mathrm{IJ}}}\right)$ .

Here’s a problem that occurs in automatic program analysis. For a set of variables${\mathit{x}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{x}}_{\mathbf{n}}$, you are given some equality constraints, of the form “ ${\mathit{x}}_{\mathbf{i}}\mathbf{=}{\mathit{x}}_{\mathbf{j}}$” and some disequality constraints, of the form “ ${\mathit{x}}_{\mathbf{i}}\mathbf{\ne }{\mathit{x}}_{\mathbf{j}}$.” Is it possible to satisfy all of them?

For instance, the constraints.

$\mathbf{}{\mathit{x}}_{\mathbf{1}}\mathbf{=}{\mathit{x}}_{\mathbf{2}}\mathbf{,}{\mathit{x}}_{\mathbf{2}}\mathbf{=}{\mathit{x}}_{\mathbf{3}}\mathbf{,}{\mathit{x}}_{\mathbf{3}}\mathbf{=}{\mathit{x}}_{\mathbf{4}}\mathbf{,}{\mathit{x}}_{\mathbf{1}}\mathbf{\ne }{\mathit{x}}_{\mathbf{4}}$

cannot be satisfied. Give an efficient algorithm that takes as input m constraints over $\mathit{n}$ variables and decides whether the constraints can be satisfied.