coworker suggests a paycheck of 2|log2n∫+1 per splay operation instead of 3|log2 n∫+ 1, the same credit invariant as before, and a strategy of spending only 2k credits

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Homework 5, CS420, Spring 2020

1. A coworker suggests a paycheck of 2|log2n∫+1 per splay operation instead of 3|log2 n∫+ 1, the same credit invariant as before, and a strategy of spending only 2k credits from the paycheck instead of 3k if x’s credit requirement goes up by k during a rotation

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.

2. The coworker suggests a paycheck of 3|log2n∫ per splay operation instead of 3|log2 n∫+ 1, the same credit invariant as before, and a strategy of spending only 3k credits from the paycheck if x’s credit requirement goes up by k during a rotation

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.

3. Suppose a co-worker implements a pseudo-array, as I have described in lectures, using splay trees. However, when looking up an  element,  if  the  path  traversed  down  the splay tree to the position where the element is found or inserted has length at most     3|log2 n∫ + 1, she doesn’t bother to splay it.  (The only exception she makes is when  the element is required to be moved  to the root to delete it, or to split the list after          the In that case, she splays it and pays for it as we described before.)

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,

4. Consider the data structure suggested by Problem 17-2 on page 473, without sup- porting the Delete operation suggested by part

 

• Let n be the number of insertions that will take place on the data structure. This will be the largest it ever grows. Suppose you already know the largest value of n before you begin inserting

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.

• Suppose you don’t know the value of n in advance. Does the amortized O(log n) bound for insertion still apply, where you only find out what n is after the last insertion?
• Derive the big-Θ bound for the lookup operation of part b?

 

5. In our study of max flow, we have seen how to find a minimum cut separating t from

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.

6. To the operations on pseudo-arrays that I discussed in lectures, let us add a new one,

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.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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