Questionq1 assume that the ith operation on a data

Assignment Help Computer Engineering

Reference no: EM13348309

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.

Reference no: EM13348309

Questions Cloud

Questionwireless technologywrite down a three to four page : questionwireless technologywrite down a three to four page paper in which you-1. compare pros and cons of 3g and 4g

Questionphysical layer is only concerned with transmission : questionphysical layer is only concerned with transmission of a series of bits from one point to another. assume that

Questiona company is rewriting its payroll scheme to move : questiona company is rewriting its payroll scheme to move it from old batch-type mainframe to a distributed

Questionthis is from my the essentials of computer : questionthis is from my the essentials of computer organization and architecture book its 3rd edition and website only

Questionq1 assume that the ith operation on a data : questionq1 assume that the ith operation on a data structure takes thetaui time where ui is the number of units in the

Questionthe small business that you created new domain : questionthe small business that you created new domain controllers for now wants you to develop a backup and recovery

Question 1a a receptionist who has been working in a large : question 1a a receptionist who has been working in a large accountancy firm for eleven months has been complaining of

Questionwrite down a three to four page paper in which you : questionwrite down a three to four page paper in which you can search following points1. identify the dsl and cable

Questionthe high-class reporter for foreign affairs learned : questionthe high-class reporter for foreign affairs learned about asymmetric cryptography and proposed to security team

User Account

All Pages