Topical Information

The purpose of this paper is to give you a chance to show your knowledge of algorithm analysis.

Paper Information

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. But DDJ is gonna charge you unless you already subscribe.)

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).