聯系方式

您當前位置:首頁 >> Python編程Python編程

日期:2020-01-31 11:15

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


版權所有:編程輔導網 2018 All Rights Reserved 聯系方式:QQ:99515681 電子信箱:[email protected]
免責聲明:本站部分內容從網絡整理而來,只供參考!如有版權問題可聯系本站刪除。

25选5一等奖多少钱