Java Reference
In-Depth Information
valuedepth
5 2
20 0
30 0
2 0
25 1
26 3
31 0
16.7 If we had a linked list that would never be modified, we can use a simpler
approach than the Skip List to speed access. The concept would remain the
same in that we add additional pointers to list nodes for efficient access to the
ith element. How can we add a second pointer to each element of a singly
linked list to allow access to an arbitrary element in O(log n) time?
16.8 What is the expected (average) number of pointers for a Skip List node?
16.9 Write a function to remove a node with given value from a Skip List.
16.10 Write a function to find the ith node on a Skip List.
16.6
Projects
16.1 Complete the implementation of the Skip List-based dictionary begun in Sec-
tion 16.2.2.
16.2 Implement both a standard (n
3
) matrix multiplication algorithm and Stras-
sen's matrix multiplication algorithm (see Exercise 14.16.3.3). Using empir-
ical testing, try to estimate the constant factors for the runtime equations of
the two algorithms. How big must n be before Strassen's algorithm becomes
more efficient than the standard algorithm?
