Chapter 9

Find the maximum number of guesses needed to find the positive integer \(n \leq N\) for each value of \(N .\) (Use the binary search algorithm.) $$97$$

Construct a binary search tree for each set. $$\mathbf{i}, \mathbf{a}, \mathbf{u}, \mathbf{o}, \mathbf{e}$$

How many edges does a spanning tree of each graph have? $$K_{n}$$

Construct a binary search tree for each set. $$ a, e, i, 0, u $$

Find the maximum number of guesses needed to find the positive integer \(n \leq N\) for each value of \(N .\) (Use the binary search algorithm.) $$243$$

Construct a binary search tree for each set. $$\mathrm{a}, \mathrm{e}, \mathrm{i}, \mathrm{o}, \mathrm{u}$$

Find the maximum number of guesses needed to find the positive integer \(n \leq N\) for each value of \(N .\) (Use the binary search algorithm.) $$1976$$

Construct a binary search tree for each set. $$ \mathrm{i}, \mathrm{a}, \mathrm{e}, \mathrm{o}, \mathrm{u} $$

Find the maximum number of guesses needed to find the positive integer \(n \leq N\) for each value of \(N .\) (Use the binary search algorithm.) $$3076$$

Construct a binary search tree for each set. $$\mathbf{i}, \mathbf{a}, \mathbf{e}, \mathbf{o}, \mathbf{u}$$

Among the \(N\) coins in a collection plate, one is counterfeit and heavier. Using an equal-arm balance, find the minimum number of weighings needed to ascertain the counterfeit, for each value of \(N.\) $$12$$

Construct a binary search tree for each set. $$8,5,2,3,13,21$$

Using Kruskal's algorithm, construct a spanning tree for each graph, starting at \(a\).

Among the \(N\) coins in a collection plate, one is counterfeit and heavier. Using an equal-arm balance, find the minimum number of weighings needed to ascertain the counterfeit, for each value of \(N.\) $$13$$

Construct a binary search tree for each set. $$5,2,13,17,3,11$$

Among the \(N\) coins in a collection plate, one is counterfeit and heavier. Using an equal-arm balance, find the minimum number of weighings needed to ascertain the counterfeit, for each value of \(N.\) $$28$$

Among the \(N\) coins in a collection plate, one is counterfeit and heavier. Using an equal-arm balance, find the minimum number of weighings needed to ascertain the counterfeit, for each value of \(N.\) $$75$$

Construct a binary search tree for each set. $$\text {inning, input, output, insect, inroad, inset, insole}$$

order, ouch, outfit, outing, outcome, outlet, outcry

Four coins, \(a\) through \(d,\) in a plate look identical, but one is counterfeit and heavier. Using an equal-arm balance and minimum weighings, identify the counterfeit coin and determine if it is lighter or heavier. Display your analysis in a decision tree.

Let \(n\) denote the number of vertices of a tree and \(e\) the number of edges. Verify that \(e=n-1\) for each tree. IMAGE IS NOT AVAILABLE TO COPY

Construct a binary search tree for each set. order, ouch, outfit, outing, outcome, outlet, outcry

Using Kruskal's algorithm, construct a spanning tree for each graph, starting at \(a\).

Let \(n\) denote the number of vertices of a tree and \(e\) the number of edges. Verify that \(e=n-1\) for each tree. IMAGE IS NOT AVAILABLE TO COPY

Construct a binary search tree for each set. canna, coleus, balsam, celosia, dahlia, azalea, tulip

Let \(n\) denote the number of vertices of a tree and \(e\) the number of edges. Verify that \(e=n-1\) for each tree. IMAGE IS NOT AVAILABLE TO COPY

Let \(n\) be a positive integer and key an arbitrary positive integer \(\leq n .\) Using binary search, write an algorithm to find key and the number of guesses made.

How many bonds does the hydrocarbon molecule \(\mathrm{C}_{n} \mathrm{H}_{2 n+2}\) have? Assume a carbon molecule has degree four.

Among seven identical coins lies a heavier counterfeit coin. Write an algorithm to identify the false coin using an equal-arm balance and minimum weighings.

Let \(T\) be a tree with vertices \(v_{1}, \ldots, v_{n} .\) Show that \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)=2 n-2\)

Let \(\Sigma=\\{0,1\\},\) where \(0<1 .\) The language \(\Sigma^{n}\) can be defined as \(\Sigma^{n}=\left\\{w x | w \in \Sigma^{n-1}, x \in \Sigma\right\\}\)

For what values of \(n\) is \(K_{n}\) a tree?

Let \(\Sigma=\\{0,1\\},\) where \(0 \prec 1 .\) The language \(\Sigma^{n}\) can be defined as \(\Sigma^{n}=\left\\{w x | w \in \Sigma^{n-1}, x \in \Sigma\right\\}\).

Determine if each complete bipartite graph is a tree. $$K_{1,2}$$

Using this definition, display the elements of \(\bigcup_{n=0}^{3} \Sigma^{n}\) in a rooted tree, where the vertices at level \(k\) represent the elements of \(\Sigma^{k}\). Draw a full binary tree that is not balanced.

Determine if each complete bipartite graph is a tree. $$K_{1,3}$$

Determine if each complete bipartite graph is a tree. $$K_{2,2}$$

Rewrite each infix expression in prefix form. $$a \uparrow(b \uparrow c)+d / e-f$$

Using this definition, display the elements of \(\bigcup_{n=0}^{3} \Sigma^{n}\) in a rooted tree, where the vertices at level \(k\) represent the elements of \(\Sigma^{k}\) Determine all simple paths in the maze in Figure 9.44 that a person at gate A can take to exit through gate \(\mathrm{Z}\) . (Hint: Draw a tree rooted at A.)

Rewrite each infix expression in prefix form. $$(a+b * c) /(d-e / f) \uparrow g$$

Determine if each complete bipartite graph is a tree. $$K_{2,3}$$

Rewrite each infix expression in prefix form. $$(a+b * c) /(d-e / f) \uparrow g$$

For what values of \(m\) and \(n\) is \(K_{m, n}\) a tree?

Rewrite each infix expression in prefix form. $$a-(b * c+d) / e * f-g \uparrow h$$

Using the following frequency table, construct a Huffman tree for each character in the alphabet \((a, b, c, d, e, f)\) $$ \begin{array}{|l|l|l|l|l|l|}\hline \text { Character } & {a} & {b} & {c} & {d} & {e} & {f} \\ \hline \text { Frequency } & {4} & {1} & {2} & {3} & {5} & {4} \\\ \hline\end{array} $$

Find the number of vertices of a full ternary tree with four internal vertices.

Construct a binary search tree using the words in each phrase or sentence. Fourscore and seven years ago.

Draw all nonisomorphic trees with the given number of vertices \(n .\) $$2$$

Using the following frequency table, construct a Huffman tree for the alphabet $\\{a, b, c, e, g, l, o, s, u\\}$$$\begin{array}{|l||lllllllll|} \hline \text { Character } & a & b & c & e & g & l & o & s & u \\\\\hline \text { Frequency } & 4 & 3 & 2 & 3 & 1 & 2 & 4 & 1 & 5 \\\\\hline\end{array}$$

Find the number of leaves of a full 5 -ary tree with 156 vertices.