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: 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: 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: 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: Assume you are using a backtracking algorithm to search for the node 40 in the max heap represented…

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: ****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: 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: 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.
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.
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:
This is Java programming! The current code for BstMaxHeap is printing names backwords. So please modify the code BstMaxHeap.java so it prints as the following: The heap is not empty; it contains 9 entries. The largest entry is Whitney Removing entries in descending order: Removing Whitney Removing Regis Removing Megan Removing Matt Removing Jim Removing Jared Removing Doug Removing Brittany Removing Brett