Exercise 10.9

1. For the list
   
   Bat Cat Cow Dog Elk Fly Fox Gnu Hen Owl Pig Rat Yak
   
   trace the execution of a binary search as it looks for the value Man in the list. In your trace, note the bounds of the sub-array and the value in the list that is being examined on each pass. If a sub-array has no exact middle, choose the item to the immediate left of the middle.



2. Sequential search as given in the text does not require that the list of items be sorted but, if the list is sorted, then sequential search can be made more efficient. Write a method with header

   public static int seqSearchSorted (String[] list, String item)

   that uses the fact that list is sorted in ascending order to make the search more efficient. The method should, as usual, return the index in list of the first occurrence of item or -1 if item is not in the list.



3. Rewrite the binary search method of Section 10.2 so that, if there is more than one element in the list whose value is equal to item, the method returns the index of the first such element in the list.



4. Suppose that the following list of values is to be sorted into ascending order.
   

   5 1 4 8 9 6 3

   Show the list as it would appear after the first and second pass of each sort.
   
   a) selection sort    b) insertion sort    c) bubble sort



5. Suppose that the following list is to be arranged in ascending order.
   

   86 13 14 61 54 70 75 26 50 12 53 29 70 65

   Show the list as it would appear after one pass of Shellsort with k = 5.



6. Suppose that insertion sort is to be used to sort a list of n integers. Show that, in the worst case, the number of data movements required is (1/2)n² + (3/2)n - 2.



7. We might think of the process of shuffling (as used with decks of playing cards) as the opposite of sorting. To investigate shuffling, suppose that you are given an array called list of n int values. Initially, list [i] has the value i.
   
   (a) Suggest a reasonably efficient algorithm that could be used to shuffle the numbers in list.

   (b) Implement your algorithm as a Java method with heading

   public static void shuffle (int[] list)



8. Write a program that reads up to 1000 positive integers. The values are not necessarily all different and they are not in any particular order. The program should continue reading input until it has read 1000 values or it has read the sentinel value, zero. The program should then print all the distinct positive integers read (in ascending order) together with a count of the number of occurrences of each number. As an example, input of
   5 7 2 5 4 9 475 1 0
   should produce output like the following.
   
   Value Frequency
   1 1
   2 1
   4 2
   5 3
   7 2
   9 1




Projects



9. Write a program to play the following game. Begin by displaying the ten digits 0 - 9 in some random order. Then repeatedly ask the person playing the game to choose a number n, after which the computer will reverse the first n digits in the sequence. The object of the game is for the player to put all the digits in ascending order using as small a number of reversals as possible. Set up your program so that after each game it asks if the game should be repeated with the same starting sequence, played with a new starting sequence, or terminated.



10. In the card game called bridge, each of the four players is dealt thirteen cards. To help players to evaluate the worth of their hands, it is common to assign a numerical value to each hand. One widely used system assigns values as follows:
    
    • 4 points for each ace
    • 3 points for each king
    • 2 points for each queen
    • 1 point for each jack
    • 3 points for a void (no cards in a suit)
    • 2 points for a singleton (one card in a suit)
    • 1 point for a doubleton (two cards in a suit)
    
    Write a program that will read a string representing a bridge hand. The string should consist of 26 characters, two characters for each card. For each card, the first character will represent the denomination (using A for ace, K for king, Q for queen, J for jack, T for ten, and 2 to 9 for the other denominations) and the second character will represent the suit (S for spades, H for hearts, D for diamonds, and C for clubs). For example, the string
    4DTCKC5H7CQSAH4H6SJHAC9H2H
    would represent a hand containing the four of diamonds, ten of clubs, king of clubs, and so on.
    
    Your program should repeatedly ask the user if another hand should be evaluated. If so, the program should prompt the user to submit a hand, read the input, and determine whether or not the input is valid. If the input is not valid, the program should reject it and print a message. If it is valid, the program should evaluate the hand and print a display of the hand together with its value. The display should be arranged according to the following rules. Spades should be listed on the first line, hearts on the second line, diamonds on the third line, and clubs on the fourth line. Within each line, the cards of a suit should be arranged in descending order of value (ace, king, queen, jack, 10, 9, ... , 2) with each value separated by one