11. a. Any feasible state of the board can be described by an ×binary
matrix, in which the element in the th row and th column is equal to
1 if and only if the corresponding panel is lit. Let and be such
matrices representing the initial and final (all-zeros) boards, respectively.
The impact of toggling the panel at ( )on a board represented by a
Let is the number of times the ( )panel is toggled in a solution that
transforms the board from a starting state to a final state Since the
ultimate impact of toggling this panel depends only on whether is even
orodd,wecanassumewithnolossingeneralitythat is either 0 or 1.
Then a solution to the puzzle can be expressed by the matrix equation
Note: This solution follows Eric W. Weisstein et al. “Lights Out Puzzle”
from MathWorld—A Wolfram Web Resource at http://mathworld.wolfram.com/LightsOutPuzzle.html
b. The system of linear equations for the instance in question (see part a)
is
21
Solving this system in modulo-2 arithmetic by Gaussian elimination pro-
ceedsasfollows:
⎡
⎢
⎢
⎣
11101
11011
10111
01111
⎤
⎥
⎥
⎦⎡
⎢
⎢
⎣
11101
00110
01010
01111
⎤
⎥
⎥
⎦⎡
⎢
⎢
⎣
11101
01010
00110
01111
⎤
⎥
⎥
⎦
22
Exercises 6.3
1. Which of the following binary trees are AVL trees?
5
3
6
5
4
6
5
3
6
3. Draw diagrams of the single L-rotation and of the double RL–rotation in
their general form.
4. For each of the following lists, construct an AVL tree by inserting their
elements successively, starting with the empty tree.
6. Write a program for constructing an AVL tree for a given list of distinct
integers.
7.a. Constructa2–3treeforthelistC,O,M,P,U,T,I,N,G.Usethe
alphabetical order of the letters and insert them successively starting with
the empty tree.
23
8. Let and 2–3be, respectively, a classical binary search tree and a 2-3
tree constructed for the same list of keys inserted in the corresponding
trees in the same order. True or false: Searching for the same key in 2–3
always takes fewer or the same number of key comparisons as searching
in ?
Hints to Exercises 6.3
1. Use the definition of AVL trees. Do not forget that an AVL tree is a
special case of a binary search tree.
5. a. An efficient algorithm immediately follows from the definition of the
binary search tree of which the AVL tree is a special case.
b. The correct answer is opposite to the one that immediately comes
to mind.
Solutions to Exercises 6.3
1. Only (a) is an AVL tree; (b) has a node (in fact, there are two of them:
6).
2. a . Here are all the binary trees with nodes (for =1234and 5)
that satisfy the balance requirement of AVL trees.
n = 1 n = 2 n = 3
26
b. A minimal AVL tree (i.e., a tree with the smallest number of nodes) of
height 4 must have its left and right subtrees being minimal AVL trees of
heights3and2. Followingthesamerecursivelogicfurther,wewillfind,
as one of the possible examples, the following tree with 12 nodes built
bottom up:
h = 0
h =1
27
3. a. Here is a diagram of the single L-rotation in its general form:
single L-rotation
b. Here is a diagram of the double RL-rotation in its general form:
r
double RL-rotation
v
28
4. a.ConstructanAVLtreeforthelist1,2,3,4,5,6.
1
2
0
1 1
-2
2
-1
3
0
>
2
0
3
0
1
0
L(1)
-10
2
-1
3
-1
1
0
4
0
2
-2
4
-1
1
5
-1
3
0
6
0
0
>
L(2)
4
0
5
-1
2
0
6
0
1
0
3
0
b. Construct an AVL tree for the list 6, 5, 4, 3, 2, 1.
6
5
0
6
1
0
6
5
1
2
4
0
R(6)>
5
4
0
0
6
0
5
4
1
0
6
0
3
0
29
c.ConstructanAVLtreeforthelist3,6,5,1,2,4.
3
6
0
3 3
-2
6
1
5
0
>
5
0
6
0
3
0
RL(3)
-1
5
1
6
3
1
1
0
0
5. a. The simple and efficient algorithm is based on the fact that the smallest
and largest keys in a binary search tree are in the leftmost and rightmost
nodes of the tree, respectively. Therefore, the smallest key can be found
by starting at the root and following the chain of left pointers until a node
with the null left pointer is reached: its key is the smallest one in the tree.
3
8
13
6. n/a
7. a.Constructa2–3treeforthelistC,O,M,P,U,T,I,N,G.
C>
M
O
C
C, O C, M, O
b. The largest number of key comparisons in a successful search will be
in the searches for O and U; it will be equal to 4. The average number
of key comparisons will be given by the following expression:
31
8. False. Consider the list B, A. Searching for B in the binary search tree
9. The smallest and largest keys in a 2-3 tree are the first key in the leftmost
leaf and the second key in the rightmost leaf, respectively. So searching
10. n/a
32
Exercises 6.4
1. a. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by the bottom-up algo-
rithm.
2. Outline an algorithm for checking whether an array [1]is a heap and
determine its time efficiency.
3. a. Find the minimum and the maximum number of keys that a heap of
height can contain.
5. a. Design an efficient algorithm for finding and deleting an element of the
smallest value in a heap and determine its time efficiency.
6. Indicate the time efficiency classes of the three main operations of the
priority queue implemented as
7. Sort the following lists by heapsort by using the array representation of
heaps.
8. Is heapsort a stable sorting algorithm?
11. Implement three advanced sorting algorithms–mergesort, quicksort, and
heapsort–in the language of your choice and investigate their performance
on arrays of sizes =10
2103104105and 106For each of these sizes
consider:
12. Spaghetti sort Imagine a handful of uncooked spaghetti, individual rods
whose lengths represent numbers that need to be sorted.
Hints to Exercises 6.4
1. a. Trace the two algorithms outlined in the text on the inputs given.
2. For a heap represented by an array, only the parental dominance require-
ment needs to be checked.
3. a. What structure does a complete tree of height with the maximum
number of nodes have? What about a complete tree with the minimum
number of nodes?
5. a. Where in a heap should one look for its smallest element?
b. Deleting an arbitrary element of a heap can be done by generalizing
the algorithm for deleting its root.
6. Fill in a table with the time efficiency classes of efficient implementations
of the three operations: finding the largest element, finding and deleting
the largest element, and adding a new element.
10. This algorithm is less efficient than heapsort because it uses the array
rather than the heap to implement the priority queue.
35
Solutions to Exercises 6.4
1.a. Constructingaheapforthelist1,8,6,5,3,7,4bythebottom–up
algorithm (a root of a subtree being heapified is shown in bold):
1865374 ⇒1875364
1875364
2. For =12 b2ccheck whether
[]≥max{[2][2+1]}
3. a. A complete binary tree of height with the minimum number of nodes
has the maximum number of nodes on levels 0 through −1and one node
on the last level. The total number of nodes in such a tree is
−1
X
number of nodes in such a tree is
b. The results established in part (a) imply that for any heap with
nodes and height
2≤2+1
4. We are asked to prove that P−1
=0 2(−)2=2(−log2(+1)) where
=2
+1 −1
5. a. The parental dominance requirement implies that we can always find
the smallest element of a heap [1]among its leaf positions, i.e., among
[b2c+1] [](One can easily prove this assertion by contradic-
37
6. The entries in the table are the efficiency classes for the tree operations
of the priority queue ADT: find the value of the largest element, find and
delete the largest element, and add a new element of value :
7. a. Sort 1, 2, 3, 4, 5 by heapsort
Heap Construction
12345
Maximum Deletions
54312
38
Heap Construction
54321
54321
Maximum Deletions
54321
14325
c. Sort S, O, R, T, I, N, G (in alphabetic order) by heapsort
Heap Construction
1234567
SORTING
Maximum Deletions
1234567
TSROING
8. Heapsort is not stable. For example, it sorts 10,1
00 into 100,1
0
9. If the heap is thought of as a tree, heapsort should be considered a
10. The answer is selection sort. Note that selection sort is less efficient