91Ó°ÊÓ

Show all solutions to the four-queens problem.

Draw a graph having the given properties or explain why no such graph exists. Full binary tree; height \(=3\); nine terminal vertices

Show that any algorithm that finds a minimal spanning tree in \(K_{n}\), when all the weights are the same, must examine every edge in \(K_{n}\).

Find a solution to the five-queens and six-queens problems.

Show all solutions to the five-queens problem in which one queen is in the first column, second row.

Draw all nonisomorphic free trees having three vertices.

How many solutions are there to the five-queens problem?

Draw all nonisomorphic free trees having six vertices.

Show all solutions to the six-queens problem in which one queen is in row \(2,\) column \(1,\) and a second queen is in row 4 column 2

Refer to tournament sort. Tournament Sort. We are given a sequence \(s_{1}, \ldots, s_{2^{k}}\) to sort in nondecreasing order. We will build a binary tree with terminal vertices labeled \(s_{1}, \ldots, s_{2^{k}} .\) An example is shown. Working left to right, create a parent for each pair and label it with the maximum of the children. Continue in this way until you reach the root. At this point, the largest value, \(m\), has been found. To find the second-largest value, first pick a value vless than all the items in the sequence. Replace the terminal vertex w containing \(m\) with \(v\). Relabel the vertices by following the path from w to the root, as shown. At this point, the secondlargest value is found. Continue until the sequence is ordered. How many comparisons does tournament sort require to find the largest element?