Hello World - Spring 2007

Homework 4

Attempt by: Monday, February 12
Due by: Thursday, February 15

*** Deadline extended to Monday, February 19 ***

Reading

• Reread Chapter 3 of the textbook.

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 page 687, but don't look at the answers until you have tried working through them on your own.

• Problem 1 on page 98
• Problems 1-4 on page 105
• Problems 1-2 on page 111

Problems To Hand In

1. From the textbook, Chapter 3:

   • exercise 2 (page 120)
   • exercises 8, 9, and 10 (page 121)
   • exercises 13 and 14 (page 121)
   • exercise 18 (page 122)
   • exercises 19 and 20 (page 122)
   • exercise 31 (page 123)

2. Consider the following algorithm:

     Input a list of n values V1, V2, ... Vn
     Set i to 1
     While i < n and Vi < Vn do
        Set i to i + 1
     (End of loop)
     Set x to Vn 
     Set j to n 
     While j > i do
        Set Vj to Vj-1
        Set j to j - 1
     (End of loop)
     Set Vi to x
   

   1. Show what this algorithm does given the following input list:

        3, 5, 24, 7, 9 (n = 5)
      

   2. How many set instructions are executed in the best and worst case, in terms of n?

   3. What is this algorithm's order of magnitude worst-case complexity?