Question

Q1 assume that the ith operation on a data structure takes Θ(ui) time, where ui is the number of units in the binary representations of i (e.g., for i = 5, the binary representation is 101 and thus u5 = 2).
For a sequence of n operations, determine the amortized time per operation.

Q2 Design a data structure to support the following two operations for a dynamic multiset S of integers (in contrast to sets, multisets allow duplicate values)-

1. Insert(S, x) inserts x into S.
2. Remove-Duplicates(S) removes from S all duplicated values.
For example, Remove-Duplicates ({1, 1, 1, 2, 4, 4, 7}) = {1, 2, 4, 7}. such that
3. Any sequence m Insert and/or Remove-Duplicates operations (starting from the empty multiset) runs in O(m lg m) time;
4. There should be a way to output the elements of S in O(|S|) time.

Q3- Given strings U, V , and T , determine whether T includes interweaving (without spaces) copies of U and V.

For example, the strings U = acab and V = ccb appear interweaving in T = baccacbbd. Design a dynamic-programming algorithm for this problem.

a)Describe the optimal substructure of a solution. Derive and prove a corresponding recurrent formula.
b)Give a pseudocode for a dynamic programming algorithm. Analyze its space and time requirements in terms of the given strings lengths.