Recursion - Data Structures and Problem Solving Using Java - page 343

The printInt method shown in Figure 7.4 may incorrectly handle the
case where N = Long.MIN_VALUE . Explain why and fix the method.

7.22

Write a recursive method that returns the number of 1s in the binary
representation of N . Use the fact that this number equals the number
of 1s in the representation of N / 2, plus 1, if N is odd.

7.23

Implement the one comparison per level binary search recursively.

7.24

An alternate formulation of the maximum contiguous subsequence
sum solution is to recursively solve the problems for items in posi-
tions low to mid -1 and then mid +1 to high . Notice that position mid is
not included. Show how this leads to an O ( N log N ) algorithm for
the entire problem and implement the algorithm, comparing its speed
to the algorithm in the text.

7.25

The maximum contiguous subsequence sum algorithm given in
Figure 7.20 gives no indication of the actual sequence. Modify it so
that it fills static class fields seqStart and seqEnd , as in Section 5.3.

7.26

For the change-making problem, give an algorithm that computes the
number of different ways to give exactly K cents in change.

7. 2 7

The subset sum problem is as follows: Given N integers
and an integer K, is there a group of integers that sums
exactly to K? Give an O ( NK ) algorithm to solve this problem.

7.28

A 1 A 2 , , … , A N

Give an O (2 N ) algorithm for the subset sum problem described in
Exercise 7.28. ( Hint: Use recursion.)

7.29

Method allSums returns a List<Integer> containing all the possible sums
that can be formed by using any of the items in the input array at most
once. For instance, if the input contains 3, 4, 7, then allSums returns [ 0,
3, 4, 7, 7, 10, 11, 13 ]. Note that the items do not have to be returned in
any particular order, but also note that if a sum can be produced multi-
ple ways, it has to be listed multiple times. Implement allSums recur-
sively. If the input has N items, what is the size of the returned list?

7. 3 0

Write the routine with the declaration

7. 3 1

public static void permute( String str );

that prints all the permutations of the characters in the string str . If
str is "abc" , then the strings output are abc , acb , bac , bca , cab , and cba .
Use recursion.

Repeat Exercise 7.31, but have permute return a List<String> contain-
ing all the possible permutations.

7.32