Danny Tervooren

9/12/06

CS-005-1

Assignment 1

Ch 2: 4, 5, 9, 14, 17

Ch 3: 3, 9, 10, 24, 27

CH 2

4.) Get values for A and q (item cost and quantity, respectively)

If (either A=0 or q=0) then

Set the value of product to 0

Else

Set the value of count to 0

Set the value of product to 0

While (count < q) do

Set the value of product to (product + 1.06A)

Set the value of count to (count + 1)

End of loop

Print the value of product

Stop

5.)

a.) Get values for x and y

If (y = 0) then

Print “Unable to perform the division”

Else

Set the value of quotient to (x/y)

Print the value of quotient

Stop

b.) Get value for r

If (r ³ 1.0) then

Set the value of area to (πr²)

Set the value of circumference to (π2r)

Print the values of area and circumference

Else

Set the value of circumference to (π2r)

Print the value of circumference

Stop

9.) Get value for A (item cost)

If (A=0) then

Set the value of product to 0

Else

Set the value of count to 0

Set the value of product to 0

While (product < 1000) do

Set the value of product to (product + 1.06A)

Set the value of count to (count + 1)

End of loop

Print the value of product

Stop

14.)

17.)

a.) If the instruction was changed to read “If A_i ³ largest so far then…,” the algorithm would not be affected

b.) If the instruction was changed to read “If A_i < largest so far then…,” the final value of largest so far would actually be the smallest number of the list, and the opposite of the intent of the algorithm would be accomplished. With this in mind, it is essential to be sure that the correct relational operation is used in an iterative or conditional algorithm primitive.

CH 3

3.)

a.) 342/2 = 171

171/2 = 85+1

86/2 = 43

43/2 = 21+1

22/2 = 11

11/2 = 5+1

6/2 = 3

3/2 = 1+1

2/2 = 1

171+85+43+21+11+5+3+1+1 = 341 matches

b.) As each player must lose one match until one player remains without a loss, there must be 341 matches to eliminate 341 of the 342 players.

c.) The second algorithm is easier to understand, more elegantly stated, and requires far fewer steps to complete.

9.) The bubble sort algorithm in exercise 8 performs n comparisons each time it goes up or down the list, which it does n times. Thus, the number of comparisons made to complete the algorithm is n · n or n²

10.) When performing on a list that is already sorted, a bubble sort will perform fewer exchanges than selection sort because the bubble sort will not need to perform any exchanges, while the selection sort may move parts of the list into a subset to sort and then back into the main list.

24.) 1+2+3+4+5+6+7=28 comparisons to find each item in a 7-element list. The average number of comparisons would be four (28/7=4). Compared to the worst case, which requires seven comparisons, the average is three fewer comparisons required.

27.) An algorithm that does 100n² instructions becomes more efficient than one that does .001(2ⁿ) instructions when n reaches a value of 23.