91Ó°ÊÓ

Concern \(n\) teams that play a single-elimination tournament. After the teams are assigned, in how many ways can the tournament unfold? For example, if there are three teams, Scientists, Whales, Pilots, assigned as one way the tournament can unfold is There are three other ways that the tournament can unfold: (a) Whales defeat Scientists; Pilots defeat Whales. (b) Scientist defeat Whales; Scientists defeat Pilots. (c) Scientist defeat Whales; Pilots defeat Scientists. Thus, if three teams play a single-elimination tournament, after the teams are assigned, the tournament can unfold in four ways.

Four coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same. Draw a decision tree that gives an algorithm that identifies in at most two weighings the bad coin (but not necessarily determines whether it is heavier or lighter than the others) using only a pan balance.

Find the disjunctive normal form of each function and draw the combinatorial circuit corresponding to the disjunctive normal form. $$\begin{array}{cc|c}\hline x & y & f(x, y) \\\\\hline 1 & 1 & 1 \\\1 & 0 & 0 \\\0 & 1 & 1 \\\0 & 0 & 1 \\\\\hline\end{array}$$

Eight coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same. Draw a decision tree that gives an algorithm that identifies in at most three weighings the bad coin and determines whether it is heavier or lighter than the others using only a pan balance.

Place the words FOUR SCORE AND SEVEN YEARS AGO OUR FOREFATHERS BROUGHT FORTH, in the order in which they appear, in a binary search tree.

For which values of \(m\) and \(n\) is the complete bipartite graph on \(m\) and \(n\) vertices a tree?

Thirteen coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same. How many weighings in the worst case are required to find the bad coin and determine whether it is heavier or lighter than the others using only a pan balance? Prove your answer.

Represent the expression as a binary tree and write the prefix and postfix forms of the expression. $$ ((A-C) * D) /(A+(B+D)) $$

True or false? Let \(T\) be a binary tree. If for every vertex \(v\) in \(T\) the data item in \(v\) is greater than the data item in the left child of \(v\) and the data item in \(v\) is less than the data item in the right child of \(v,\) then \(T\) is a binary search tree. Explain.

Evaluate each vertex in each game tree. The values of the terminal vertices are given.