In this exercise, you
- Set yourselves up as usual for studio, with one person having eclipse open, and others with these directions.
- In eclipse,
- right (control) click on your project name in the package explorer
- Drag down to Team
- Choose Pull
- This video is from CSE131 and it shows conceptually how to add to the end of a linked list.
- Here starts the roundtable discussion with code about how to add to the end of a list.
- The part about addLast is about 17 seconds into that clip.
- You are given this code for studio, but it's important to understand how it works.
- Sequence through clips 5 and further to see the rest of the implementation.
- The work performed here is mostly in the AddLastBase class.
- Take a look at its run method, where you'll see the code that appends n times to the end of a list.
- The AddLastNoTail extension you run here uses a list without a tail reference.
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?
- This is the only class you will modify in this exercise.
- As given to you, its behavior is identical to AddLastWithTail.
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?
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.
Have you convinced yourselves that it takes the time it should?
Part COK now for the fun part…
Why does getSize() take the ticks it does?
If you get stuck, ask your TA for a hint.
Part C, continued
How did you achieve Θ(1) performance for getSize()?
Let f(n) and g(n) be non-negative functions of n.
Recall the approach for showing that one function is Θ of another: You have two obligations here:
and you can assume that f(n) and g(n) are non-negative and that f(n)=O(g(n))
- Show ∃ c ∃ n0 | ∀ n≥n0 f(n)+g(n) ≤ g(n)
- Show ∃ c ∃ n0 | ∀ n≥n0 g(n) ≤ f(n)+g(n)
When you done with this studio, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately, but should be posted in the next day or so
This demo box is for studio 2