Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Exercises

1.   Determine the running times predicted by the detailed model of the computer given in Section  for each of the following program fragments:

   1. i = 0
      while i < n:
          k += 1
          i += 1

   2. i = 1
      while i < n:
          k += 1
          i = i * 2

   3. i = n - 1
      while i != 0:
          k += 1
          i = i / 2

   4. i = 0
      while i < n:
          if i % 2 == 0:
      	k += 1
          i += 1

   5. i = 0
      while i < n:
          j = 0
          while j < n:
      	k += 1
      	j += 1
          i += 1

   6. i = 0
      while i < n:
          j = i
          while j < n:
      	k += 1
      	j += 1
          i += 1

   7. i = 0
      while i < n:
          j = 0
          while j < i * i:
      	k += 1
      	j += 1
          i += 1

2. Repeat Exercise , this time using the simplified model of the computer given in Section .
3. Prove by induction the following summation formulas:
   1. 
   2. 
   3. 
4. Evaluate each of the following series summations:
   1. 
   2. 
   3. 
   4. 
5. Show that , for . Hint: Let and show that .
6. Show that . Hint: Let and show that the difference is (approximately) a geometric series summation.
7. Solve each of the following recurrences by repeated substitution:
   1. 
   2. 
   3. 
   4. 
   5. 
   6. 
   7. 

Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.