Weiss Exercise Conversion (C -> C++)

Differences Between Exercises in
Data Structures and Algorithm Analysis in C, 2nd edition and
Data Structures and Algorithm Analysis in C++, 2nd edition,
both by Mark Allen Weiss, published by Addison Wesley

This list describes differences in the exercises between the C and C++ versions of Mark Allen Weiss' book. The list is intended to be useful for students wishing to use the C++ book for a course designed for the C book. Exercises in the C book but not in the C++ book are reproduced here. However, exercises in the C++ book but not in the C book are omitted, due to their number and language specific nature.

This list compiled by Dan Sanderson, April 1999. The list has been made publicly available as a resource for others; the author takes no responsibility for any mistakes that it may contain.

Chapter 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12

Chapter 1

  C     C++
 1.1    1.1
 1.2    1.2
 1.3    1.3
 1.4    1.4
 1.5    1.7
 1.6    1.8
 1.7    1.9
 1.8    1.10
 1.9    1.11
 1.10   1.12

Chapter 2

  C     C++
 2.1    2.1
 2.2    2.2
 2.3    2.3
 2.4    2.4
 2.5    2.5
 2.6    2.7
 2.7    2.8
 2.8    2.9
 2.9    2.13
 2.10   2.14
 2.11   2.15
 2.12   2.17
 2.13   2.20
 2.14   2.21
 2.15   2.22
 2.16   2.23
 2.17   2.24
 2.18   2.25
 2.19   2.26
 2.20   2.29
 2.21   2.30
 2.22   2.31
 2.23   2.32
 2.24   2.33
 2.25   2.34

Chapter 3

  C     C++
 3.1    --

Write a program to print out the elements of a singly linked list.

 3.2    3.1
 3.3    3.2
 3.4    3.9
 3.5    3.10
 3.6    3.11
 3.7    3.12
 3.8    3.13
 3.9    3.14
 3.10   3.15
 3.11   3.16
 3.12   3.17
 3.13   3.18
 3.14   --

Write a program to read a graph into adjacency lists using:
Linked lists.
Cursors.

 3.15   3.19
 3.16   --

Suppose we have an array-based list A[0..N - 1] and we want to delete all duplicates. LastPosition is initially N - 1, but gets smaller as elements are deleted. Consider the pseudocode program fragment [below]. The procedure Delete deletes the elements in position j and collapses the list.
     /* 1*/  for( i = 0; i < LastPosition; i++ )
             {
     /* 2*/      j = i + 1;
     /* 3*/      while( j < LastPosition )
     /* 4*/          if( A[ i ] == A[ j ] )
     /* 5*/              Delete( j );
                     else
     /* 6*/              j++;
             }
Explain how this procedure works.
Rewrite this procedure using general list operations.
(*) Using a standard array implementation, what is the running time of this procedure?
What is the running time using a linked list implementation?
(*) Give an algorithm to solve this problem in O(N logN) time.
(**) Prove that any algorithm to solve this problem requires Omega(N log N) comparisons if only the comparisons are used. (Hint: Look to Chapter 7.)
(*) Prove that if we allow operations besides comparisons, and the keys are real numbers, then we can solve the problem without using comparisons between elements.

 3.17   3.20
 3.18   3.21
 3.19   3.22
 3.20   3.23
 3.21   3.24
 3.22   3.25
 3.23   3.26
 3.24   3.27
 3.25   --

Write the routines to implement queues using:
Linked lists
Arrays

 3.26   3.28

Chapter 4

Write routines to implement the basic binary search tree operations.

 4.11   4.11
 4.12   4.14
 4.13   4.15
 4.14   4.17
 4.15   4.18
 4.16   4.19
 4.17   4.20
 4.18   4.21
 4.19   4.23
 4.20   4.24
 4.21   4.25
 4.22   4.26
 4.23   4.27
 4.24   4.28
 4.25   --

Nodes 1 througn N = 1024 form a splay tree of left children.
What is the internal path length of the tree (exactly)?
(*) Calculate the internal path length after each of Find(1), Find(2), Find(3), Find(4), Find(5), Find(6).
(*) If the sequence of successive Finds is continued, when is the internal path length minimized?

 4.26   4.29
 4.27   4.30
 4.28   4.31
 4.29   4.34
 4.30   4.35
 4.31   4.36
 4.32   4.37
 4.33   4.38
 4.34   4.39
 4.35   4.40
 4.36   --

Show the result of inserting the following keys into an initially empty 2-3 tree: 3, 1, 4, 5, 9, 2, 6, 8, 7, 0.
Show the result of deleting 0 and then 9 from the 2-3 tree created in part (a).

 4.37   4.41
 4.38   4.42
 4.39   4.43
 4.40   4.44
 4.41   4.45
 4.42   4.46
 4.43   4.47
 4.44   4.48
 4.45   4.49
 4.46   --

A binary search tree presupposes that searching is based on only one key per record. Suppose we would like to be able to perform searching based on either of two keys, Key₁ or Key₂.
One method is to build two separate binary search trees. How many extra pointers does this require?
An alternative method is a 2-d tree. A 2-d tree is similar to a binary search tree, except that branching at even levels is done with respect to Key₁, and branching at odd levels is done with Key₂. [The figure below] shows a 2-d tree, with the first and last names as keys, for post-WWII presidents. The presidents' names were inserted chronologically (Truman, Eisenhower, Kennedy, Johnson, Nixon, Ford, Carter, Reagan, Bush, Clinton). Write a routine to perform insertion into a 2-d tree.
                           Harry Truman
                        ________/\________
         Dwight Eisenhower             John Kennedy
           _____/\_____                   _____/\_____
     George Bush   Gerald Ford    Lyndon Johnson   Richard Nixon
      _____/                     _____/              \_____
   Bill Clinton               Jimmy Carter             Ronald Reagan
Write an efficient procedure that prints all records in the tree that simultaneously satisfy the constraints Low₁ <= Key₁ <= High₁, and Low₂ <= Key₂ <= High₂.

Chapter 5

  C     C++
 5.1    5.1
 5.2    5.2
 5.3    5.3
 5.4    5.4
 5.5    --

An alternate collision resolution strategy is to define a sequence, F(i) = r_i, where r₀ = 0 and r₁, r₂, ..., r_N is a random permutation of the first N integers (each integer appears exactly once).
Prove that under this strategy, if the table is not full, then the collision can always be resolved.
Would this strategy be expected to eliminate clustering?
If the load factor of the table is lambda, what is the expected time to perform an insert?
If the load factor of the table is lambda, what is the expected time for a successful search?
Give an efficient algorithm (theoretically as well as practically) to generate the random sequence. Explain why the rules for choosing P are important.

 5.6    5.8
 5.7    5.9
 5.8    5.10
 5.9    5.11
 5.10   5.12
 5.11   5.13
 5.12   5.14
 5.13   5.15
 5.14   5.19
 5.15   5.20

Chapter 6

  C     C++
 6.1    --

Suppose that we replace the DeleteMin function with FindMin. Can both Insert and FindMin be implemented in constant time?

 6.2    6.2
 6.3    6.3
 6.4    --

Write the routines to do a percolate up and a percolate down in a binary heap.

 6.5    --

Write and test a program that performs the operations Insert, DeleteMin, BuildHeap, FindMin, DecreaseKey, Delete, and IncreaseKey in a binary heap.

 6.6    6.6
 6.7    6.7
 6.8    6.9
 6.9    6.10
 6.10   6.11
 6.11   6.12
 6.12   6.13
 6.13   6.14
 6.14   6.15
 6.15   6.18
 6.16   6.19
 6.17   6.20
 6.18   6.21
 6.19   6.22
 6.20   6.23
 6.21   6.24
 6.22   6.25
 6.23   6.26
 6.24   6.27
 6.25   6.28
 6.26   6.29
 6.27   6.30
 6.28   6.31
 6.29   6.32
 6.30   6.33
 6.31   6.34
 6.32   6.35*

[The C book has a third part to this exercise, renumbering them as follows:]

  .a     --

What happens when the call Merge(H,H) is made? Modify the code to fix this problem.

  .b     .a
  .c     .b
 6.33   6.36
 6.34   6.37
 6.35   6.38
 6.36   6.39

Chapter 7

  C     C++
 7.1    7.1
 7.2    7.2
 7.3    7.3
 7.4    7.4
 7.5    7.5
 7.6    7.6
 7.7    7.7
 7.8    7.8
 7.9    7.9
 7.10   7.10
 7.11   7.11
 7.12   7.12*

[The C book has a second part to this exercise:]
b. (*) Prove that the worst case bound for heapsort is achievable.

 7.13   7.15
 7.14   7.16
 7.15   7.17
 7.16   7.18
 7.17   7.19
 7.18   7.20
 7.19   7.21
 7.20   7.22
 7.21   7.23
 7.22   7.24
 7.23   7.29
 7.24   7.30
 7.25   7.31
 7.26   7.32
 7.27   7.33
 7.28   7.34
 7.29   7.35
 7.30   --

Prove that sorting N elements with integer keys in the range of 1 <= Key <= M takes O(M+N) time using bucket sort.

 7.31   7.39
 7.32   7.40
 7.33   7.41
 7.34   7.42
 7.35   7.43
 7.36   7.44
 7.37   7.45
 7.38   7.46
 7.39   7.47
 7.40   7.51
 7.41   7.52
 7.42   7.53
 7.43   --

ANSI C requires the routine qsort to be present in C libraries. qsort is typically implemented by quicksort (but this is not required). Experiment with various inputs to see if qsort can be driven to quadratic behavior. Try random 0s and 1s.

Chapter 8

  C     C++
 8.1    8.1
 8.2    8.2
 8.3    8.3
 8.4    8.4
 8.5    8.5
 8.6    --

Show the operation of the program in Section 8.7 on the following graph: (1,2), (3,4), (3,6), (5,7), (4,6), (2,4), (8,9), (5,8). What are the connected components?

 8.7    --

Write a program to implement the algorithm in Section 8.7.

 8.8    8.8
 8.9    8.9
 8.10   8.10
 8.11   8.11
 8.12   8.12
 8.13   8.13
 8.14   8.14

Chapter 9

  C     C++
 9.1    9.1
 9.2    9.2
 9.3    9.3
 9.4    9.4
 9.5    9.5
 9.6    9.6
 9.7    9.7
 9.8    9.8
 9.9    9.9
 9.10   9.10
 9.11   9.11
 9.12   9.12
 9.13   9.13
 9.14   9.14
 9.15   9.15
 9.16   9.16
 9.17   9.17
 9.18   9.18
 9.19   9.19
 9.20   9.20
 9.21   9.21
 9.22   9.22
 9.23   9.23
 9.24   9.24
 9.25   9.25
 9.26   9.26
 9.27   9.27
 9.28   9.28
 9.29   9.29
 9.30   9.30
 9.31   9.31
 9.32   9.32
 9.33   9.33
 9.34   9.34
 9.35   9.35
 9.36   9.36
 9.37   9.37
 9.38   9.38
 9.39   9.54
 9.40   9.55
 9.41   9.56

Chapter 10

  C     C++
 10.1   10.1
 10.2   10.2
 10.3   10.3
 10.4   10.4
 10.5   10.5
 10.6   10.6
 10.7   10.7
 10.8   10.8
 10.9   10.9
 10.10  10.10
 10.11  10.11
 10.12  10.12
 10.13  10.13
 10.14  10.14
 10.15  10.15
 10.16  10.16
 10.17  10.17
 10.18  10.18
 10.19  10.19
 10.20  10.20
 10.21  10.21
 10.22  10.22
 10.23  10.23
 10.24  10.24
 10.25  10.25
 10.26  10.26
 10.27  10.27
 10.28  10.28
 10.29  10.29
 10.30  10.30
 10.31  10.31
 10.32  10.32
 10.33  10.33
 10.34  10.34
 10.35  --

[See 10.38 below.]

 10.36  10.36
 10.37  10.37
 10.38  --

[The C++ book has combined the C book's exercises 10.35 and 10.38 into one two-part exercise, renumbered as follows:]

   .35  .38.a
   .38  .38.b

 10.39  10.39
 10.40  10.40
 10.41  10.41
 10.42  10.42
 10.43  10.43
 10.44  10.44
 10.45  10.45
 10.46  10.46
 10.47  10.47
 10.48  10.48
 10.49  10.49
 10.50  10.50
 10.51  10.51
 10.52  10.52
 10.53  10.53
 10.54  10.54
 10.55  10.55
 10.56  10.56
 10.57  10.57
 10.58  10.58
 10.59  10.59
 10.60  10.60

Chapter 11

All exercises in the C book for this chapter are numbered identically in the C++ book.

  C     C++
 11.1   11.1
 11.2   11.2
 11.3   11.3
 11.4   11.4
 11.5   11.5
 11.6   11.6
 11.7   11.7
 11.8   11.8
 11.9   11.9
 11.10  11.10
 11.11  11.11
 11.12  11.12
 11.13  11.13
 11.14  11.14

Chapter 12