2023年11月25日

算法分析代写 | CS 535 Design and Analysis of Algorithms Homework 3

本次美国代写是算法分析相关的一个assignment

1. C/C++/Java instructions are fine. But do not write object-oriented additions. Do not
declare or use any class. Declare only procedures (if necessary) and explain in words what
each procedure does, and what is the use of each parameter. Feel free to use as procedures
algorithms from the textbook; indicate page and edition.

2. One instruction per line

3. Match the brackets with a horizontal line

4. Number your lines

5. Write down if your array is indexed 0 . . . n − 1 or 1 . . . n.Problem 1 When analyzing splay trees, we have defined the rank function on nodes: r(v) =
⌊lg |V (Tv)|⌋, where lg is the base 2 logarithm, and Tv is the subtree rooted at v (V and all its
descendants).

We also called r′(v) as being the rank of v after one operation – a double rotation or a single
rotation. We proved that the amortized cost of a double rotation at x does not exceed 3(r′(x)−r(x)),
and that the amortized cost of a single rotation at x does not exceed does not exceed 1+3(r′(x)−r(x)).

This problem asks to show that the +1 term for a single rotation is needed. In other words, give
an example of a binary search tree and a single rotation whose amortized cost as defined in class
(actual cost plus the sum of ranks after the operation minus the sum of ranks before the operation)
exceeds 3(r′(x) − r(x)).

As an aside (no need to turn in anything about this paragraph), with single rotations only, the
splay operations will not have amortized cost of O(lg n) each.

Problem 2 Suppose we implement the UNION-FIND Data structure with union-by-rank but no
path-compression. For every n, give an example of a sequence of operation with n MAKE-SET(),
p UNION and r FIND operations whose total running time exceeds c(n + p + r) log n) for some
constant c. We also require that each element is a parameter in UNION(,) and FIND() at most
once in this sequence.

Problem 3 We describe below a data structure that maintains the transitive closure of a directed
graph while arcs (directed edges) are added to the graph.