Description
1.) Let us consider f´utbol players (or what Americans call “soccerers”) who are lined up in a row. We can refer to the players by where they are standing in the line – positions numbered 1, . . . , n. Each player is wearing a unique numbered jersey which has an integer (which can be positive, negative, or zero) printed on it, and all the players are lined up such that the numbers on their jerseys are increasing. For this question, your solutions must be in plain English and mathematical expressions (do not use pseudocode).
(a.) (15 points) Design a Divide & Conquer algorithm to determine if there is a position, i, such that the player standing in position i is wearing the jersey with the number i on it. Your algorithm must run in O(log n), and you must use the Master Theorem to prove your algorithm’s time complexity.
(b.) (15 points) Modify your algorithm from part (a.) to find the smallest value for i such that the player standing in position i is wearing the jersey with the number i (the modified algorithm should still use a Divide & Conquer approach). If this modified algorithm has the same time complexity as the one from part (a.), explain why; otherwise, use the Master Theorem to prove what the modified algorithm’s time complexity is.
(c.) (10 points) Provide a Divide & Conquer algorithm to find the total number of players standing in a position that matches their jersey’s number. You must prove why your algorithm finds the correct count and provide runtime analysis.
Solution:
We can again mimic our part (a) and part (b) solutions. Again, we first take what we can assume to be the array of players lined up and grab the middle element. We can then check if the index of this middle element matches the player number at that index. Assume we have a running count of matches. There are 3 cases we can hit:
2.) (30 points) Solve the following dynamic programming problems by creating and filling out tables using the algorithms shown in lecture.
(a.) (15 points) Find the longest increasing subsequence in the array [5, 6, 9, 7, 2, 13, 11, 8, 10, 17, 1, 3]. Your response must include: (1) the filled out DP table and (2) the longest increasing sub-sequence in the array and a brief explanation of how you used the table to find this result.
3.) (30 points) Given a list A of positive integers, you want to find the maximum sum of numbers such that no numbers in the sum are adjacent in the list A. Design a dynamic programming algorithm to solve this problem. For example, if the maximum sum contains the number at position 2 in the list, then the sum cannot contain the number at position 1 nor the number at position 3. The following are some examples of inputs and expected outputs:
(a.) Define the entries of your table in words, e.g. T [i] or T [i, j] is …
(b.) State your base cases and the recurrence for entries of your table in terms of smaller sub-problems. Briefly explain in words why it is correct.
Solution:
Solution:
(d.) Analyze the running time of your algorithm.
