CSE 247 Module 2: Simple Data Structures


Obtaining better asymptotic performance for a list

Abstract: This course is greatly concerned with characterizing the performance of a given approach or algorithm.

In this exercise, you


Warmup procedure

Useful prepping information for this studio

Part A

Part A

Write answers to the following in the studio2.txt file of the studiowriteups folder:

What do you see in the plots for ticks and time?

How would you characterize those curves?

Based on the code you see, based on your understanding of how we are currently adding to the end of a list, and based on your work from Studio 1, why do you see the results you see for ticks and timing?

Part B

Part B

What behavior do you see now for appending n items to a list if you use a tail reference?

While we have reasoned so far only about time, if we are adding n elements to the end of a list, what is the asymptotic complexity of the additional space required when using the tail reference?

Under what conditions would you recommend using a linked list with a tail reference vs. a linked list without at tail reference?

Part C

For this part, you continue modifying only the LinkedListWithTail class.
We next look at the expense of determining the size of a list of n elements.
Part C

Why does getSize() take the ticks it does?

OK now for the fun part…
Part C, continued

How did you achieve Θ(1) performance for getSize()?

Part D

Let f(n) and g(n) be non-negative functions of n.

Try to come up with proofs of the above.

Submitting your work (read carefully)

Last modified 14:14:20 CST 01 December 2016
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 2
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

TA: Password: