Java Reference
In-Depth Information
Thus, the full process for multiplying polynomials A and B using the Fourier
transform is as follows.
1. Represent an n 1-degree polynomial as 2n 1 coefficients:
[a
0
;a
1
;:::;a
n1
; 0;:::; 0]
2. Perform
FourierTransform
on the representations for A and B
3. Pairwise multiply the results to get 2n 1 values.
4. Perform the inverse
FourierTransform
to get the 2n 1 degree poly-
nomial AB.
16.4
Further Reading
For further information on Skip Lists, see “Skip Lists: A Probabilistic Alternative
to Balanced Trees” by William Pugh [Pug90].
16.5
Exercises
16.1 Solve Towers of Hanoi using a dynamic programming algorithm.
16.2 There are six possible permutations of the lines
for(intk=0;k<G.n();k++)
for(inti=0;i<G.n();i++)
for(intj=0;j<G.n();j++)
in Floyd's algorithm. Which ones give a correct algorithm?
16.3 Show the result of running Floyd's all-pairs shortest-paths algorithm on the
graph of Figure 11.26.
16.4 The implementation for Floyd's algorithm given in Section 16.1.2 is ineffi-
cient for adjacency lists because the edges are visited in a bad order when
initializing array
D
. What is the cost of of this initialization step for the adja-
cency list? How can this initialization step be revised so that it costs (jVj
2
)
in the worst case?
16.5 State the greatest possible lower bound that you can prove for the all-pairs
shortest-paths problem, and justify your answer.
16.6 Show the Skip List that results from inserting the following values. Draw
the Skip List after each insert. With each value, assume the depth of its
corresponding node is as given in the list.
