Problem Set 4
Dynamic Programming Solution Guidelines (For Problems 2 and 3)
Dynamic programming can be very tricky and this template will help guide you through solving new problems. Get in the habit of going through the list and filling everything out step by step. We will grade harshly on missing items. And if theres no english description of the two items mentioned below then the solution will get anAUTOMATIC 0on homeworks and exams with no exceptions.
- (AUTOMATIC 0 IF MISSING) English description of the
(a) recursion you use/the memoization table.
(b) logic behind your recursion.
- The actual recursion. And dont forget the base cases!
- Final value we have to return.
- Brief description of how an iterative Algorithm would l oop through the memoization array and fill the values (make sure your order makes sense, and that values are already filled when you call them). Pseudocode isnt required, just a couple sentences.
- The number of subproblems you have to solve.
- How much time each subproblem takes to solve (usually constant or linear).
- Final running time.
Problem 1 (Edges and Spanning Trees) 20
Suppose we have a weighted undirected graphG, where all the weights are not necessarily distinct. Give an efficient algorithm that, given an edgee, determines whethereis in a minimum spanning tree ofGand whethereis in all minimum spanning trees ofG. For your submission please provide pseudocode of your algorithm and analysis for both correctness and runtime.
Problem 2 (Longest Palindrome Subsequence) 25
Given an arrayA[1… n]of letters, compute the length of the longest palindrome subsequence ofA. A sequenceP[1… m]is a palindrome ifP[i] =P[mi+1]for everyi. For example, RACECAR is a palindrome, while REAR is not a palindrome; and the longest palindrome subsequence in the string ABETEB is BETEB of length 5.
Problem 3 (Coin Change) 25
Given a list ofKpositive distinct coin denominations(V 1 , …, Vk)and a valueSas input how many ways can you make change forS. For example, with coins being{ 1 , 2 , 3 }the number of ways to get the value 4 is 4 as follows:{ 1 , 1 , 1 , 1 },{ 1 , 1 , 2 },{ 2 , 2 },{ 1 , 3 }. With coins being{ 2 , 5 , 3 , 6 }the number of ways to get the value 10 is 5 as follows: { 2 , 2 , 2 , 2 , 2 },{ 2 , 2 , 3 , 3 },{ 2 , 2 , 6 },{ 2 , 3 , 5 },{ 5 , 5 }. Find
Problem set 4, (14 October 2022 28 October 2022); Page 1
and prove the time complexity of your algorithm.Hint: LetOP T(i, j)denote the number of ways to make the valueiusing the coins fromV 1 toVj.
Problem 4 (Sprungli Bars) 30
Submit your code at the following Hackerrank link: https://www.hackerrank.com/cs5800-fall22-pset4. Problem Statement: IMPORTANT Please make sure to include the Hackerrank ID of your submission here.
You are given ann X mbar of chocolate and find the minimum number of horizontal or vertical cuts to produce blocks that are squares.
The input consists of one line withnandmseparated by a space.
Input Format:
6 7
Constraints: The output should consist only of square pieces.
Output Format: The output should consist of one line indicating the minimum number of cuts, and then one line per cut starting with the input. Each line includes whether it is either a H or V cut, the size of the component being cut written as “NxM”, then the symbols ” > ” and finally a pair of dimensions in the format “AxB CxD”.
In each line, the order of the components should be sorted by first index and then second index. The first line should indicate how the input piece is cut. The next set of lines (requiring as many lines as needed) should explain how the first non-square piece from the first line is handled, and then how the second non-square piece should be handled. Recursively, each set of lines should explain how the first and then the second piece is handled before continuing.
4 V 6×7 > 6×3 6x H 6×3 > 3×3 3x H 6×4 > 2×4 4x V 2×4 > 2×2 2x
Sample input : 6 7
Sample output :
4 V 6×7 > 6×3 6x H 6×3 > 3×3 3x H 6×4 > 2×4 4x V 2×4 > 2×2 2x
Problem set 4, (14 October 2022 28 October 2022); Page 2
