Answered: Q1. Implement in Java the greedy…

Q1. Implement in Java the greedy algorithm for giving change with minimum number of coins: while (more coin-sizes && change

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Java Assignment. In Java, implement a min heap and/or a max heap. Include heapsort and a driver that…

A: The solution to the given question is: // Java program for implementation of Heap Sort and…

Q: Suppose a max-heap is stored in array A. Accidentally, one element of A is changed so that the…

A: Building Heap from Array Difficulty Level : Medium Last Updated : 03 Jan, 2022 Given an array…

Q: Create a birthday reminder system using a minheap such that the ordering on the heap is done each…

A: In this question we have to write and create a birthday reminder system using a minheap Let's code…

Q: Suppose you want to use Heapsort to sort the contents of the following array in alphabetical order:…

A: The heap that has been previously obtained is :

Q: Insert Delete Search Display Height Total number of nodes

A: Lets see the solution.

Q: void build (int[] elts, int N); // The "magic" build operation which constructs a heap in O(N) time…

A: the code is an given below public class JavaMinHeap { private final int[] HeapArray; private…

Q: Implement the three self-organizing list heuristics: Count – Whenever a record is accessed it may…

A: Answer: main.cpp#include <iostream>#include <string>#include <fstream>#include…

Q: Justify the extra work involved in the trickle down algorithm compared to the trickle up method when…

A: A heap is a binary tree with the qualities listed below: It is always finished. This indicates that…

Q: Write the pseudocode for min heap or max heap. write the pseudocode for the huffman coding…

A: Answer : class GFG { private int[] Heap; private int size; private int maxsize;…

Q: Suppose you have started with a list of numbers and have built the following max-heap: 75 3 4 2 1.…

A: To Do: To find the first and second swaps.

Q: (3) Consider the linked list provided below: 2 > 3 >1>7>5> 18 > NULL Here the > symbol means a…

A: Here's a Java program that deletes the third last node of a singly linked list in a single pass…

Q: From the given heap can you please insert the item 7 and then the item 6 delete one item from the…

A: Ans:) The given heap is a max heap. For the insertion and deletion of elements, the below steps are…

Q: erase any node from the heap - be it the root or any sub-tree node. The challenge is to rebuild the…

A: Heap Data Structure A Heap is a Special tree type Data Structure In heap it is a tree is a…

Q: 1) Write a program that creates and manages Fibonacci heaps. The program must implement the…

A: JAVA CODE TO COPY:- import java.util.*;class Fibonacci_Heap_Node{ Fibonacci_Heap_Node…

Q: Assume you are using a backtracking algorithm to search for the node 40 in the max heap represented…

Q: 4. Build a Max-Heap on the following array A = Show all the steps.

A: I'm providing the answer to above question. I hope this will be helpful for you

Q: Make a data type that enables you to discover the maximum and minimum, as well as insert, remove,…

A: We can utilise two heaps to create a data type that allows for insert, delete the maximum and…

Q: а. 10, 20, 30, 40, 50 (in decreasi b. 50, 40, 30, 20, 10 (in decreas: c. H, E, A, P, S, O, R, T (in…

A: given - Analyze and evaluate the Heapsort algorithms as Transform-and-Conquer technique usea. 10,…

Q: Suppose you want to use Heapsort to sort the contents of the following array in alphabetical order:…

A: Heapsort is a Sorting technique in which the elements are first inserted in to the binary heap and…

Q: ****The question is to implement two method the update and getIndex. Please the question before…

A: import java.util.Arrays;import java.util.Vector; // A class for implementing the priority queueclass…

Q: Trace out the heap sort algorithm for the following list: {25, 44, 55, 99, 30, 37, 15, 10, 2, 4}.

A: Given Trace out the heap sort algorithm for the following list: {25, 44, 55, 99, 30, 37, 15, 10, 2,…

Q: Using an array that has the initial values given below, rearrange the values into a max heap using…

A: Given: Using an array that has the initial values given below, rearrange the values into a max heap…

Q: There is an algorithm for making the heap complete: 1. Remove the node at the root. 2. Move the node…

A: Heap sort mechanism which refers to the one it is a comparison-based sorting technique based on…

Q: Implement a heap and show how to insert, remove, and search on it.

A: The heap attribute is satisfied by a heap, which is a specific type of tree-based data structure.…

Q: Implement heap sort 1- Use a Heap() class that implements .insert(data) .delete() an .front()…

A: Description The following code performs a heap sort using a Heap class. The Heap class has the…

Q: Show the array's contents after the first deletion operation has been performed on the heap…

A: solution in step-2

Q: size) return; heapBuilder(arr,2*index+ 1); heapBuilder(arr,2*index + 2); heapify(arr,size,index); }…

A: Heap sort is a sorting algorithm that uses the Binary Heap data structure to compare items. It's…

Q: There is an algorithm for making the heap complete: 1. Remove the node at the root. 2. Move the node…

A: The data is continuously deleted from the heap in sorted order when this approach is used. The code…

Q: a) Why would we use circ b) Consider the Double en the right. How will it lo grder:

A: Define header files <iostream> and <string.h> for io and string operations. Define…

Q: This question is on heapsort. (a) We aim to construct a max heap based on an array A. When we call…

A: maxHeapify(array, size, k) set k as largest leftChild = 2k + 1 rightChild = 2k + 2 if…

Q: Question 30 Multiple Select, Choose Two: Which of the following declares a variable within the heap…

A: Heap memory allows random allocation and it contains reference memory . Code optimization is…

Question

Q1. Implement in Java the greedy algorithm for giving change with minimum number of coins:
while (more coin-sizes && change<amount owed)
choose the largest remaining coin-size
if (adding the coin does not make the change exceed the amount owed)
then add coin to change
else delete coin-size
Design specifications:
Represent the coin denominations in a heap ADT using the PriorityQueue or the PriorityBlockingQueue class. Make
the heap independent of the application by using class IntegerCompare, implementing Comparator.
Represent the change in a set ADT using the HashMap or the TreeMap class.
• You should enter the coin denominations (any denominations, not only the "normal" denominations) and the
amount owed. The program should display the change.
Q2. Find an instance (the amount owed and the available set of coin sizes) for which your program cannot give the
change, even when this is theoretically possible.
Q3. Analyze your algorithm (worst case only). Don't forget that you are using a heap and a map (it is a good idea to
review execution times for these data structures).
Q4. Could we use other data structures instead of heap and map to improve our implementation? Give ideas and use
arguments (asymptotic time, easy to implement, etc).
Submit the source code for Q1 and the answers to Q2-Q4.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1: Algorithm of the program:

VIEW

Step 2: Source code of the program:

VIEW

Step 3: Screenshot of the program:

VIEW

Solution

VIEW

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Java programming homework Please help me on Question 9.34
Build a heap from the following array. Show the heap after ???????() occurred at each node. ? = [3, 5, 1, 6, 2, 0, 8, 11, 9] Perform 2 rounds of sorting (i.e., sort two largest numbers) using ????????() procedure. Show the heap and array after every round.
DO NOT COPY FROM OTHER WEBSITES Upvote guarenteed for a correct and detailed answer. Thank you!!!
In class we turned normal arrays into heaps. We called this operation heapify. Given the following array of numbers; show the final heap and the final corresponding array resulting from our heapify operation. Show all work. 5, 9, 8, 13, 7, 15, 2
solve it in Apache NetBeans 12.0
Develop a program in Java to demonstrate the operations of Leftist Heap. The menu should contain following items: for: Insert An implamantion
When The HeapSort Algorithm this algorithm is applied continually, the data is removed from the heap in sorted order. give the code for the Remove and TrickleDown methods.
Given a BST, which traversal method would allow you to turn it into a min heap using N heap insertions calls in O(N) worst case runtime? Draw an example of this process. First, draw a BST with 4 nodes and height of 3. You can pick the integer values in your BST. Then show the resulting traversal order, and a drawing of the values inserted into a min heap using N heap insertions. Redraw the heap after each insertion.
Question Give the sequence of the 13 keys in the array that results after inserting the sequence of 3 keys 75 31 40 into the following maximum-oriented binary heap of size 10: 93 82 77 16 59 20 69 11 13 41 Answer Your answer should be a sequence of 13 integers, separated by whitespace.
Hii I already asked this question yesterday and the answer given is wrong ,only answer if are sure about the answer is 100% correct Thank you
Execute program maxHeap.java and heapApplication.java(Attached Screenshot): Insert the nodes listed in 95 77 43 66 64 25 44 11 10 47 to the heap. Show screenshot. Display the heap array and compare it with the array in 95 77 43 66 64 25 44 11 10 47 . What do you find out? Max Heap import java.util.*; public class maxHeap{ public int heapSize, capacity; public int[] Arr; public maxHeap(int cap) { heapSize = 0; capacity = cap; Arr = new int[cap]; } public void heapify(int parent) { int Lson, Rson, largest, temp; Lson = 2 * parent + 1; Rson = 2 * parent + 2; /* find the largest among A[parent], A[lson] and A[rson] */ if ( Lson <= heapSize - 1 && Arr[Lson] > Arr[parent] ) { largest = Lson; } else { largest = parent; } if (Rson <= heapSize - 1 && Arr[Rson] >…
There is an algorithm for making the heap complete:1. Remove the node at the root.2. Move the node in the last position to the root.3. Trickle the last node down until it is below.When this algorithm is applied continually, the data is removed from theheap in sorted order. imlement the code for the Remove and TrickleDownmethods: