1. Consider an array of size eight with the numbers in the following order 40, 20,...
1. Consider an array of size eight with the numbers in the following order 40, 20, 80, 60, 30, 10, 70, 50.
(a) What is the array after heap creation? Make sure to form the heap bottom up as done in class. How many comparisons does the algorithm use?
(b) Show the array after each element sifts down during the remainder of heapsort, and state how many comparisons each sift takes. What is the total number of comparisons for the remainder of heapsort (i.e., the sum of the comparisons for all of the sifts)?
Homework Answers
Add Answer to:
1. Consider an array of size eight with the numbers in the
following order 40, 20,...
How do I write this in the c++ language? 1. (10 points) Write a program to...
How do I write this in the c++ language?
1. (10 points) Write a program to implement Heapsort. The input should be an array of size at least 15. Have the user enter the values or you can specify your own array (unsorted). The output should be the final sorted array AND print out the values in the max heap (just the heap, NOT the full array) after each MAX-HEAPIFY (after BUILD- MAX-HEAP i.e. don't print output in BUILD-MAX-HEAP) in...
Consider a MergeSort-like algorithm in which the array is split into thirds, rather than halves. (a)...
Consider a MergeSort-like algorithm in which the array is split into thirds, rather than halves. (a) Write pseudo-code for your algorithm. You may assume a three-way merge algorithm is available. Your algorithm should work for general n, i.e., even if the size of the array is not a power of 3. (b) Use the tree method to analyze exactly how many comparisons your algorithm uses. You may assume that the size of the array is a power of 3. Assume...
Consider an ordered array A of size n and the following ternary search algorithm for finding...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
Problem 3 (20 points): An array A of size (n) contains floating-point items. 1. Implement a...
Problem 3 (20 points): An array A of size (n) contains floating-point items. 1. Implement a Divide & Conquer algorithm to return the number of items with values less than a given value (x). (5 points) 2. Test your algorithm by generating an array A of size n = 1024 random floating-point numbers with each number R between 0 and 1, i.e. 0.0 <R< 1.0. Run the algorithm to find the percentage of the numbers in the array with values...
JAVA PROGRAMMING PLEASE This lab has three parts: Create an ArrayList class. Create a LinkedList class....
JAVA PROGRAMMING PLEASE This lab has three parts: Create an ArrayList class. Create a LinkedList class. Print out the results after testing each of the methods in both of the classes and solving a simple problem with them. Task 1 – ArrayList Class Create an ArrayList class. This is a class that uses an internal array, but manipulates the array so that the array can be dynamically changed. This class should contain a default and overloaded constructor, where the default...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2)...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
Consider the following definition of a C++ class that acts like an array with bounds-checking (i.e....
Consider the following definition of a C++ class that acts like an array with bounds-checking (i.e. ensuring that a valid array index is used each time an array element is referenced). class c_array { public: c_array(int s){ size = s; a = new int[size]; } int &operator[](int i); int get_size() { return size; } private: int size; int *a; }; 1- Write the header for the c-array class in a different header file (c_array.h). 2- Complete the definition of the...
Java question Q1) Use the following code snippet which generates a random sized array with random...
Java question Q1) Use the following code snippet which generates a random sized array with random contents to complete the following problems: public int [] createRandomArray() { int size = (int) (Math.random() * 10) + 1; int[] array = new int [size]; for (int i = 0; i < array.length; i++) { array[i] = (int) (Math.random() * 10 ) + 1; } return array; } Assignment...
1. Consider the following unordered list: 20, 35, 25, 10, 40, 50, 45. Perform heap sort...
1. Consider the following unordered list: 20, 35, 25, 10, 40, 50, 45. Perform heap sort to sort this list in nondecreasing (ascending) order. a. Perform the bottom-up method to arrange these values into a max heap. Show the heapify operations on each relevant subtree. (10 points) b. Show the tree representation and the array representation of these numbers after every dequeue operation. Remember that dequeue does not delete a number. Dequeue will instead remove that number from the heap...
QUEUEBOX: Using an Array of initial size of five (5) for storage, start with the following...
QUEUEBOX: Using an Array of initial size of five (5) for storage, start with the following generic class declaration for QueueBox: public class QueueBox<E> { private E[] elements = (ED))( new Object[5]); private int front_idx = 0; private int rear_idx = 0; private int count = 0; Hint: use the count variable to keep track of how many elements are in the queue (increment count when enqueing and decrement when dequeing). Makes it a lot easier to determine if the...
How do I write this in the c++ language?
1. (10 points) Write a program to implement Heapsort. The input should be an array of size at least 15. Have the user enter the values or you can specify your own array (unsorted). The output should be the final sorted array AND print out the values in the max heap (just the heap, NOT the full array) after each MAX-HEAPIFY (after BUILD- MAX-HEAP i.e. don't print output in BUILD-MAX-HEAP) in...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
Problem 3 (20 points): An array A of size (n) contains floating-point items. 1. Implement a Divide & Conquer algorithm to return the number of items with values less than a given value (x). (5 points) 2. Test your algorithm by generating an array A of size n = 1024 random floating-point numbers with each number R between 0 and 1, i.e. 0.0 <R< 1.0. Run the algorithm to find the percentage of the numbers in the array with values...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
1. Consider the following unordered list: 20, 35, 25, 10, 40, 50, 45. Perform heap sort to sort this list in nondecreasing (ascending) order. a. Perform the bottom-up method to arrange these values into a max heap. Show the heapify operations on each relevant subtree. (10 points) b. Show the tree representation and the array representation of these numbers after every dequeue operation. Remember that dequeue does not delete a number. Dequeue will instead remove that number from the heap...
QUEUEBOX: Using an Array of initial size of five (5) for storage, start with the following generic class declaration for QueueBox: public class QueueBox<E> { private E[] elements = (ED))( new Object[5]); private int front_idx = 0; private int rear_idx = 0; private int count = 0; Hint: use the count variable to keep track of how many elements are in the queue (increment count when enqueing and decrement when dequeing). Makes it a lot easier to determine if the...
Most questions answered within 3 hours.
-
what is IoT? How is it being used today? How will it be used in
the...
asked 4 minutes ago -
Please answer the four questions below.
1. If you were going to test a method that...
asked 19 minutes ago -
Provide two or three examples of support he uses to reinforce
his arguments?
The Alienation of...
asked 26 minutes ago -
QUESTION 1
Why do we see terms with multiple names in the database
community?
Consistency is...
asked 22 minutes ago -
In a titration experiment, 11.5 mL of 0.400 M H2SO4 neutralized
48.0 mL of NaOH. What...
asked 26 minutes ago -
A shot-putter throws the shot with a horizontal velocity of 10
m/s and a
vertical velocity...
asked 42 minutes ago -
Mildred sells industrial-sized refrigeration units. Her
prospective buyer's face looks tense, and his forehead is wrinkled....
asked 43 minutes ago -
Clark Heter is an industrial engineer at Lyons Products. He
would like to determine whether there...
asked 1 hour ago -
3. Use a text editor to create a comma-delimited file of user
IDs and passwords. Revise...
asked 1 hour ago -
Jensen and Associates has a projected balance
sheet that includes the following accounts. What is the...
asked 58 minutes ago -
implement a doubly-linked list in C. Each node in the linked list should contain a string,...
asked 1 hour ago -
What are some best practices and things to avoid when developing
a PowerPoint presentation or file
asked 1 hour ago