”
CIS 413/513作业 写作、 写作Data Structures作业、Java，Python程序语言作业 辅导
CIS 413/513 Advanced Data Structures
Winter 2020
Assignment 2
due Monday, February 3, 2020
1. (from DPV) Heres 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 https://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-
scapegoat-splay.pdf”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
