Exercises

1. Within a textbook, chapters cover specific topics. The information required to understand each topic is expected to have appeared before the topic appears in the book. Suppose you are given a list of topics and the other topics on which each depends. How might you select an ordering of the topics for their appearance in the book?

2. Which of these binary relations is a partial order on S?

a. "Square root of" on the set S of all real numbers greater than 1

b. "Is older than" on the set S of all your relatives

c. "Sits in front of" on the set S of all students in a class

d. "Lives diagonally across from" on the set S of all people

3. Write down the graphic representation for the binary relation R on the first 10 integers. R = (3, 2), (4, 6), (7, 6), (8, 1), (9, 7), (9, 8).

4. Write a detailed modification of the algorithm of Section 11.2 that will check if a given ranking is consistent with the given partial order.

5. Write a program to implement the refinement of Exercise 4 and determine its worst-case time and storage requirements.

6. Apply the construction-based algorithm of Section 11.3 to the following data to obtain a consistent ranking. Always select the smallest integer for output.

S = 1, 2, 3, . . . , 12

R = (3, 2), (4, 6), (7, 9), (12, 10), (5, 6), (2, 4), (8, 9), (2, 6), (3, 6), (7, 12), (3, 4), (7, 10)

7. If the second implementation of the construction-based algorithm is applied to the input of Exercise 6, what integers are in the bag after 3 is removed?

8. State clearly and concisely what purpose the bag serves in the better "bag" refinement and why it was introduced.

9. Write an expanded version of the better refinement that will output integers from the bag by selecting the smallest possible integer first.

10. What will the succ, lists and count arrays have in them after phase I, when the input pairs of the running example appear in the order 7 6, 5 3, 2 10, 6 8, 5 6, 7 3, 4 8, 7 1, 4 2?

11. What will the count, succ, and lists arrays look like after phase II as compared to after phase I?

12. Suppose the better implementation were modified so that no count array were stored in memory, and only the succ and lists arrays were available after phase I. Write a new phase II refinement under this constraint.

13. Suppose a solution to the topological sort problem had been constructed by determining what object should be at the bottom of the ranking. How would the better refinement be changed to reflect this new solution?

14. a. Suppose the bag is implemented in a separate record bag instead of using the ranking record. How must the data abstraction implementations change?

b. Suppose the output ranking is not kept in the ranking record but, instead, is simply printed. How must the program and data abstraction implementations change?

15. The function process is itself dependent on the ranking and bag implementations. Modify it so that process becomes independent of these implementations.

16. Suppose task 5b of the better refinement is further expanded to:

5b.i. For each successor of the output object, decrease its predecessor count by 1.

5b.ii. For each successor of the output object, if its predecessor count is zero, add the successor to the bag.

a. ow should the implementation of the data abstraction algorithm (on p. 503) be modified to reflect this refinement?

b. rite implementations for tasks 5b.i and 5b.ii that use traverse as a tool. This should include writing the corresponding two process functions.

c. ow will this expansion of task 5b affect the time required for the algorithm?

17. Suppose the input for Exercise 10 had the pairs below appended after 4 2. What would the graphic depictions of the successor lists be after phase I of topsort?

7 3, 5 6, 4 2, 7 3, 6 8

18. For the input of Exercise 17, what would be in the count array after phase I?

19. For the input of Exercise 17, show what will be in the count array, the successor lists, and the bag after 7 is output.

20. Take as input the Example 11.6 with pairs 10 4 and 10 1 appended after 4 2. What will the second implementation of topsort output in the rank array? What will be the value of next after phase II?