308-250A Introduction to Computer Science 
Homework 1 Due: Friday September 24, 1999


For this assignment you need Chapter 7 of Weiss, "Data Structures and Problem Solving using Java", available free at COPI-EUS at the entrance to McConnell Engineering

1. Write a recursive function that returns the number of 1's in the binary representation of an integer n. Use the fact that this is equal to the number of 1's in the representation of n/2, plus 1, if n is odd. Your code should be modelled after examples in the text such as Figures 7.1 and 7.2.
 

2. (a) For the code below, give a trace for the execution of the function when called with the parameters
a=0,b=1,c=1,d=1,n=5. Show the value of the parameters a,b,c,d each time the function f is called, and show the output as it is produced. Your trace will be a tree (see eg., Figure 7.7, p. 185).
(b) What does the program do in general, when called with a=0,b=1,c=1,d=1 and any positive integer n? 

public static void f(int a, int b, int c, int d, int n)
{
    if (b+d <= n) {
        f(a, b, a+c, b+d, n);
        f(a+c, b+d, c, d, n);
    } else {
        System.out.println(a + "/" + b);
    }
}

 

3. Trace the code for function power in Figure 7.14 (P. 191) as it computes 2^109 mod 11, ie. with parameters x=2, n=109, and p=11. For each recursive call, show the values of the parameters x,n,p and give the value of tmp returned in each case.

Assignments are due before 5pm on the due date, in the box marked 250, first floor of McConnell Engineering, near the elevators. No late assignments.