Homework Answers
import java.util.*;
public class Coins {
public static int minimumCoins(int value) {
if(value==0) {
return 0;
}
else {
if(value>=5)
{
return 1 + minimumCoins(value-5);
}
else
if(value<5 && value >=2) {
return 1 + minimumCoins(value-2);
}
else {
return 1 + minimumCoins(value-1);
}
}
}
public static void main(String[] args) {
Scanner sc = new
Scanner(System.in);
System.out.println("Enter the
required value");
int requiredValue =
sc.nextInt();
System.out.println("Minumum coins
required to fullfil the given value is " +
minimumCoins(requiredValue));
}
}
[a]
In the dynamic programming, every thing is divided into sub problems which are called states. Also called as DP States.
In the same way, above problem have divided into many parts.
First it is divided into two parts depending upon the function
input value.
First DP state is if block with condition value==0 which is the
base case.
Second DP state is else block which come into exist when above
block is not executed.
Inside the second DP state, main DP parts of our recursive function
will come into exist.
First state is if value is greater than or equal to 5, if it is
true code inside it executes.
otherwise another DP state (part) will come into exist. That is if value is greater than or equal to 2 and less than 5
If that part also not true then the
final DP state will come into exist. which is
else {
return 1 + minimumCoins(value-1);
}
[b]
1) Base case is the case where any recursive call doesnot
involve.
In above function, the code in if block with the codition
(value==0) is base case, because it will return 0 instead of
recursive call.
if(value==0) {
return 0;
}
2) Recursive case is the part where the function calls itself
again.
In above function, the code in else condition is recursive case,
because it is returning the same_func again.
There are three recursive cases in the above program. They are
else {
if(value>=5)
{
return 1 + minimumCoins(value-5);
}
else
if(value<5 && value >=2) {
return 1 + minimumCoins(value-2);
}
else {
return 1 + minimumCoins(value-1);
}
}
[c]
Time complexity can be calculated from the number of iterations or number of recursive calls.
Here in our algorithm, number of recursive calls for our
function will be always less than the input value, except for 0 and
1.
For input 0, number of recursive calls will be 0.
For input 1, number of recursive calls will be 1.
For any given input number of recursive will be the output which will be always less than the input except for 0 and 1.
So for input n, recursive calls = n {for n=0,1}
= n-i {for i<n}
Which says that time complexity will be O(n) or O(n-i)
Obviously O(n-i) for i<n will be equal to O(n)
So our algorithm follows Time complexity of O(n).
Screenshots of different Input and output are also attached.
Add Answer to:
Consider the problem of finding change using as few coins as given coins: lc, 2c, 5c....
Making Change: Given coins of denominations (value) 1 = v1 < v2< … < vn, we...
Making Change: Given coins of denominations (value) 1 = v1 <
v2< … < vn, we wish to make change for an amount A using as
few coins as possible. Assume that vi’s and A are integers. Since
v1= 1 there will always be a solution.
Formally, an algorithm for this problem should take as input:
An array V where V[i] is the value of the coin of the ith
denomination.
A value A which is the amount...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two different algorithms that can solve the problem in the competition. • Algorithm I solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. • Algorithm 2 solves problems of size n by dividing them into 16 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in...
Recall the coin changing problem: given coins of denomination di zonks, where 1 = d1 <...
Recall the coin changing problem: given coins of denomination di zonks, where 1 = d1 < d2 < ··· < dk, and infinitely many coins of each denomination, find the minimum number of coins needed to make exact change for n zonks. Here we ask a different problem. Each coin has a weight, the weight of each coin with denomination di being wi > 0. We want to make exact change while minimizing the total weight of the coins used....
A) Write the pseudocode for an algorithm using dynamic programming to solve the activity-selection problem based...
A) Write the pseudocode for an algorithm using dynamic programming to solve the activity-selection problem based on this recurrence: c[i, j] = 0 if Si; = Ø max {c[i, k] + c[k,j] + 1} if Sij +0 ak eSij B) Analyze the running time (the time complexity) of your algorithm and compare it to the iterative greedy algorithm.
The Egg Drop problem asks us to find the fewest number of egg dropping trials we...
The Egg Drop problem asks us to find the fewest number of egg dropping trials we need to perform in the worst case in order to identify the highest floor from which we can safely drop an egg out of an n-floor building when given k eggs. Notably, if E(n, k) represents the solution to the Egg Drop problem with n floors and k eggs, E(n, k) satisfies the following recurrence: E(n, k) = min i=1,...,n max(E(n ? i, k),...
2. In the BACKPACK problem, you are given a collection of books of different costs and...
2. In the BACKPACK problem, you are given a collection of books of different costs and are tasked with storing as expensive a subset of books as possible so you can sell them at the bookstore in only one trip. Unfortunately, the books are very heavy, and you are limited in how much total weight you can carry. Formally, you are given two arrays C[1.. n] and w[1..n] of positive integers where C[i] is the cost of book i in...
Suppose that, even unrealistically, we are to search a list of 700 million items using Binary...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
Suppose you have an array S indexed from 1 to n which contains n numbers, not...
Suppose you have an array S indexed from 1 to n which contains n numbers, not in any particular order, and you wish to count how many times a given number x occurs in S. Consider the recursive algorithm below for this which finds the number of occurrences of x in the index range i...j in S. Of course, solving the problem would involve an initial call to the algorithm for the range 1.n: int CountOccur (int i,j) { int...
4 Problem 4 -Extra Credit Given an array A, we say that elements A and Al...
4 Problem 4 -Extra Credit Given an array A, we say that elements A and Al are swapped if J >「 but Alj]< A[i]. For example, if A - [8,5,9,7], then there are a total of3 swapped pairs, namely 8 and 5; 8 and 7; and 9 and 7 Describe a recursive algorithm that given an array A, determines the number of swapped pairs in the array in O(n log(n)) time. To analyze the algorithm, you must state the recurrence...
Q1: Here we consider finding the length of the shortest path between all pairs of nodes...
Q1: Here we consider finding the length of the shortest path between all pairs of nodes in an undirected, weighted graph G. For simplicity, assume that the n nodes are labeled 1; 2; : : : ; n, that the weight wij of any edge e = (i; j) is positive and that there is an edge between every pair of nodes. In this question, the goal is to solve this via dynamic programming. Note that the algorithm you will...
Making Change: Given coins of denominations (value) 1 = v1 <
v2< … < vn, we wish to make change for an amount A using as
few coins as possible. Assume that vi’s and A are integers. Since
v1= 1 there will always be a solution.
Formally, an algorithm for this problem should take as input:
An array V where V[i] is the value of the coin of the ith
denomination.
A value A which is the amount...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two different algorithms that can solve the problem in the competition. • Algorithm I solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. • Algorithm 2 solves problems of size n by dividing them into 16 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in...
A) Write the pseudocode for an algorithm using dynamic programming to solve the activity-selection problem based on this recurrence: c[i, j] = 0 if Si; = Ø max {c[i, k] + c[k,j] + 1} if Sij +0 ak eSij B) Analyze the running time (the time complexity) of your algorithm and compare it to the iterative greedy algorithm.
2. In the BACKPACK problem, you are given a collection of books of different costs and are tasked with storing as expensive a subset of books as possible so you can sell them at the bookstore in only one trip. Unfortunately, the books are very heavy, and you are limited in how much total weight you can carry. Formally, you are given two arrays C[1.. n] and w[1..n] of positive integers where C[i] is the cost of book i in...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
Suppose you have an array S indexed from 1 to n which contains n numbers, not in any particular order, and you wish to count how many times a given number x occurs in S. Consider the recursive algorithm below for this which finds the number of occurrences of x in the index range i...j in S. Of course, solving the problem would involve an initial call to the algorithm for the range 1.n: int CountOccur (int i,j) { int...
4 Problem 4 -Extra Credit Given an array A, we say that elements A and Al are swapped if J >「 but Alj]< A[i]. For example, if A - [8,5,9,7], then there are a total of3 swapped pairs, namely 8 and 5; 8 and 7; and 9 and 7 Describe a recursive algorithm that given an array A, determines the number of swapped pairs in the array in O(n log(n)) time. To analyze the algorithm, you must state the recurrence...
Most questions answered within 3 hours.
-
The phylum Protista has often been referred to as a junk drawer
of classification. Explain what...
asked 1 minute from now -
The average amount of money spent for lunch per person in the
college cafeteria is $7.09...
asked 37 seconds ago -
You follow the lab procedure and at the end of Part 4C, you used
an average...
asked 19 minutes ago -
Write 250-450 words, about the following: • Analyze how a
servant leader in your organization or...
asked 23 minutes ago -
3. American and Japanese workers can each produce 4 cars a
year. An American worker can...
asked 26 minutes ago -
On October 1, 20X1, a company purchased a piece of land by
agreeing to pay the...
asked 38 minutes ago -
Jamie is doing a survey at her school about whether the students
feel the cafeteria food...
asked 43 minutes ago -
What are the roles of 3' and 5' untranslated regions in
mRNAs?
asked 44 minutes ago -
A domestic television receives antenna delivers a sky noise
power of -105 dBm to a matched...
asked 43 minutes ago -
What do you think are the chemical reactions involved in the
breathalyzer tests administered to potentially...
asked 58 minutes ago -
A random sample of 120 observations produces a mean of
38.2 from a population with a...
asked 1 hour ago -
The average area of land burned by forest fires every year in
Canada is 2.5 million...
asked 1 hour ago