You are probably being recorded (and transcribed)
Approximate overview
Graph.java, our class’s implementation of graphs.If you’d like to suggest token events, please let me know in advance of class.
What should I do in the ethical reuse LA?
Show that you regularly cite code you borrow.
Show that you make sure that you have permission to use the code you borrow from elsewhere.
Usually, this will be a narrative of a time you’ve used someone else’s code along with a copy of your citation and other context.
Big picture:
Our goal: Figure out how to do that (TPS)
Strategy:
java.lang.Integer.toBinaryString to convert to a series of
0’1 and 1’s. [Whoops; that’s the strategy for character to Braille]New strategy
Integer.parseIntDetails:
Can we assume the input we get from load is valid?
Yes.
Can we assume the input we get in get is valid?
No. Be prepared to throw an exception.
When are we getting MPs back?
I’m not sure. I’ve tried to find time to grade them myself, but haven’t been able to.
Will we get at least one redo opportunity?
That’s still the plan.
Will you be more generous on the MP grading (in terms of the number needed for A/B/C)?
Almost certainly.
SoLA 12 will open tonight, right?
Yes.
Will MP 11 be a group project?
No.
Will we still have at least two tries on each LA?
Yes. There are five new LAs due Monday of finals week and they will be repeated Friday of finals week.
Why didn’t you repost an LA for TOPIC?
I intended to. If you notice a missing LA, let me know asap.
Are priority queues considered FIFO just like queues? The first element to enter may not be the first one to be removed if it has a low priority. But then why is this structure considered a queue?
Welcome to the wonderful world of CS terms. Priority queues are not FIFO. They aren’t really queues. They are simply linear structures with a “highest-priority first” policy.
What are some practical use cases where the linked implementation of a priority queue would outperform the array implementation?
Presumably, if we ended up inserting things in reverse order of priority, the linked structure would win out.
In practice, we use neither a linear linked structure nor a standard array-based approach.
What are the practical scenarios where an unordered array implementation is preferred over an ordered one?
If we do many more calls to
putthanget, an unordered array is likely to be much more efficient.
How does the choice of data structure (e.g., binary heaps) improve the performance of priority queues?
We’ll cover this in class.
But if you know what a binary heap is, you should know the answer.
For an array-based implementation of priority queues, could you also store elements in descending order (highest priority to lowest priority)? Or generally, why would it be better to consider one form of ordering for either array-based or linked-based implementations as opposed to the opposite ordering?
To be discussed in class.
With priority queues, what should be done if two items are considered to have equal priority? This is only important if the objects are different. For example, what should be done if length determines priority (less is better) and “two” is put in after “one”?
They are equal priority and can therefore be returned in either order. We might try to make our priority queue more like a queue and return the first one added.
Linear structures with “highest priority first” as the policy.
void put(T val)T get() - get and remove the highest priority valueT peek() - get but not remove the highest priority valueTPS
size field)
put: Constant - O(1), unless you have to expand the array.
If we double the size of the array when we expand it, we can say
it’s “amortized O(1)” - N puts is O(N) [n constant plus one big
one], so it averages out to constant.peek: O(n) because you have to searchget: O(n) because you have to search and you also have to fill
in the hole you create (which could be O(1) if you just grab the
last element)put: Find where it belongs: O(logn) because you can use binary
search. Shifting is O(n). O(n + logn) = O(n).peek: O(1): It’s the first valueget. O(n): You can get the first value in constant time, but
you’ll then have to shift, which is O(n). Or we could use the
evil wrap-around technique from our array-based queues.put: O(n) see abovepeek: O(1) if we keep track of the size/endget: O(1), since we can just decrease the size/end by 1put: O(1): Put it at the start (or at the end if you have an end pointer)peek: O(n): You have to search for itget: O(n): You have to search for it. At least deletion is easier
than in arrays.put: O(n) because we have to look through the linked structurepeek: O(1)get: O(1) because you grab the first element and then do something
like first = first.next.put: O(n) see abovepeek: O(1) if you keep track of the last nodeget: O(n) because you have to iterate the whole damn list to get the
one before it.
O(1) if you keep track of the last node and make it doubly linked.put:get:peek:Note: Unrelated to the heap from memory management.
A (max-)heap is a binary tree with two properties:
Because our heaps are nearly complete, we know that the height is
O(log2n). If we can implement put and get in O(height), we have
a more efficient priority queue.
peek: The root has the highest priority element. O(1).
Observations for put and get:
put:
get:
Outstanding issues:
Although heaps are trees, and we generally implement trees as linked structures, we can implement heaps (and, I suppose any binary tree) as arrays.
Primary idea: Number the nodes in the tree using top-down, left-to-right, breadth-first traversal.
If we know the size, it’s easy to find the first empty space and the last full space.
How about finding children and parents.
Left child of position i:
Right child of position i
Parent of position i
Suppose you have a cool implementation of a priority queue. Can you use that priority queue to sort? You get two operations: put(val) and get(), which returns the largest value.
Heap sort
| Invariant: Heap and small | Sorted and large |
Magically turn the array into the heap
for (i = 1; i < size; i++) {
heap-up(i);
} // for
Alternately
for (i = size-1; i >= 0; i--) {
heap-down(i);
} // for