Problem 1

There are five (5) classes presented in Chapter 2 of the textbook. Write a BRIEF summary of each class. Be sure to include the runtimes, both worst case and amortized, and any details of the implementations (actual code) that is relevant to such things as resizing or balancing.

Problem 2

Suppose that the ArrayStack resized (grew) by creating a new array of size l each time. The value of l is arbitrary but finite (and fixed). Show that the worst case of adding an element is no longer O(1). In particular, show that the cost of resizing no longer has an amortized constant cost.

Problem 3

In the DualArrayDeque class, the implementation always maintains that 3f≥b and 3b≥f. Prove that for list index i,

If 0≤i

if 34/4

Problem 4

Suppose we have a RootishArrayStack with many elements. Which block and local index within that block would list item i be when

the list index is i=47

the list index is i= your student number

Attachment:- comp2402a2_0.zip