Homework 5, CS420, Spring 2020
Where does the strategy fail? Your answer must address the which types of rotations on page 54 and the values of k for which they fail. Justify each case where you claim it fails.
Where does the strategy fail? Your answer must address the which types of rotations on page 54 and the values of k for which they fail. Justify each case where you claim it fails.
She reasons that she can use the paycheck of 3|log2 n∫ + 1 to pay directly the cost of traversing the path if its length is bounded by this value, so there is no need to splay.
Is her analysis correct? Reason in terms of the goals we sought to achieve during each splay: not overspending our paycheck and maintaining invariants we must maintain in order to make sure that subsequent operations also do not overspend their paychecks,
Assume that you have a paycheck of |log2 n∫ credits for each insertion. You maintain a credit invariant that if an element is in an array of size 2 , then it has |log2 n∫ − i credits on it.
You need to pay for all work resulting from an insertion at the rate of O(1) per credit while maintaining the credit invariant. Explain how to do that.
Hint: Consider the running time of the merge operation from Mergesort.
s, where s and t are given.
Suppose we want to find a minimum cut separating any two vertices in the graph. One way to do this is to run the max-flow algorithm for each of the n(n − 1) ordered pairs (s, t) of vertices.
Tell how to solve the problem with O(n) calls to the max-flow algorithm.
reverse, which reverses the order of elements in it.
For instance, the following gives the elements and their indices before and after the
reverse operation on an example:
1 2 3 4 5 6 7
[3,9,1,2,5,4,6]
1 2 3 4 5 6 7
[6,4,5,2,1,9,3]
Before the reverse operation if the user asks for the element at position 2, the list returns 9. After it, it returns 4. Similarly for any other operation that indexes by position.
Here is a hint: Instead of letting each node have a left child and a right child, it has an A child and a B child. Assign an integer k(v) to each node v. If k(v) is even, then the A child of v is interpreted as the left child and the B child as the right child; if k(v) is odd, then the A child of v is interpreted as the right child and the B child as the left child.
Alternatively, let k(v) be a bit, and let the interpretation of the two children depend on whether k(v) = 0 or k(v) = 1.
All operations that traverse from the root to an element consult k(v) and use the prescribed interpretation of A and B, both otherwise work as before.
Tell how to implement the reverse operation so that it takes o(n) time, though the list still supports the operation of looking up an element by its position, changing the value of an element in a given position, deleting an element in a given position, inserting an element in a given position, and splitting and concatenating lists.
Tell what amortized bounds you can achieve. You may use any claims I have already shown in lectures to be true in deriving your bounds.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of