Question

Describe how one can implement each of the following operations on an array so that the...

Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array’s size n.

a. Delete the $i$th element of an array ($1\leq i \leq n$).

b. Delete the $i$th element of a sorted array (the remaining array has to stay sorted).

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Ans.

First of all I think "$i$th element" it should be ith element so i'm answering it by considering as ith

a).

For the first part best way to delete ith element of a unsorted array of size n so that the time taken to delete it does not depend on the array’s size is swaping the ith element with the (n-1)th element (i.e last element) of given array and reduce the array size by 1.

b).

Best way to delete the ith element of sorted array of size n so that the time taken to delete it does not depend on the array’s size is using "lazy deletion" i.e replacing the ith element with a special symbol that cannot be a value of the array's element (eg., 0 for an array which hold the integer greater than 0) to mark the ith position as empty.

This is done to indicate that the element does not belong to the array any more.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
c++ just one file for all of it. You are to implement a 'list' class to...
c++ just one file for all of it. You are to implement a 'list' class to handle a list with general operations. That means you can insert and delete any element anywhere in the list. your list will be an array. the list has no order, except for the order you insert or delete. The methods you are to implement are as given: constructor methods (two, default and copy constructor, a list to a newly defined list, ie 'list listA(listB)')...
In five sentences describe the following: a) how you would implement a stack using an array,...
In five sentences describe the following: a) how you would implement a stack using an array, including the push and pop operation b) how you could implement a queue using a linked list, including what type of linked list would be best, the enqueue and dequeue operations
You are asked to implement a C++ class to model a sorted array of unsigned integers....
You are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Your class should should: (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be...
How to use C++ figure this question? Collection and Sorted Collection An array is great for...
How to use C++ figure this question? Collection and Sorted Collection An array is great for storing a list of values. However, one challenge when working with arrays is they have a fixed size. If you declare an array of size 10 and later need to actually store 11 elements you have to create a new array and copy everything over. C++ (and other langauges) create classes that handle this and other operations behind the scenes. In this assignment, we...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
CAN YOU PLEASE WRITE THIS CODE IN A DIFFERENT WAY 'EASIER AND BETTER' QUESTION Using C++...
CAN YOU PLEASE WRITE THIS CODE IN A DIFFERENT WAY 'EASIER AND BETTER' QUESTION Using C++ 11. Write a function that will merge the contents of two sorted (ascending order) arrays of type double values, storing the result in an array out- put parameter (still in ascending order). The function shouldn’t assume that both its input parameter arrays are the same length but can assume First array 04 Second array Result array that one array doesn’t contain two copies of...
MATLAB save output as array this is my code so far, I'm going to need to...
MATLAB save output as array this is my code so far, I'm going to need to save these as arrays or vectors i think to take some statistics on them. how do i save each walkers position relitive to time I should end up with 1000x 1000 matrix i think or 1000 arrays walkers=1000; %walkers=input('how many walkers do you want to simulate?') N = 1000; %N = input('how many steps do you want?') for k= 1:walkers displacement= randn(1,N); x =...
One way to represent a very large integer (one that won't fit into a variable of...
One way to represent a very large integer (one that won't fit into a variable of type short, int, or even long) is to use an array. The array is of type int, so each element in the array can hold an integer -- we will store just one digit of our number per array element. So if a user entered 2375, it might be stored as -------------------------- | 2 | 3 | 7 | 5 | ... | --------------------------...
Write a template-based class that implements a template-based implementation of Homework 3 that allows for any...
Write a template-based class that implements a template-based implementation of Homework 3 that allows for any type dynamic arrays (replace string by the template in all instances below). • The class should have: – A private member variable called dynamicArray that references a dynamic array of type string. – A private member variable called size that holds the number of entries in the array. – A default constructor that sets the dynamic array to NULL and sets size to 0....
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT