DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 858

F IGURE 22.12

The program animates a linear search.

**22.17

( Closest-pair animation ) Write a program that enables the user to add/remove
points by clicking the left/right mouse button, and displays a line that connects
the pair of nearest points, as shown in Figure 22.4.

**22.18

( Binary search animation ) Write a program that animates the binary search algo-
rithm. Create an array with numbers from 1 to 20 in this order. The array ele-
ments are displayed in a histogram, as shown in Figure 22.13. You need to enter
a search key in the text field. Clicking the Step button causes the program to
perform one comparison in the algorithm. Use a light-gray color to paint the bars
for the numbers in the current search range and use a black color to paint the a bar
indicating the middle number in the search range. The Step button also freezes the
text field to prevent its value from being changed. When the algorithm is finished,
display the status in a label at the top of a border pane. Clicking the Reset button
enables a new search to start. This button also makes the text field editable.

F IGURE 22.13

The program animates a binary search.

*22.19

( Largest block ) The problem for finding a largest block is described in Pro-
gramming Exercise 8.35. Design a dynamic programming algorithm for solv-
ing this problem in O ( n 2 ) time. Write a test program that displays a 10-by-10
square matrix, as shown in Figure 22.14a. Each element in the matrix is 0 or
1, randomly generated with a click of the Refresh button. Display each number
centered in a text field. Use a text field for each entry. Allow the user to change
the entry value. Click the Find Largest Block button to find a largest square
submatrix that consists of 1s. Highlight the numbers in the block, as shown in
Figure 22.14b. See www.cs.armstrong.edu/liang/animation/FindLargestBlock.html
for an interactive test.