The purpose of this paper is to give you a chance to show your knowledge of algorithm analysis.
Get a copy of the Dr. Dobb's Journal article about Mark Sams' interesting SquareList data structure (May 2003 issue; p37-40). (I'll make you a copy or you can try to find it online.)
After reading the article and studying the code (which is free online with a Basic registration), perform your own (reasonably) detailed analysis of insertion, removal, and retrieval of items from the SquareList data structure.
Also analyze the space consumption (assume a pointer size of 4 bytes). How much extra space does this data structure take beyond that required for the data it stores? (Hint: How many bytes of data are stored in each node?)
All of your analyses should involve (reasonable) mathematical rigor. (See the linear search example and the Big-O notes for examples of the 'rigor' to which I'm referring.)
This assignment is (Level 4).
Add (Level 1) to validate the timing information given in Table 2 of the article (p39).
Add (Level 1) to verify your analysis using the methods described in your book (section 6.7).