| |
| • | Some arguments are small-range by virtue of being in small domains,
e.g. 1- and 2-byte integers
|
| • | Can you avoid initializing the table? |
| • x i. y (x⍳y) |
| • x and y are 2-byte ints |
| • #x and #y are small relative to the table size (65536) |
|
Answer: Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley, 1974; Exercise 2.12
[Spoiler Alert!]
Develop a technique to initialize an entry of a matrix to zero the first time it is accessed,
thereby eliminating the O(‖V‖2) time to initialize an adjacency matrix.
[Hint: Maintain a pointer in each initialized entry to a back pointer on a stack.
Each time an entry is accessed, verify that the contents are not random by making sure the pointer
in that entry points to the active region on the stack and that the back pointer points to the entry.]
|
|