Data Structures and Algorithms with Object-Oriented Design Patterns in C++

# 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. ```for (unsigned int i = 0; i < n; ++i)
++k;```
2. ```for (unsigned int i = 1U; i < n; i *= 2U)
++k;```
3. ```for (unsigned int i = n - 1U; i != 0; i /= 2U)
++k;```
4. ```for (unsigned int i = 0; i < n; ++i)
if (i % 2 == 0)
++k;```
5. ```for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = 0; j < n; ++j)
++k;```
6. ```for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = i; j < n; ++j)
++k;```
7. ```for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = 0; j < i * i; ++j)
++k;```
2. Repeat Exercise , this time using the simplified model of the computer given in Section .
3. Prove by induction the following summation formulas:
4. Evaluate each of the following series summations:
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:

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