Announcements

Exam today at 4-6 PM.

• (unless you’re doing a makeup of some kind)

​

datastructur.es

datastructur.es

CS61B

• Lecture 31: Ask me stuff

Review Questions

Applications of pre-order traversal of a tree:

• Directory listings.
• Any time you want to traverse and tree and don’t really care which traversal.

​

Disjoint sets / dynamic connectivity:

• Interface with two operations:
• Connect(a, b)
• isConnected(a, b)
• Four implementations of this interface: Quick Find, Quick Union, Weighted Quick Union, and WQUwithPathCompression
• The first three were just to come up with a basic idea and make improvements.
• �

Review Questions

Disjoint sets / dynamic connectivity, performance:

• What are height constraints of weighted quick union:
• After N calls to connect, the max height is Theta(log N).
• We did not prove this, but there is a nice proof in the study guide. It’s not worth going through right now, I think.

​

Simple way of finding amortized runtime.

• What is amortized runtime? After making Z calls to a method, we want to know the average (a.k.a. amortized) time per call.
• Seen two amortized runtime examples so far.
• Resizing arrays.
• MinPQs using an array based representation of a tree.
• Heap put with no resize, what is the worst case runtime as a function of N? Theta(log N)
• Heap put (single call) if we have resizing, what is the worst case runtime as a fucntion of N? Theta(N)

Review Questions

Simple way of finding amortized runtime.

• What is amortized runtime? After making Z calls to a method, we want to know the average (a.k.a. amortized) time per call.
• Seen two amortized runtime examples so far.
• Resizing arrays.
• MinPQs using an array based representation of a tree.
• Scenario 1: Heap put with no resize, what is the worst case runtime as a function of N? Theta(log N) ← THIS HAPPENS WAY MORE OFTEN.
• Scenario 2: Heap put (single call) if we have resizing, what is the worst case runtime as a fucntion of N? Theta(N) ← Resizing is very rare, and gets rarer as N grows (gets exponentially rare).
• What is the average time per call if we make N insertions into a heap, with some of them involving resizing (if we double when the array gets full)? Theta(log N)
• The real proof comes from making one of those charts from class where we write in the average time per op, and show that with a ”log(N) rate of deposits, we can cover the expensive operations”.

Review Questions

Simple way of finding amortized runtime.

• What is amortized runtime? After making Z calls to a method, we want to know the average (a.k.a. amortized) time per call.
• Seen two amortized runtime examples so far.
• Resizing arrays.
• MinPQs using an array based representation of a tree where we resize by ADDING 10 to our size, what happens?
• Scenario 1: Heap put with no resize, what is the worst case runtime as a function of N? Theta(log N): Happens 9/10 times.
• Scenario 2: Heap put (single call) if we have resizing, what is the worst case runtime as a fucntion of N? Theta(N), happens 1/10 times.
• Average runtime is Theta(N). Argument is: 1/10 calls to put is Theta(N) time, so the runtime for a whole lot of calls will also be Theta(N).

Review Questions

Self-Balancing trees, what types have we seen?

• 2-3 Trees [medium to maintain]
• 2-3-4 Trees [medium]
• 2-3-... : B-Trees [medium]
• Left leaning red black tree [medium to hard], which is really just what in disguise?
• 2-3 tree.
• Arguable:
• Weighted Quick Union: Sure, seems self-balancing. [fairly easy]
• Heap: Self-balancing. [fairly easy]

​

One thing NOT in scope of midterm is how to insert/rotate/etc. Natively with LLRBs.

​

Review Questions

Height of an LLRB, how is it defined?

• An LLRB is a balanced search tree. The only difference is:
• When you insert, you perform some sequence of “rotations” that keep the height under control.
• Specifically, there is a constraint that the number of “black” links form the root to null is the SAME for every path to null.
• An LLRB’s height is simply the length of the longest path from the root to any leaf.
• So in the worst case, if we never have consecutive red links AND the path to any node is B black links, the height of an LLRB in the worst case is, in terms of B: Probably it’s 2B+1, see the red/black/red example.
• By isometry with 2-3 tree, we know that B = Theta(Log N), the height of an LLRB is Theta(Log N) as well.
• Best case for an LLRB in Theta is also Theta(Log N). Exact is a little trickier.

Review Questions

Could you have:

• Root node, red link, then black link, then a red link. In that case we have B = 1, height = 3. So it’s actually 2B + 1. But in the LARGE scale, 2B + 1 → 2B
• So tehcnicalllllly if you were asked about exact heights in this specific manner, that’s how it would go.

​

• If we convert the red/black/red example into a 2-3 tree.

​

@

#

$

%

&

^

# @

$

$

& %

Review Questions

Bits in general, what should you know:

• How positive integers in Java are represented. 32 bit binary.

​

What you don’t need to know:

• Bitwise-AND, bitwise-OR, XOR & | ^
• How negative numbers are represented in Java, EXCEPT that we can make a number not negative with & 0x7FFFFFFF which somehow makest he number positive but we don’t really care how. This is from HW4.

​

�

Review Questions

When doing DFS on a graph, if we don’t get to all the components, do we restart?

• A case where we want to restart:
• Topological sort.,
• A case where we don’t restart:
• Has path to.

​

If a worksheet or problem ever just says “run DFS”, it is ambiguous. If somebody wants to assign a score to you, they were assuming some specific context not given on the page.

​

​

​

Review Questions

How do you identify if a weighted quick union tree is valid?

• You could specifically train your brain to do this. Given the “axioms” of the class, there are little “rules of thumb” you could derive. In the Princeton course that I used to teach, there were non-programming homeworks taht specifically led you to derive these rules of thumb, and thus they popped up on exams a lot, particularly as Cish to B level problems.
• In our course they’d be considered “harder” because we haven’t given you the homework to learn those rules of thumb.
• If you have a tree that is SUPER spindly, and it claims to be a weighted quick union, what can you say? It is wrong. There turns out to be an EXACT bound, something like > lg N or >= lg N.
• Another red flag: There is a cycle in the tree, that’s not good. Nobody is it’s own parent in WQU.

​

Review Questions

How would we convert a BST into a heap.

• Is this in general possible? It’s always possible, because given any sequence of values without duplicates, we could build the heap.
• Easy way: Just collect all the items in the BST and insert into a heap.
• Traversing a BST: Theta(N) time
• Inserting N items into a heap in the worst case: Theta(N log N)
• It might be faster to cleverly insert into the heap so that you never need to sink or swim.
• If we insert in increasing order starting from the minimum, we can insert all the items into a heap in Theta(N) time.
• Can we get the items from a BST in increasing order in theta(N) time? Yes, do an in-order traversal.
• Building a heap on the side takes Theta(N) space
• ​

Review Questions

How would we convert a BST into a heap in constant space.

• One of the trickiest parts of this is that a BST is not necessarily complete, so we’re going to need to do some rotations.
• Crude algorithm:
• TASK 1: Rotate the tree until it is complete, ignoring the heap ordered property.
• TASK 2: Then sink in some nice sequence (reverse level order is fastest, we’ll see why next week or so).

Review Questions

WQU or a Quick Union and you’re implementing it with an array under the hood, how do you store multiple trees?

• The concern is that not everything is connected, so it seems like we have a “forest” not a “tree”.
• Example:
• Int[] parent = new int[5];
• Parent[0] = 1
• Parent[3] = 2
• In this example, there are three trees, the tree with 0 and 1, the tree with 2 and 3, and the tree of 4 all by itself.
• ​