For reference, you can review the lecture slides on
As before, answer the following questions in the studio3.txt file in your studiowriteups folder:
- Look at the Comparable interface.
- Name three data types that could serve as T.
- Find a class there that you don't know yet, and visit it to see how it implements compareTo(…).
To find the source code, Google the name of the class along with the words source code and that should take you to a page with the Java code for that class. For example, you already know String, so you can't pick that one, but if you Googled this, and picked the top hit, it would show you the source code. From there, you can click on the compareTo method to see its code.
Part B: Discuss this among yourselves and your TA. Write your answers into studio3.txt.
Here, you are using Java's built-in LinkedList implementation. This implementation is different from what we have done in class, but you don't need to worry about how it is different. You can use its API however you want, but use one of its methods to add a new item into your list, which represents the priority queue.
There is no order here, so it doesn't matter where the new item goes.
Take a look at this source code and answer the following questions. You have to click on links to method calls to get to their source. As you go, determine whether the result of calling the method to add an object to the list takes constant time, or time that depends on the current size of the list.
From your inspection of the LinkedList
class's source code: Given a LinkedList of size n, what is the asymptotic complexity, worst-case, for performing each of the following operations?
1) Appending to the end of that list addLast(Objct)
2) Prepending to the beginning of that list addFirst(Object)
3) Inserting an element in the middle of the list add(int, Object)
And for your implementation of a PriorityQueue using the Unordered List, given n elements already in the queue, what is the asymptotic complexity, worst-case for performing each of the following operations?
Assume that the initial size of the array, established in the constructor, is sufficiently large to accommodate any number of inserts called on the class.
From your implementation of OrderedArray, what is the asymptotic complexity, worst-case, for performing each of the following operations?
1) Adding an element at the end of the array
2) Inserting an element at the beginning of the array
3) Inserting an element in the middle of the list
And for your implementation of a PriorityQueue using the Ordered Array, given n elements already in the queue, what is the asymptotic complexity, worst-case for performing each of the following operations?
Are there situations when you would want to use the OrderedArray or the UnorderedList instead of the binary heap described in class? Explain please.
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 3