CIS 413/513代做、代做Data Structures、Java，Python程序语言代写

日期：2020-02-03 11:16

CIS 413/513 Advanced Data Structures

Winter 2020

Assignment 2

due Monday, February 3, 2020

1. (from DPV) Here’s a problem that occurs in automatic program analysis. For a set of

variables x1, x2, . . . , xn you are given some equality constraints of the form “xi = xj” and

some disequality constraints of the form “xi 6= xj”. Is it possible to satisfy all of them?

For example, the constraints

x1 = x2, x2 = x3, x3 = x4, x1 6= x4

cannot be satisfied. Give an algorithm that takes as input m constraints over n variables and

decides whether the constraints can be satisfied.

2. (from Er) Suppose we want to maintain an array X[1 . . . n] of bits, which are all initially zero,

subject to the following operations.

? Lookup(i): Given an index i, return X[i].

? Blacken(i): Given an index i < n, set X[i] ← 1.

? NextWhite(i): Given an index i, return the smallest index ji such that X[j] = 0.

(Because we never change X[n], such an index always exists.)

If we use the array X[1 . . . n] itself as the only data structure, it is trivial to implement

Lookup andBlacken in O(1) time and NextWhite in O(n) time. But you can do better!

Describe data structures that support Lookup in O(1) worst-case time and the other two

operations in the following time bounds. (We want a different data structure for each set of

time bounds, not one data structure that satisfies all bounds simultaneously!)

(a) The worst-case time for both Blacken and NextWhite is O(log n).

(d) The worst-case time for Blacken is O(1), and the amortized time for NextWhite is

O(α(n)).

(Hints)

? (a) think of a self-balancing search tree

? (a) you may need the Successor function

? (d) α(n) can be replaced by lg? n

? (d) the amortized bound did not depend on the Union function being done by-rank

? (d) there is no Whiten.

3. (from Er) Consider the following simpler alternative to splaying:

MoveToRoot(v):

while parent(v) != null

single rotate at v

1

Prove that the amortized cost of MoveToRoot in an n-node binary tree can be ?(n). That

is, prove that for any integer k, there is a sequence of k MoveToRoot operations that

require ?(kn) time to execute

4. (for 551 students) exercise 5 from http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-

scapegoat-splay.pdf

2