Cis work, do first 3 questions 24 hrs

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