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.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme