联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

您当前位置:首页 >> 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 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。