91影视

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{鈮�}\mathbf{k}$, if such a tree exists.Show that for any $\mathbf{k}\mathbf{鈮�}\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 鈥渄ealer鈥� produces a sequence ${\mathit{s}}_{\mathbf{1}}\mathbf{}\mathbf{路}\mathbf{}\mathbf{路}\mathbf{}\mathbf{路}\mathbf{}{\mathit{s}}_{\mathbf{n}}$ of 鈥渃ards,鈥� 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{鈯�}\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{.}$

Question: 0.1. In each of the following situations, indicate whether $\mathbf{\text{蹿=翱(驳),辞谤蹿=惟(驳),}}$or both (in which case $\mathit{f}\mathbf{}\mathbf{=}\mathbf{鈯�}\mathbf{\left(}\mathit{g}\mathbf{\right)}\mathbf{)}$

Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and five other people whom they don鈥檛 know. Give an efficient algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. Give the running time in terms of n

Show that, if c is a positive real number, then g(n) = 1 + c + c² + 路 路 路 + cⁿ is:

(a) 螛(1) if c < 1.

(b) 螛(n) if c = 1.

(c) 螛(cⁿ) if c > 1.

The moral: in big-螛 terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

The Fibonacci numbers ${\mathbf{F}}_{\mathbf{0}}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{,}{\mathbf{F}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}$ are defined by the rule

${\mathbf{F}}_{\mathbf{0}}\mathbf{=}\mathbf{0}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{=}\mathbf{1}\mathbf{,}{\mathbf{F}}_{\mathbf{n}}\mathbf{=}{\mathbf{F}}_{\mathbf{n}\mathbf{鈭�}\mathbf{1}}\mathbf{+}{\mathbf{F}}_{\mathbf{n}\mathbf{鈭�}\mathbf{2}}$.

In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.

(a) Use induction to prove that ${\mathbf{F}}_{\mathbf{n}}\mathbf{鈮�}{\mathbf{2}}^{\mathbf{0}\mathbf{.5}\mathbf{n}}$for $\mathbf{n}\mathbf{鈮�}\mathbf{6}$.

(b) Find a constant $\mathbf{c}\mathbf{<}\mathbf{1}$such that${\mathbf{F}}_{\mathbf{n}}\mathbf{鈮�}{\mathbf{2}}^{\mathbf{cn}}$ for all $\mathbf{n}\mathbf{鈮�}\mathbf{0}$. Show that your answer is correct.

(c) What is the largest$\mathbf{c}$ you can find for which ${\mathbf{F}}_{\mathbf{n}}\mathbf{=}\mathbf{惟}\mathbf{\left(}{\mathbf{2}}^{\mathbf{cn}}\mathbf{\right)}$?