### Design a data structure which supports two operations

Assignment Help Computer Engineering
##### Reference no: EM132253

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.

#### Questions Cloud

 Explain how an enterprise would use 3g, 4g and wwan : Explain how an enterprise would use 3G, 4G and WWAN Use at least three quality resources in this project. Which method allow channel to synchronization sequence : Which method allow channel to synchronization sequence? Discuss the trade-offs between fibre optic and satellite communication in terms of costs, signal capacity, signalling method, interference, likelihood of failure and repair issues, multipoin.. What is advantage of payroll scheme approach for the project : What is advantage of payroll scheme approach for the project? What do you think is the most suitable Life Cycle Approach? Why didn''t the vendor just bid fewer disks : Why didn't the vendor just bid fewer disks Design a data structure which supports two operations : Design a data structure which supports two operations 1. Insert(S, x) inserts x into S. 2. Remove-Duplicates(S) removes from S all duplicated values. What is a backup strategy or active directory? : What is a backup strategy or Active Directory? The small business that you created new domain controllers for now wants you to develop a backup and recovery plan for Active Directory. Four types of hazard which arise from the use of chemicals : (a) Describe the provisions of Occupational Safety and Health Act 2005 with regard to â€˜Substances hazardous to health' (b) Describe four types of hazard which arise from the use of chemicals How to compare and evaluate speeds of dsl and cable modem : How to compare and evaluate speeds of DSL and cable modem Make a diagram of the DSL and Cable Modem connections to your ISP, cable organization, and telecom to your home router using Visio or its open source another software. How to generate paper for pair of public or private rsa key : How to generate paper for a pair of public or private RSA keys? The high-class reporter for foreign affairs learned about asymmetric cryptography, and proposed to security team at the paper to generate for a pair of public or private RSA keys.

### Write a Review

#### Mathematics in computing

Binary search tree, and postorder and preorder traversal Determine the shortest path in Graph

#### Ict governance

ICT is defined as the term of Information and communication technologies, it is diverse set of technical tools and resources used by the government agencies to communicate and produce, circulate, store, and manage all information.

#### Implementation of memory management

Assignment covers the following eight topics and explore the implementation of memory management, processes and threads.

#### Realize business and organizational data storage

Realize business and organizational data storage and fast access times are much more important than they have ever been. Compare and contrast magnetic tapes, magnetic disks, optical discs

#### What is the protocol overhead

What are the advantages of using a compiled language over an interpreted one? Under what circumstances would you select to use an interpreted language?

#### Implementation of memory management

Paper describes about memory management. How memory is used in executing programs and its critical support for applications.

#### Define open and closed loop control systems

Define open and closed loop cotrol systems.Explain difference between time varying and time invariant control system wth suitable example.

#### Prepare a proposal to deploy windows server

Prepare a proposal to deploy Windows Server onto an existing network based on the provided scenario.

#### Security policy document project

Analyze security requirements and develop a security policy

#### Write a procedure that produces independent stack objects

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g.

#### Define a suitable functional unit

Define a suitable functional unit for a comparative study between two different types of paint.

#### Calculate yield to maturity and bond prices

Calculate yield to maturity (YTM) and bond prices