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.

 

Reference no: EM132253

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.

Reviews

Write a Review

 

Computer Engineering Questions & Answers

  Spreadsheet model of the heat transfer situation

Spreadsheet model of the heat transfer situation

  What will be formula of digital certificate of the server

Point out what will be the formula of digital certificate of the server N. we denote the public and private keys of server N as K+ ,N KN, and public or private keys of CA are denoted as K+ CA KCA.

  How many tasks real-time application contain

How many tasks real-time application contain In this particular real-time application, there are many tasks; each runs exact same code except with different data each time.

  Hardware support to memory management

Study any two multicore processor architecture and discuss the following features briefly

  Prepare a proposal to deploy windows server

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

  How to write a class named dayofyear that gets an integer

How to write a class named DayOfYear that gets an integer Day 2 would be January 2 Day 32 would be February 1 Day 365 would be December 31

  How to write code for selection sort, insertion sort

How to write code for selection sort, insertion sort. Using your performance of selection, bubble and insertion sort, add a counter in an appropriate place so as to measure the runtime of your code for example this capacity be a counter to track ..

  How to run and modify marie program

How to run and modify marie program Include a decision before storing and outputing result. If  value of the result is not positive (so zero or negative), set  Result value to the value ZERO (0)

  Data representation and logic

Representing Text and Numbers, Binary Arithmetic, Interpreting Logical Statements, Logic Puzzle, Binary and Algorithms.

  Software engineering and microprocessor systems

Software is required for a simple house burglar alarm system.

  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.

  What profit do you see with partitioned view

Explain your idea for a database along with your thoughts for a partitioned view. 1. How will you use this partitioned view?

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd