ZuoTi.Pro
Question

2. You must support the following two operations on a set of numbers: (1) insertion, and (2) large-delete which is to delete the largest half of the values in the set. In other words if there are k elements you delete the elements with the rk/2] largest values. For example, large-delete15, 3,7,9,1,8) 3,1,5) Both operations should take constant time, amortized. Assume that you start with an empty data structure. You can use whatever data structure you like for the set. A small amount of the total credit for this problem will be given for making a non-complicated choice. (a) Describe your structure and how you will handle the operations algorithmically. Explain what the worst-case time complexity is for one operation, and for n operations. (a) Analyze with the accounting method (b) Analyze with the potential method

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

The requirement is to design a dynamic multi-set. Since it is dynamic and a set, it has the following properties: The elements can be inserted into the set dynamically. So, the set must grow to accommodate for this feature. Since, it is a set; there is no need to maintain an order of the elements. The elements can be randomly placed Since, it is a multi-set, repetition of the elements is allowed. Keeping the above properties in mind and the constraints provided, a proper data structure for this is a simple dynamic array. There is no need of sorting the array

0 0
Add a comment
Know the answer?
Add Answer to:
2. You must support the following two operations on a set of numbers: (1) insertion, and...
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. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • 1) A Java program that implements an insertion sort algorithm. (InsertionSort.java): Must include the proper comments...

    1) A Java program that implements an insertion sort algorithm. (InsertionSort.java): Must include the proper comments in the code. 2) A report in pdf. It contains: a) the pseudocode of the insertion sort algorithm and assertions between lines of the algorithm. b) As insertion sort has a nested-loop of two layers, you need to put one assertion in each loop. c) a proof of the partial correctness of the algorithm using mathematical induction c.1) prove the correctness of the two...

  • 1. What is the worst case time complexity of insertion into a binary search tree with...

    1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...

  • Problem 3 Suppose that you have a set of n large, orderable, objects, each of size...

    Problem 3 Suppose that you have a set of n large, orderable, objects, each of size q, so that it requires time e(a) to time to compute a hash function h(a) for any object and requires time e(g) to compare any two objects. Describe a compound data structure, built out of a heap and a hash table, that supports the following operations with the specified run times.. elt (x) Is x an element of the set? Expected run time O(g)....

  • problem 2 can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to...

    problem 2 can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1, n). You also need to provide the worst case time complexity analysis of your algorithm. 2. (20 points) Given a set of n distinct numbers, we wish to find the k largest in sorted order using a comparison-based algorithm. Give an algorithm that implements each of the following methods, and...

  • Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for...

    Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for “travel arrangement”. For example, at a high level of abstraction, the algorithm for “travel arrangement” is: book a hotel buy a plane ticket rent a car Using the principle of stepwise refinement, write more detailed pseudocode for each of these three steps at a lower level of abstraction. Exercise 2 Asymptotic Complexity (3 pts) Determine the Big-O notation for the following growth functions: 1....

  • 1) Write a segment of code (application level) to perform each of the following operations. Assume...

    1) Write a segment of code (application level) to perform each of the following operations. Assume myStack is an object of the class ArrayStack. You may call any of the public methods of ArrayStack. You may declare additional stack objects. a) Set secondElement to the second element from the top of myStack, leaving myStack without its original top two elements. b) Set bottom equal to the bottom element in myStack, leaving myStack empty. c) Set bottom equal to the bottom...

  • please be thorough with explanations. thank you Question 2 Consider the implementation we made in class...

    please be thorough with explanations. thank you Question 2 Consider the implementation we made in class for ArrayList, and its extensions you did in the lab. In this question, we will add two more methods to this class: the insert method and the pop method. For this question, please submit the modified ArrayList class. a) Implement the method insert (self, index, val) that inserts val before index (shifting the elements to make room for val). For example, your implementation should...

  • // 1. Add methods to get and set, Data and Link. Data should be any Comparable...

    // 1. Add methods to get and set, Data and Link. Data should be any Comparable object. class Node { Integer data; // Integer is Comparable Node link; public Node(Integer data, Node link) { this.data = data; this.link = link; } public Integer getData() { return data; } public void setData(Integer data) { this.data = data; } public Node getLink() { return link; } public void setLink(Node link) { this.link = link; } } // b. Create MyLinkedList class and...

  • SECTION B (4 QUESTIONS, 90 MARKS) Question 4. [32 marks in total] For this question, assume the definition of Java clas...

    SECTION B (4 QUESTIONS, 90 MARKS) Question 4. [32 marks in total] For this question, assume the definition of Java class Heap given in the Appendix. The heaps referred to in this question are all maxHeaps. a. (5 marks) Insert into an empty (binary) heap the values 35, 4, 72, 36, 49, 50. Draw all intermediate steps b. (3 marks) Carry out one deletion operation on the final heap in (a.) above. c. (2 marks) Give the worst-case time complexity...

  • Assignment on Java programing 1. Write programs for the following exercises in Java. Each file should...

    Assignment on Java programing 1. Write programs for the following exercises in Java. Each file should have short description of the implemented class and for files with main method the problem it is solving. Make sure your files have appropriate names. Programs should write output to the Console. b) BST: Implement Binary Search Tree ADT with insert(int key), delete(int key), Node find(int key), and in-order traverse() where it prints the value of the key. Your operations should use recursion. The...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT