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 your code.
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
Strategy:
java.lang.Integer to do that).
java.lang.Character to do that.)Details:
What do you mean by “don’t fill in the nodes until necessary”?
Consider the call
new BitTree(3).
That could be a tree with four levels (one node at level 0, two nodes at level 1, four nodes at level 2, eight nodes at level 3).
We could build all fifteen nodes at once, but that would be wasteful. And we wouldn’t have anything to put in the leaf nodes. So we instead only add nodes when we call
set.
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: Add at the end of the array O(1), if we have enough room.
O(n) if we have to expand the array. If we double the size of the
array, it’s “amortized O(1)”.get: O(n) because you have to look at all of the elementspeek: O(n) dittoput: O(n) you have to figure out where it goes, which means
searching through all the elements. (Even if we can find the spot
in O(logn) by using binary search, it will still be O(n) to shift
values to make room for it.)get: O(n) because you’ll have to shift everything down after
removing the first element (or use that horrid “wrap-around”
strtegy we used for queues).peek: O(1) it’s at the frontput: O(n): see aboeget: O(1)peek: O(1)put: O(1): Update either the pointer to the first node or the
pointer to the last node.get: O(n) because you have to look through all of thempeek: O(n) because you have to look through all of themput: O(n) because you have to search through the list (at least
there’s no shifting)get: O(1) you can easily move front to front.next.peek: O(1) it’s at the frontput: O(n) for similar reasonsget: O(n) because we have to go through the entire list to find
the predecessor of the last nodepeek: O(1) if we keep a pointer to the last nodeput:get:peek:peek is cheap.put and
get be O(height), they will be O(log2n) operations.put: How do we add an element to the tree and then restore the
two properties? (The heap property and the nearly-complete property.)
get: After removing the top element, how do we restore the two properties?
(The heap property and the nearly-complete property.)
Side note:
Number the nodes left-to-right, breadth first, starting at 0. That gives their location in a corresponding array.
Given a node at position i,
How do we sort with a priority queue:
put is O(logn), get is O(logn)