[SOLVED] Cs5800 – algorithms problem set #8 problem #1 – 20 points the longest subsequence problem is a well-studied problem in computer science, where given a sequence

CS5800 – Algorithms
Problem Set #8
Problem #1 – 20 points
The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence
of distinct positive integers, the goal is to output the longest subsequence whose elements appear from
smallest to largest, or from largest to smallest.
For example, consider the sequence S = [9, 7, 4, 10, 6, 8, 2, 1, 3, 5]. The longest increasing subsequence
of S has length three ([4, 6, 8] or [2, 3, 5]), and the longest decreasing subsequence of S has length five
([9, 7, 4, 2, 1] or [9, 7, 6, 2, 1]).
And if we have the sequence S = [531, 339, 298, 247, 246, 195, 104, 73, 52, 31], then the length of the longest
increasing subsequence is 1 and the length of the longest decreasing subsequence is 10.
(a) Find a sequence with nine distinct integers for which the length of the longest increasing subsequence is 3, and the length of the longest decreasing subsequence is 3. Briefly explain how you
constructed your sequence.
(b) Let S be a sequence with ten distinct integers. Prove that there must exist an increasing subsequence of length 4 (or more) or a decreasing subsequence of length 4 (or more).
Hint: for each integer k in the sequence you found in part (a), define the ordered pair (x(k), y(k)),
where x(k) is the length of the longest increasing subsequence beginning with k, and y(k) is the
length of the longest decreasing subsequence beginning with k. You should notice that each of your
ordered pairs is different. Explain why this is not a coincidence, i.e., why it is impossible for two
different numbers in your sequence to be represented by the same ordered pair (x(k), y(k)).
(c) In class, we unpacked the Longest Common Subsequence (LCS) problem, where we showed that if
our two sequences have size n, then our Dynamic Programming algorithm runs in O(n
2
) time.
Let S be your 9-integer sequence from part (a), and let S
∗ be the same sequence where the 9
numbers are sorted from smallest to largest. Using the LCS algorithm from class, determine the
length of the longest common subsequence of S and S
∗
. (Your answer will be 3. Do you see why?)
Now prove the general case. Specifically, if S is a sequence of n distinct integers, prove that the
length of the longest increasing subsequence of S must equal the length of the longest common
subsequence of S and S
∗
, where S
∗
is the sorted sequence of S.
(d) The results of part (c) immediately gives us an O(n
2
) time algorithm to determine the length of
the longest increasing subsequence of an input sequence S with n distinct integers. But this is
(unsurprisingly) not the optimal algorithm. Your goal is to improve this result.
Given an input sequence S with n distinct integers, design a linearithmic algorithm (i.e., running in O(n log n) time) to output the length of the longest increasing subsequence of S. Clearly
explain how your algorithm works, why it produces the correct output, and prove that the running
time of your algorithm is O(n log n).
If you are unable to come up with an O(n log n) algorithm, you will receive partial credit for designing an O(n
2
) algorithm that is different from the one described in part (c).

Problem #2 – 20 points
For those of you who follow professional sports, you will know that there are many team sports that are
clock-based, i.e., the game lasts a fixed amount of time and the winner is the team that scores the most
points or goals during that fixed time.
In all of these sports (e.g. basketball, football, soccer, hockey), you will notice that near the end of
the game, the team that is behind plays very aggressively (in order to catch up), while the team that
is ahead plays very conservatively (a practice known as “stalling”, “stonewalling”, and “killing the clock”).
In this problem we will explain why this strategy makes sense, through a simplified game that can
be solved using Dynamic Programming. This game lasts n rounds, and you start with 0 points. You
have two fair coins, which we will call X and Y . The number n is known to you before the game starts.
In each round, you select one of the two coins, and flip it. If you flip coin X, you gain 1 point if it
comes up Heads, and lose 1 point if it comes up Tails. If you flip coin Y , you gain 3 points if it comes up
Heads, and lose 3 points if it comes up Tails. After n rounds, if your final score is positive (i.e., at least
1 point), then you win the game. Otherwise, you lose the game.
All you care about is winning the game, and there is no extra credit for finishing with a super-high
score. In other words, if you finish with 1 point that is no different from finishing with 3n points. Similarly, every loss counts the same, whether you end up with 0 points, -1 point, -2 points, or -3n points.
Because you are a Computer Scientist who understands the design and analysis of optimal algorithms,
you have figured out the best way to play this game to maximize your probability of winning. Using this
optimal strategy, let pr(s) be the probability that you win the game, provided there are r rounds left to
play, and your current score is s. By definition, p0(s) = 1 if s ≥ 1 and p0(s) = 0 if s ≤ 0.
(a) Clearly explain why p1(s) = 0 for s ≤ −3, p1(s) = 1
2
for −2 ≤ s ≤ 1, and p1(s) = 1 for s ≥ 2.
Explain why you must select X if s is 2 or 3, and you must select Y if s is -2 or -1.
(b) For each possible value of s, determine p2(s). Clearly explain how you determined your probabilities, and why your answers are correct. (Hint: each probability will be one of 0
4
,
1
4
,
2
4
,
3
4
, or 4
4
.)
(c) Find a recurrence relation for pr(s), which will be of the form pr(s) = max( ??+??
2
,
??+??
2
). Clearly
justify why this recurrence relation holds.
From your recurrence relation, explain why the optimal strategy is to pick X when you have certain
positive scores (be conservative) and pick Y when you have certain negative scores (be aggressive).
(d) Compute the probability p100(0), which is the probability that you win this game if the game lasts
n = 100 rounds. Use Dynamic Programming to efficiently compute this probability.
For a bonus mark, determine the limit of pn(0) as n → ∞, and clearly prove why your answer
is correct. (Shockingly, or perhaps not shockingly, the answer is way more than 50%.)

Problem #3 – 20 points
There are over 200 LeetCode problems on Dynamic programming. In this question, you will create a
mini-portfolio consisting of Three (3) LeetCode problems on Dynamic Programming Algorithms, chosen
from the following website.
https://leetcode.com/tag/dynamic-programming/
As always, you may code your algorithms in the programming language of your choice.
Here is how your mini-portfolio will be graded.
(i) There will be a total of 15 points for all the problems that your are including in the mini-portfolio:
For each of these,
• Provide the problem number, problem title, difficulty level, and the screenshot of you getting
your solution accepted by LeetCode
• Source code used – this can be uploaded in Canvas
• Provide a written analysis of the problem investigating the time complexity of your algorithm
Note: Leetcode has three different problem variations: Easy, Medium, Hard
For this problem, the following different problem combinations will get the total points:
• 5 Easy problems
• 4 Medium problems
• 3 Hard problems
• 3 Easy and 1 Hard problem
• 4 Easy and 1 Medium problem
• 3 medium and 1 Hard problem
• 2 medium and 2 Hard problem
• 2 Easy and 1 medium and 1 Hard problem

You will get full credit for any correct solution accepted by LeetCode, regardless of how well your
runtime and memory usage compares with other LeetCode participants.
(ii) (5 marks – INDIVIDUAL WORK) For one of the problems you are including in your miniportfolio, explain the various ways you tried to solve this problem, telling us what worked and what
did not work. Describe what insights you had as you eventually found a correct solution. Reflect on
what you learned from struggling on this problem, and describe how the struggle itself was valuable
for you.
The choice of problems is yours, though you may only include problems that took you a minimum of 30
minutes to solve.