Hello World - Spring 2007

Homework 3

Reading

• For Monday: read pages 80-98 of the textbook
• For Thursday: read pages 99-119

Practice Problems (not to turn in)

The following problems will give you extra practice with algorithms, and are strongly recommended, but you don't need to turn them in. Solutions are given on pages 685-687, but don't look at the answers until you have tried working through them on your own.

• Problems 1-3 on page 66
• Problems 2-4 on page 73
• Problems 1-3 on page 84
• Problem 1 on page 88
• Problem 1 on page 94

Problems To Hand In

1. Consider the following algorithm:

   1. Get a list of m elements E1 E2 ... Em 
   2. Set value of i to 1
   3. Set value of j to m
   4. While i < j do
   5.    Exchange element at position i with element at position j
   6.    Add 1 to i
   7.    Subtract 1 from j
      (End of the loop)
   

   1. What does the resulting list look like after this algorithm is executed given the following list of letters as input?
      U, V, A, J, E, D   (m = 6)

   2. In a clear and concise sentence explain what this algorithm does.

   3. In the general case, how many times does step 5 get executed, in terms of m?

2. From the textbook, Chapter 2 (page 76): exercises 16 and 17

3. From the textbook, Chapter 2 (page 76): exercise 19

4. From the textbook, Chapter 2 (page 76): exercise 23

5. From the textbook, Chapter 3 (page 121): exercise 12a