Решить 3 задания Algorithms and Data Structures

Problem 1 

Consider the operations Union and Find from the Union-Find algorithm with path compression.

Suppose we have a set of n elements, which has had a series of arbitrary Unions performed on

it. Let us denote the result as T. Determine the complexity (expressed in terms of n and m) of a

sequence of m Find operations performed on T.

your upper bound should be tight, and the analysis must be done using either the

accounting method (credits) or the potential method.

Problem 2 

Suppose we need a data structure in which we can search for elements. Specifically, we need to be

able to perform operations:

Insert(A; x) adds an element x to the structure A;

Check(A; x) determines whether a given element x is in the structure A.

One way to do this is to keep an array of elements in sorted order. Constant time access allows us

to quickly search for elements using a binary search in O(log n) time. On the other side, inserting

elements is slow (O(n)) due to the requirement that the array remains sorted: when we add an

element, all the elements after it must be shifted one array index to the right.

Let us examine a better data structure that provides the same functionality: Keep a list of arrays,

numbered 0 through n, where array k is of size 2k. We will maintain the invariant that all arrays

are either empty or full, and all full arrays are sorted. To insert an element, we rst create an

array of size 1 containing only that element. Then we iterate through the list of arrays, starting

with the smallest. If the current array k is empty, we replace it with the full new array and we

are done. Otherwise, we merge array k into the new array using the standard operation Merge,

doubling its size. Then we set array k to be empty and move on to array k + 1.

Compare the time complexity of the operations Insert and Check over an ordered array data

structure and over an array of ordered arrays data structure. What is the worst case complexity

of the operation Insert into a ListOfArrays containing n elements? What is the worst case

complexity of a sequence containing m Search and n Insert operations performed on an initially

empty data structure?

your upper bound should be tight, and the analysis must be done using either the

accounting method (credits) or the potential method.

Problem 3 

The element of rank i in an array A[1; : : : ; n] of numbers is the i-th smallest element of A.

Design an algorithm that takes as an input an array A[1; : : : ; n] of numbers, a positive integer

b, and a non-negative integer k such that kb≤n. The algorithm should print the elements of A

whose ranks in A are b; 2b; 3b; :::; kb (in order). If k = 0, your algorithm should print nothing. Your

algorithm should run in O(n log k) time. For simplicity, you can assume that all the elements in

A are distinct. Prove that your algorithm has the required complexity.

Больше информации в прикрепленных файлах.

По цене рассмотрю Ваше предложение.