HW3_draft

docx

School

North Carolina State University *

*We aren’t endorsed by this school

Course

505

Subject

Computer Science

Date

Feb 20, 2024

Type

docx

Pages

Uploaded by CaptainOxideVulture34

CSC 505, Homework 3 1. a) (4 points) Give a recursive algorithm that generates a similar series of coins for changing n cents. Don’t use dynamic programming for this problem. Ans: cents = [50, 25, 10, 5, 1] change(n): if n < 1 else return “Done” for i = 1 to length of cents ch = n//cents[i] if ch > 0 print ch cents[i] cents n = n- (ch)*cents[i] change(n) Description of Algorithm: In this greedy algorithm, the denominations are sorted in reverse and are put into an array, cents, so that the largest denomination will be subtracted first, resulting in the biggest coin to be returned, smaller than the change specified. If the change is 0, then there are no coins to be given. If the change is not 0, then the algorithm loops through the array of cents. Inside the loop, the algorithm finds the floor value of dividing the change n with the current value in cents. This is stored in another variable ch. If ch is greater than 0, this means that n is greater than cents[i] , so at least one cents[i] coin can be removed from change n . The algorithm does exactly that by printing the number of coins for value cents[i] and subtracting ch number of cents[i] coins from n . Regardless of whether n is more than the current cents[i] , the algorithm will recursively check all the values of the array cents until n is less than 1 in which case it returns “Done” to exit out of the function. b) (4 points) Write an O(1) (non-recursive!) algorithm to compute the number of returned coins. Ans: ( c change instead of n change ) change(c): if (c > 50) if (c%50 == 0) then print(c/50 number of fifty cent coins) return “Done” then print(c//50 number of ten cent coins) c-= (c//50)*50 if (c > 25) if (c%25 == 0) then print(c/25 number of twenty-five cent coins) return “Done” then print(c//25 number of ten cent coins) c-=(c//25)*25 if (c > 10)

if (c%10 == 0) then print(c/10 number of ten cent coins) return “Done” then print(c//10 number of ten cent coins) c-=(c//10)*10 if (c > 5) if (c%5 == 0) then print(c/5 number of five cent coins) return “Done” then print(c//5 number of five cent coins) c-=(c//5)*5 if (c > 0) then print(c number of one cent coins) return “Done” if (c>25) if (c%25 == 0) then print(c/25 number of twenty-five cent coins) return “Done” then print(c//25 number of ten cent coins) c-=(c//25)*25 if (c>10) if (c%10 == 0) then print(c/10 number of ten cent coins) return “Done” then print(c//10 number of ten cent coins) c-=(c//10)*10 if (c >5) if (c%5 == 0) then print(c/5 number of five cent coins) return “Done” then print(c//5 number of five cent coins) c-=(c//5)*5 if ( c//5 == 0 and c > 0) then print(c number of one cent coins) return “Done if (c > 10) if (c%10 == 0) then print(c/10 number of ten cent coins) return “Done” then print(c//10 number of ten cent coins) c-=(c//10)*10 if (c > 5) if (c%5 == 0) then print(c/5 number of five cent coins)

return “Done” then print(c//5 number of five cent coins) c-=(c//5)*5 if (c > 0) then print(c number of one cent coins) return “Done” if (c > 5) if (c%5 == 0) then print(c/5 number of five cent coins) return “Done” then print(c//5 number of five cent coins) c-=(c//5)*5 if ( c > 0) then print(c number of one cent coins) return “Done” if (c > 0) then print(c number of one cent coins) return “Done” if (c<=0) then then print “No change specified Description of Algorithm: In this greedy algorithm of O(1), the algorithm starts with checking if c is greater than the largest denomination given, 50. If this is the case, then there is another if-statement to check if the modulus of c and 50 will result in 0. If it is 0, that means that there is a whole number of 50 cent coins to be returned in exchange for c change. Otherwise, the algorithm follows a similar pattern to the algorithm in 1a where the floor of c/50 coins are returned and since there are no loops in this algorithm, the total number of 50 cent coins are removed from change c: c-= (c//50)*50. This pattern of if-statements continues for the rest of the denominations except that they are all nested under the first statement (the biggest denomination). Once this big if-statement reaches its end, it returns “Done” to exit out of the function. There are subsequent if-statements in a similar manner with if-statements of lesser denominations nested under the larger denominations. Through this algorithm, each denomination takes a different amount of constant time to return change.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

c) (1 point) Show that the above greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, and 10 cents. Ans: Using these denominations, the greedy algorithm would not result in the minimum number of coins. For example, if there needed to be change for 12 cents, the greedy algorithm would first return 10 cent coin and then two 1 cent coins, resulting in a total of 3 coins. However, the minimum number of coins one can receive from 12 cents is two 6 cent coins. d) (6 points) Given a set of arbitrary denominations C =( c 1 ,..., c d ), describe an algorithm that uses dynamic programming to compute the minimum number of coins required for making change. You may assume that C contains 1 cent, that all denominations are different, and that the denominations occur in an increasing order. Ans: (n change, C set of arbitrary denominations) change(n, C) let maxi be empty array of length d-1 let sums be empty array of length d-1 for i= 1 upto d maxi[i] = value//denomination[i] for i = 1 upto maxi.length value_rest = value - (maxi[i]*denomination[i+1]) let cents be array of 0’s of length i+2 last element in cents = maxi[i] for j = i downto 0 if (denomination[j] = 1) cents[0] = value_rest else if (value_rest >= denomination[j]): cents[j] = cents[j]+1 value_rest=value_rest- (value_rest//denomination[j])*denomination[j] sums[i] = sum(cents) return minimum value from array of sums Description of Algorithm: This algorithm was formulated by seeing the pattern that the least number of coins always occurs when one of the last d-1 denominations has the maximum number of coins. That means that this denomination is removed first form the value ( value//denomination[i] ) and then all the denominations lesser than denomination[i] follow. So the algorithm tabulates the maximum number of coins removed from all denominations except the first one ( c1 = 1). It then treats each element of the tabulation (maxi) as a starting point to calculate the rest of the coins. For example, if the denominations were [1, 5, 10, 15, 25] and the value was 37, then maxi would be [7, 3, 1]. In this second for loop, value_rest is calculated after removing the maximum number of coins of value

denomination[i+1] (since the algorithm doesn’t remove the maximum coins of value 1). There is another array initialized here as the length of i+2 in 0’s. In the nested loop, whenever the value_rest is bigger than a denomination that is not 1, then the value for that particular index in the array is incremented by 1. Then the value_rest will equal the value_rest with the new denomination removed. At the end, the sum of all the values in cents is added to the array sums. And the minimum value in sums is returned as the least number of coins that can be returned as change for a specific value. e) (6 points) Implement the algorithm described in d). The code framework are given in the zip file: framework.zip. To avoid loss of marks please make sure that all provided test cases pass on remote-linux server by using the test file. Instructions for setting up remote-linux server and testing are given in the document HW3_Programming_Assignment_Setup.pdf. 2. a) The optimal substructure for the Maximum Palindromic Subsequence Problem (MPSP) can be described as follows: The length of the longest palindromic subsequence L(1, n) can be determined based on the characters at positions i and j in the sequence x[1...n]. Let L(i, j) be the length of the longest palindromic subsequence in the subsequence x[i...j]. To find L(i, j), we can consider the following cases:  If x[i] == x[j] (the characters at the endpoints are the same): In this case, the length of the longest palindromic subsequence L(i, j) is 2 (the endpoints) plus the length of the longest palindromic subsequence within x[i+1...j- 1], which is L(i+1, j-1).  If x[i] != x[j] (the characters at the endpoints are different): In this case, we need to consider two possibilities: i. L(i+1, j): The longest palindromic subsequence within x[i+1...j]. ii. L(i, j-1): The longest palindromic subsequence within x[i...j-1]. We choose the maximum of these two possibilities to maximize the length of the palindromic subsequence. The recurrence relationship for L(i, j) can be expressed as follows: L(i, j) = { 0 if i > j (empty subsequence) 1 if i = j (single-character subsequence, which is a palindrome) 2 if i = j + 1 and x[i] = x[j] (two identical characters make a palindrome) L(i+1, j-1) + 2 if x[i] = x[j] (the characters at both ends match, so we can extend the palindrome by two characters) max(L(i+1, j), L(i, j-1)) if x[i] ≠ x[j] (we need to choose the longer of the two subsequences, excluding either the first or the last character) }

b) Algorithm : 1. Initialize a 2D table L of size n x n, where L[i][j] will store the length of the longest palindromic subsequence for the substring x[i...j]. Initialize all elements to 0. 2. Iterate over the characters in the sequence from right to left and bottom to top, filling in the table using the recurrence relationship described above. 3. For each i from n-1 to 0 and each j from i to n-1:  If x[i] == x[j], set L[i][j] = 2 + L[i+1][j-1].  Otherwise, set L[i][j] = max(L[i+1][j], L[i][j-1]). 4. The final answer is stored in L[0][n-1], which represents the length of the longest palindromic subsequence in the entire sequence. This algorithm fills the 2D array L in a bottom-up manner, considering the optimal substructure, and ultimately provides the length of the longest palindromic subsequence in the given sequence x[1...n] in O(n^2) time. Pseudocode : public static int longestPalindromicSubsequence(String x) { int n = x.length(); int[][] L = new int[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (x.charAt(i) == x.charAt(j)) { if (i + 1 <= j - 1) { L[i][j] = 2 + L[i + 1][j - 1]; } else { L[i][j] = 2; } } else { L[i][j] = Math.max(L[i + 1][j], L[i][j - 1]); } } } return L[0][n - 1]; } Correctness(using loop invariant): Loop Invariant 1 : At the beginning of each iteration of the outer loop, L[i][j] contains the length of the longest palindromic subsequence for the substring x[i...j] where i and j are valid indices. Loop Invariant 2 : At the beginning of each iteration of the inner loop, the L table is correctly filled for all substrings x[i...j] where i and j are indices from i to n-1. That is, L[i][j]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

is correctly computed based on the recurrence relationship. Initialization : Before the first iteration of the outer loop (when i = n - 1), L[i][j] for all j represents the length of the longest palindromic subsequence in the substrings x[i...j] which consist of only a single character. This is true, as a single character is a palindrome of length 1. Loop Invariant 1 is true for the initial state, and Loop Invariant 2 is true for the initialization as well. Maintenance : Assume that both Loop Invariant 1 and Loop Invariant 2 are true at the start of an iteration of the outer and inner loops. We will show that they remain true after each iteration.  Outer Loop: When the outer loop iterates from i = n - 1 to i = 0, we fill in L[i][j] for various j. By the end of each outer loop iteration, Loop Invariant 1 is maintained because the longest palindromic subsequences for substrings x[i...j] are correctly computed for each value of i.  Inner Loop: In each inner loop iteration, L[i][j] is calculated based on the recurrence relationship as described in the algorithm. This calculation maintains the correctness of Loop Invariant 2 since we correctly fill in L[i][j] based on the length of palindromic subsequences for the substrings x[i+1...j] and x[i...j-1]. Termination : After the outer loop completes (when i becomes 0), both Loop Invariant 1 and Loop Invariant 2 hold. This means that L[0][n-1] contains the length of the longest palindromic subsequence for the entire sequence x, and the algorithm has successfully computed the result. Time Complexity The algorithm uses two nested loops to fill in the L table, where n represents the length of the input sequence x. The outer loop iterates from n-1 down to 0, and the inner loop iterates from i to n-1. In each iteration of the inner loop, we perform a constant amount of work to compute L[i][j] based on the recurrence relationship. Since we visit each element of the L table exactly once, the time complexity is O(n^2). Space Complexity The space complexity is determined by the space required to store the L table. The L table is a 2D array of size n x n, where each cell L[i][j] stores an integer. Therefore, the space complexity is O(n^2) as well, since we need to store all possible values of L[i][j] for all substrings of x. Example 3. Algorithm Description : 1. Initialize variables:  current_position to 0 (starting in Raleigh)  stops as an empty list to store selected gas stations  remaining_distance to d (total distance to Chapel Hill)

2. While current_position is not at the restaurant (next to gas station n): a. Find the farthest gas station you can reach from current_position without running out of gas. b. Add the selected gas station to the stops list. c. Update current_position to the location of the selected gas station. d. Subtract the distance traveled from remaining_distance. 3. Return the list of selected gas stations in stops. Pseudocode : public static List<Integer> findOptimalStops(List<Integer> gasStations, int d) { List<Integer> stops = new ArrayList<>(); int currentPosition = 0; // Start in Raleigh int remainingDistance = d; // Total distance to Chapel Hill //While not at the restaurant while(currentPosition<gasStations.get(gasStations.size()-1)){ Integer nextStation = null; // Initialize the next station to null for (int i = gasStations.size() - 1; i >= 0; i--) { int distanceToStation = gasStations.get(i) - currentPosition; if (distanceToStation <= remainingDistance) { nextStation = gasStations.get(i); // Select the farthest reachable station break; } } if (nextStation == null) { System.out.println("No solution, cannot reach the restaurant"); return null; } stops.add(nextStation); // Add the station to stops currentPosition = nextStation; // Update current position remainingDistance -= (nextStation - currentPosition); } return stops; } Correctness Loop Invariant: At the beginning of each iteration, stops contains the gas stations selected so far, and remaining_distance is the distance remaining to the restaurant.

Initialization: Before the first iteration, stops is an empty list, and remaining_distance is initially set to d, which is the total distance to Chapel Hill. So, the loop invariant holds. Maintenance: In each iteration, we select the farthest reachable gas station and add it to stops. We update current_position to the location of the selected station, and remaining_distance is reduced by the distance traveled. This ensures that the loop invariant still holds for the next iteration. Termination: When the loop terminates, current_position will be at the restaurant (next to gas station n). The loop invariant still holds, as stops contains all the selected gas stations, and remaining_distance is zero, as you've reached your destination. This loop invariant ensures the correctness of the algorithm, as it guarantees that the selected gas stations will get you to the restaurant while making as few stops as possible. Time Complexity: The algorithm's time complexity is O(n) because it iterates through the sorted list of gas stations only once. The inner loop, while finding the next station within reach, takes constant time as it iterates backward through the gas station list. There are no nested loops or other time-consuming operations. Example: Let's find the optimal stops for a journey from Raleigh to Chapel Hill. Input: Gas station locations: [10, 30, 40, 50, 60, 70, 80, 90] Total distance to Chapel Hill (d): 100 miles Step 1: Initialize currentPosition to 0 (starting in Raleigh). Initialize remainingDistance to 100 (total distance to Chapel Hill). Initialize stops as an empty list. Step 2: While currentPosition (initially 0) is less than the location of the last gas station (90), enter the loop. Step 3: In the first iteration of the loop, we find the farthest gas station we can reach without running out of gas. The farthest station within reach is 40 miles from Raleigh, and we have enough gas to reach there without refueling. Add this station to the stops list. Update currentPosition to 40 miles.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Subtract the distance traveled (40 miles) from remainingDistance, which is now 60 miles. At this point, stops contains [40], and remainingDistance is 60 miles. Step 4: The loop continues as currentPosition (40 miles) is still less than the location of the last gas station (90). Step 5: In the second iteration of the loop, we find the farthest gas station we can reach. The farthest station within reach is 70 miles from Raleigh, and we have enough gas to reach there without refueling. Add this station to the stops list. Update currentPosition to 70 miles. Subtract the distance traveled (70 - 40 = 30 miles) from remainingDistance, which is now 30 miles. At this point, stops contains [40, 70], and remainingDistance is 30 miles. Step 6: The loop continues as currentPosition (70 miles) is still less than the location of the last gas station (90). Step 7: In the third and final iteration of the loop, we find the farthest gas station we can reach. The farthest station within reach is 90 miles from Raleigh, and we have enough gas to reach there without refueling. Add this station to the stops list. Update currentPosition to 90 miles. Subtract the distance traveled (90 - 70 = 20 miles) from remainingDistance, which is now 10 miles.At this point, stops contains [40, 70, 90], and remainingDistance is 10 miles. Step 8: The loop checks whether currentPosition (90 miles) is less than the location of the last gas station (90). Since they are equal, the loop terminates. Result: The algorithm finishes, and stops contains the optimal stops: [40, 70, 90]. These stops ensure you reach the restaurant in Chapel Hill while making as few stops as possible, satisfying the constraints of the problem.

HW3_draft

Related Documents