1. a. Do users of the subway system of a large city reach their destinations by a process analogous to selection or a process analogous to traversal? Why?
b. Do users of the telephone system of a large city reach their parties by a process analogous to selection or one like traversal? Why?
2. Suppose you are interested in processing English text in the following way:
a. Input is in the form of an English sentence.
b. The program is to check the sentence looking for violations of the spelling rule, "慽'" before 慹' except after 慶'." (Do not worry about exceptions such as neighbor, weigh, etc.) Would an array be a convenient data structure to use in your program, and would traversal be a relevant process?
3. Write a program to print out how many elements of an integer array (of length n) contain even integers. Did you use the process of traversal?
4. In Example 2.2 suppose the pointer array were stored in memory and there were no a itself. If you are told that a[5] and a[9] have been interchanged, then what changes would you have to make to pointer to reflect this interchange? What if a[2] and a[5] were interchanged?
5. Write a function to update the pointer array of Example 2.2 to reflect the fact that the ith and jth columns of a have been interchanged.
6. a. Suppose the cars array (Example 2.4) represents the fleet information for the cars of one rental agency. For a group of several such agencies, would the record data structure be convenient to represent all the information?
b. Assume the information is represented in an array that stores records, with each record containing all the information for a particular agency. In general, are these records fixed or variable length?
7. For Example 2.4 assume the alternate multiarray implementation. Write a function to interchange the ith and jth records.
8. Create a function that prints out the rentees of all cars that have been driven more than 50,000 miles for the multiarray implementation of Example 2.4.
9. Write a function to read in a sequence of at most twenty characters into an array. They are all digits (0, or 1, or 2, . . . , or 9) except for one character that will be a decimal point. After execution of the function the variable dp should point to the array element that contains the decimal point, and variable 1 should point to the last digit of the input sequence. The decimal point will always have at least one digit on each side.
10. Produce a function similar to that of Exercise 2.3 except that the array of integers is two-dimensional.
11. Suppose a checkerboard is represented as a two-dimensional array. Write a function that is given the current configuration of the board and the move to be made by the player whose turn it is. The function is to return the value true if the move is legal and false otherwise. (Do not forget that a move can consist of many jumps.)
12. a. Is there an analogy between tabs in your home telephone directory and pointers?
b. If a song on a tape cassette is like a record data structure type, can a particular song be indexed, or must a traverse be used to find it? How about a song on a phonograph record?
13. Explain the differences between a record stored in an array and in dynamic memory.
14. Define a function to copy the array of Example 2.5 into an array indexed by a pointer array of integers.
15. Write a function to interchange two records of the array of Example 2.5.
16. Assume the row representation for two-dimensional arrays has been extended to three-dimensional arrays. Determine the formula for the offset of a[i][j][k].
17. The array a with r rows and c columns is stored using the rowwise representation, with a[0][0] corresponding to the actual base location of a, abase. Given an integer number k (abase ?/FONT> k ?/FONT> abase + r ?/FONT> (c - 1)), write formulas that will yield the row and column of a to which actual location k corresponds. That is, if a [i] [j] is stored in k, then your formula for the row will yield i and for the column will yield j.
18. An antisymmetric array a is a square array that satisfies the condition that a[i][j] = -a[j][i] for all 0 ?/FONT> i, j < n. Hence the diagonal elements must be zero. Storing the antisymmetric array can be done just as storing the symmetric array was done, except that now the diagonal entries can be omitted, since they are known. Determine the formula for the offset of a[i] [j].
19. An array a is said to be tridiagonal if the nonzero entries of a fall along the three diagonals a[i] [i], a[i] [i+1], and a[i] [i-1], where i goes, respectively, from 0 to n - 1, 0 to n - 2, and 1 to n - 1.
a. Construct a rowwise representation of the nonzero entries of a, and find a formula for the offset of a[i] [j] in this array.
b. Construct a diagonal representation of the nonzero entries of a tridiagonal array, and find a formula for the offset of a[i] [j] in the array.
20. Write a function that takes a two-dimensional array represented in terms of p and data, as in Section 2.3.3, and changes p so that any duplicate rows of a are stored only once in data. Thus, if rows 2 and 7 are identical, the contents of p[1] and p[6] are made equal.
21. Define a function to output the n diagonal elements of the array a of Section 2.3.3 when the array is represented in terms of p and data.
22. Produce a function to print out the jth column of array a when it is represented in terms of p and data as in Section 2.3.3.
23. Write a function to interchange a[i][j] and a [j][i], for all i, j, when a is represented in terms of p and data as in Section 2.3.3.
24. Create a function that takes any array a of integers with at most twenty entries and creates a pointer array p that has in p[i] a pointer to the (i + l)th largest entry of a. Thus p[0] points to the largest entry of a.
25. Do the same as in Exercise 24, except the array a will be two-dimensional and the ith record in p must contain two pointers, one for the row and one for the column of a's ith largest entry.
26. Do Exercises 20 to 25, except use pointers and dynamic memory. Print the pointers.
27. What pairs are not stable in the example pairings?
28. Give a function to create wpairs from mpairs.
29. Write a function to create a priority array, given a pref array.
30. What function will create a pref array given a priority array?
31. a. Give a function to produce stable marriages.
b. How much time does your answer to Exercise 31a require?
32. a. Why must the algorithm to produce stable marriages terminate eventually?
b. Why does it produce stable marriages?