1 Easy Questions. 5 points each. For each of the problems in the easy section it is enough to describe in English the idea of your algorithm, define the memo table, write the base case and the recursive step to fill the table, and analyze the run time. No need for pseudo code Given a string s of length n, design an algorithm. that outputs the smallest number k such that s = w1w2wk where each wi is a palindrome. In other words, find the smallest k such that s can be written as a concatenation of k palindromes. For the definition of a palindrome see practice problems. For example if s-"add" then the algorithm should output k 2 since we can take w-"a" and w2"dd". On the other hand, if s "ada", then the algorithm should output k-1 Given two strings of length n and m, design an algorithm that outputs the length of the longest common substring of the two strings. If A[1,...n is the array representing a string, then any contiguous chunk Ali,.,j] is a substring of A Given an array A[1,... , n] of integers, design a dynamic programming algorithm running in time O(n) to find indices i, j such that the subarray Ali,...,j] has the maximum sum. You are given a set of n non-negative integers, and a target integer K. You need to find out if there exists a subset of the n integers that adds up to K. Design a dynamic programming algorithm for this problem that runs in time O(nK) e Given a string of length n, a subsequence is any non empty subset of characters read from left to right. For example, if A-atc then a, t, c, at, tc, ac, atc are all subsequences of A. Given two strings of length n, m, design an algorithm that outputs the length of the longest common subsequence (LCS) of the two strings. Modify the algorithm for the longest common subsequence (LCS) problem that you designed above such that it runs in time O(nm) but only uses O(min(n, m)) space 1 Easy Questions. 5 points each. For each of the problems in the easy section it is enough to describe in English the idea of your algorithm, define the memo table, write the base case and the recursive step to fill the table, and analyze the run time. No need for pseudo code Given a string s of length n, design an algorithm. that outputs the smallest number k such that s = w1w2wk where each wi is a palindrome. In other words, find the smallest k such that s can be written as a concatenation of k palindromes. For the definition of a palindrome see practice problems. For example if s-"add" then the algorithm should output k 2 since we can take w-"a" and w2"dd". On the other hand, if s "ada", then the algorithm should output k-1 Given two strings of length n and m, design an algorithm that outputs the length of the longest common substring of the two strings. If A[1,...n is the array representing a string, then any contiguous chunk Ali,.,j] is a substring of A Given an array A[1,... , n] of integers, design a dynamic programming algorithm running in time O(n) to find indices i, j such that the subarray Ali,...,j] has the maximum sum. You are given a set of n non-negative integers, and a target integer K. You need to find out if there exists a subset of the n integers that adds up to K. Design a dynamic programming algorithm for this problem that runs in time O(nK) e Given a string of length n, a subsequence is any non empty subset of characters read from left to right. For example, if A-atc then a, t, c, at, tc, ac, atc are all subsequences of A. Given two strings of length n, m, design an algorithm that outputs the length of the longest common subsequence (LCS) of the two strings. Modify the algorithm for the longest common subsequence (LCS) problem that you designed above such that it runs in time O(nm) but only uses O(min(n, m)) space
