Description
CS5800 – Algorithms Problem Set 1 Solution
Problem #1
Let f(n) and g(n) be two functions, defined for each positive integer n.
By definition
, f(n) = O(g(n)) if there exist positive constants c and n0 for which 0 ≤ f(n) ≤ cg(n)
for all integers n ≥ n0.
To prove that f(n) 6= O(g(n)) one must prove that no such constants c and n0 exist.
(a) Let f(n) = n
2 + 2n + 3. Prove that f(n) = O(n
2
) and f(n) 6= O(n).
(b) Let f(n) = n log n + 100n. Prove that f(n) = O(n log n) and f(n) 6= O(n).
NOTE: in this course, we will assume log n = log2 n = lg n.
(c) Let f(n) = 2n
2 + 4 and g(n) = 4n
2 + 2. Prove that f(n) = O(g(n)) and g(n) = O(f(n)).
(d) Let f(n) and g(n) be any two functions for which f(n) and g(n) are positive numbers, for each
integer n ≥ 1.
Prove or disprove: at least one of these two statements must be true:
f(n) = O(g(n)), g(n) = O(f(n)).
Clearly and carefully justify your answer.
CS5800,
Problem #2
Let f(n) and g(n) be two functions, defined for each positive integer n.
To prove that f(n) 6= O(g(n)) one must prove that no such constants c and n0 exist.
For each of these questions, show your step by step work
(a) Prove that 2n+1 = O(2n
).
(b) Prove or disprove: 22n = O(2n
)?.
(c) Let f(n) = lg(lgkn) and g(n) = lgk
(lgn). Prove which one is asymptotically larger.
(c) Let f(n) = lg3n and g(n) = lg9n. Prove the relationship between f(n) and g(n) in terms of upper
bound (big O), lower bound (Ω) and tight bound (Θ)
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #1 4
Problem #3
Consider an array, A, whose contents is integer values. Given a particular threshold value t, an event E
between indices i < j is a critical event if ai > t ∗ aj .
In this problem, write a full program that outputs the number of critical events for an arbitrary array of
integers and any arbitrary threshold value t.
(a) Submit the code of your working program (You can use any programming language). Note, you
need to upload your source file (TA’s will download and run the code- the code can be upload in
Canvas)
(b) Submit a screen capture showing that your program outputs correct values. You only need to repeat
over 2 different arrays running with 2 different threshold.
(c) Perform an analysis of your algorithm and report its time complexity.
CS5800,
Problem #4
Let {a1, a2, . . . , an} be an unsorted list of n numbers.
Bubble Sort is a well-known sorting algorithm that works as follows.
Iteration #1: Compare the first two numbers. If the first number is bigger than the second, then
swap the two numbers. Compare the second and third numbers, and swap them if necessary. Keep doing
this until we have compared the final two numbers. (After this iteration, can you see why the largest
number is guaranteed to be at the end?)
Iteration #2: Start from the beginning, comparing the first two numbers, and repeating the same process
as above. But this time we only look at the first n − 1 numbers, since we know the final number is already in the right position. (After this iteration, the two largest numbers are guaranteed to be at the end.)
We keep proceeding until the entire list has been sorted. Here is the pseudocode of Bubblesort.
for i = n down to 1
for j = 1 to i-1
if a[j]>a[j+1]
swap(a[j],a[j+1])
This sorting algorithm is known as Bubble Sort, because after each complete iteration the largest unsorted number “bubbles” to the end of the list. For example, if the initial list is {1, 7, 4, 5, 2}, we have
{1, 4, 5, 2, 7} after the first iteration, {1, 4, 2, 5, 7} after the second iteration, {1, 2, 4, 5, 7} after the third
iteration, and {1, 2, 4, 5, 7} after the fourth and final iteration. We now know that the list is sorted.
(a) Demonstrate the Bubble Sort algorithm on the input list {4, 3, 2, 1, 5}. Clearly show your steps.
(b) Let C(n) and S(n) be the total number of comparisons and swaps required by Bubble Sort when
the input list has n numbers. For example, in the list {1, 7, 4, 5, 2} above, Bubble Sort requires 10
comparisons and 5 swaps.
Suppose the input list is {n, n − 1, n − 2, . . . , 3, 2, 1}, where the numbers appear in reverse order. In this worst-case scenario, determine the exact formulas for C(n) and S(n). Clearly show all
of the steps in your proof.
(c) Determine a precise “loop invariant” for Bubble Sort, clearly stating your Initialization, Maintenance, and Termination statements. Prove that your loop invariant holds, clearly and carefully
justifying each step in your proof.
(d) Consider a random permutation of {1, 2, 3, . . . , n}. Determine an exact formula for the average
expected number of swaps required by Bubble Sort. Clearly and carefully justify your answer.
CS5800 – Algorithms Problem Set 3 Solution
Problem #1 (10 points)
Play one or more games of “Towers of Hanoi”, which you can do so on this website:
https://www.mathsisfun.com/games/towerofhanoi.html
There are three towers, and n disks. Your goal is to move all n disks from Tower 1 to Tower 3, but you
may never place a larger disk on top of a smaller disk.
For example, when n = 3, the game can be solved in 7 moves, which is the optimal result.
(a) Attach a screenshot of you winning the n = 4 game in exactly 15 moves. (No proof or explanation
is necessary – all you need to do is insert a .jpg image, just as I did above.)
(b) Let T(n) be the minimum possible number of moves required to solve the game when there are n
disks. For example, T(2) = 3 and T(3) = 7.
Clearly explain why T(4) = 15, showing it is possible to solve this game in exactly 15 moves
and proving why it is impossible to solve this game in 14 (or fewer) moves.
(c) Find a recurrence relation for T(n) and clearly and carefully explain why that recurrence relation
holds. Then solve the recurrence relation using any method of your choice to determine a formula
for T(n) that is true for all integers n ≥ 1.
(d) Substitute n = log(m) into your recurrence relation for T(n) above, and use the Master Theorem
to prove that T(n) = Θ(2n
). Briefly explain how and why your formula in part (c) is indeed Θ(2n
).
CS5800,
Problem #2 (20 points)
In this question, you will prove the Master Theorem in the special (and most important) situation when
f(n) = n
z
for some real number z.
This result enables us to determine tight asymptotic bounds for various recurrence relations, which
will help us tremendously in algorithm design and algorithm analysis.
If you can reproduce the proof of this result, then you will understand how the Master Theorem works
in all situations – e.g. when f(n) = 4n
3 + 2n
2
log n + 5n + 100 log n + 777. But for the purposes of this
problem, we will assume f(n) = n
z
.
Let x, y, z be real numbers for which T(1) = 1 and T(n) = xT(n/y) + n
z
.
(a) If z < logy(x), prove that T(n) = Θ(n
logy(x)
).
(b) If z = logy(x), prove that T(n) = Θ(n
logy(x)
logy n).
(c) If z > logy(x), prove that T(n) = Θ(n
z
).
(d) Some of you have taken a course in Linear Algebra, a core course in an undergraduate mathematics
curriculum. In this course, students learn how to multiply two n by n matrices, and one can easily
design an algorithm to perform matrix multiplication, running in Θ(n
3
) time.
In 1969, Volker Strassen developed a recursive method to perform matrix multiplication, where
the running time T(n) can be given by the recurrence relation T(n) = 7T(n/2) + n
2
.
Using any of the results in (a), (b), or (c), determine the running time of Strassen’s Algorithm
and show that it is faster than the standard algorithm that runs in Θ(n
3
) time.
Note: if you are unable to prove (a), (b), (c) in its general form, you are welcome to instead solve the
following simplified version of the problem, where you let y = 2 and x = 16, and prove the result for z = 3
in part (a), z = 4 in part (b), and z = 5 in part (c). If your proof is correct, you will be given 10 points
(i.e. instead of the 15 points for the original a,b,c) for solving the simplified version of the problem.
CS5800 – Algorithms Problem Set 4 Solution
Problem #1
Quicksort is a powerful divide-and-conquer sorting algorithm that can be described in just four lines of
pseudocode.
The key to Quicksort is the PARTITION(A, p, r) procedure, which inputs elements p to r of array A,
and chooses the final element x = A[r] as the pivot element. The output is an array where all elements
to the left of x are less than x, and all elements to the right of x are greater than x.
In class, we saw that there are very many techniques to partition the array. One nice technique covered
in the book was invented by Nico Lomuto (See page 171 of the class textbook). You can also watch a
quick youtube video here: https://www.youtube.com/watch?v=86WSheyr8cM. In this question, we will
use the Lomuto Partition Method. Please assume that the pivot is always the last (right-most) element
of the input array.
For example, if A = [2, 8, 7, 1, 3, 5, 6, 4], then the pivot element is x = A[8] = 4, and PARTITION(A, 1, 8)
returns the array [2, 1, 3, 4, 7, 5, 6, 8]. We then run PARTITION on the sub-arrays [2, 1, 3] and [7, 5, 6, 8].
(a) Demonstrate the Quicksort algorithm on the input array A = [3, 1, 5, 7, 6, 2, 4], showing how eventually the algorithm outputs the sorted array [1, 2, 3, 4, 5, 6, 7]. Clearly show all of your steps.
(b) When PARTITION is called on an array with n elements, we require n − 1 comparisons, since we
must compare the pivot element to each of the other n − 1 elements.
If the input array is A = [1, 2, 3, 4, 5, 6, 7], show that Quicksort requires a total of 21 comparisons.
(c) Determine an input array with 7 elements for which Quicksort requires the minimum number of
total comparisons.
Clearly demonstrate why your input array achieves the minimum number of comparisons, and
explain why there cannot exist a 7-element array requiring fewer comparisons than your array.
(d) Let A be an array with n = 2k − 1 elements, where k is some positive integer. Determine a formula
(in terms of n) for the minimum possible number of total comparisons required by Quicksort, as
well as a formula for the maximum possible number of total comparisons required by Quicksort.
Use your formulas to show that the running time of Quicksort is O(n log n) in the best case and
O(n
2
) in the worst case.
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #4 3
Problem #2
There are are about 44 LeetCode problems on Divide and Conquer techniques.
In this question, you will create a mini-portfolio consisting of two (two) LeetCode problems on Divide and Conquer, chosen from the following website.
Note that you can work with a partner to code up the problem but each person MUST do their own
analysis of the problem
https://leetcode.com/tag/divide-and-conquer/
As always, you may code your algorithms in the programming language of your choice.
Here is how your mini-portfolio will be graded.
(i) (5 points ) For each of the problems you are including in your mini-portfolio, provide the problem
number, problem title, difficulty level, and the screenshot of you getting your solution accepted by
LeetCode.
Note that the total points is 5 points for each problem and those points is dependent on the difficult
level – for each easy problem will be awarded 3 points, each medium problem will be awarded 4
points, and each hard problem will be awarded 5 points.
You may submit as many problems as you wish but you will receive a maximum of 5 points for
each problem and a total of 10 for the two problems.
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 points) For one of the problems you are including in your mini-portfolio, provide an analysis of
the run time of your algorithm. Be careful to only analyse what you created (i.e. your own code)
and not a general solution.
(ii) (5 points) For one of the problems you are including in your mini-portfolio, 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.
CS5800 – Algorithms Problem Set 5 Solution
Problem #1
A complete binary tree of height h has “no holes”: i.e reading from top-bottom and left-to-right, every
node exists. An almost complete binary tree has every node until the last row, which is allowed to stop
early.
Figure 1: complete (perfect) binary tree (left) and almost complete binary tree (right)
(a) Prove by mathematical induction that a complete binary tree with height, h, contains precisely
2
h+1 − 1 nodes
(b) How many leaves does an almost complete binary tree of height, h, have? Give the smallest and
largest possible values, and explain. Note, by definition every complete binary tree is almost complete tree.
(c) The diameter of a tree or a graph is the maximum distance (length of the longest path) between
nodes. Whats the diameter of an almost complete binary tree of height, h. Give the smallest and
largest possible values and explain
(d) Suppose that we “reroot” a complete binary tree of height, h, by designating one of the erstwhile
leaves as the root. What is the height of the rerooted tree?
(e) What is the diameter of a complete binary tree rerooted at one of its leaves?
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #5 3
Problem #2
A binary heap is called a max heap if it has the property that for every node i other than the root, the
value of the node is at most the value of its parent.
Below is an example of a max heap with 10 nodes (i.e., 10 elements), presented both as a binary tree and
as an array.
Figure 2: Max Heap with 10 nodes
(a) The height of a heap is defined to the number of edges on the longest downward path from the root
node to a leaf node. Thus, in the example above, the height of the heap is h = 3.
If a (binary) heap has height h = 6, determine the minimum number and maximum number of
elements that can be in this heap. Clearly justify your answer.
(b) Consider an unsorted array of n elements. Recall that the Heapsort Algorithm consists of two
parts: first we run BUILD-MAX-HEAP to convert our input array into a max heap, and then we
run MAX-HEAPIFY n times to generate the n elements of our sorted array.
Demonstrate the Heapsort Algorithm on the input array [5, 2, 1, 7, 6, 3, 4]. Clearly show your steps.
(c) In part (b) above, you should have noticed that after the i = 2 iteration of MAX-HEAPIFY, your
heap was [5, 3, 4, 2, 1, 6, 7]. Notice how the first n − i elements form a max heap, and the last i
elements are sorted and are the i largest elements of the array.
Show that this property holds for any max heap with n elements. Specifically, prove that for
all 1 ≤ i ≤ n, after the i
th iteration of MAX-HEAPIFY, the first n − i elements form a max heap,
and the last i elements are sorted and are the i largest elements of the array.
(d) Let P be a permutation of the first 7 positive integers. Sometimes this permutation is a max heap;
examples include [7, 6, 5, 4, 3, 2, 1], [7, 6, 4, 2, 5, 1, 3], [7, 5, 6, 2, 4, 3, 1], and [7, 3, 6, 2, 1, 4, 5].
If P is a randomly-chosen permutation of [1, 2, 3, 4, 5, 6, 7], determine the probability that it is
a max heap. Clearly and carefully justify your answer.
CS5800 – Algorithms Problem Set 6 Solution
Problem #1
Define Kn to the graph on n vertices, where each pair of vertices is connected by an edge. Kn is known
as the complete graph on n vertices.
To illustrate, here are the complete graphs Kn, for n = 2, 3, 4, 5, 6, 7.
(a) Draw the complete graph K10, and determine the total number of edges in this graph. Briefly
explain how you calculated this total.
(b) The complete graph Kn has exactly 120 edges.
Determine the value of n. Clearly justify your answer.
(c) Sometime in 2021 (or 2022), a group of CS5800 students meet at the Northeastern campus for the
first time, to have a post-Covid celebration party. Each pair of students shakes hands.
Unfortunately, Paul walks in late. As a result, Paul is only able to shake hands with some of
the other students at the celebration party.
If there are exactly 42 handshakes in total, determine the number of hands that Paul shook. Clearly
and carefully justify your answer.
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #6 3
Problem #2
Consider this binary tree, where each vertex is labelled with a positive integer. The root vertex is 1.
For all positive integers k ≥ 1, vertex k has two children: 2k (Left) and 2k + 1 (Right).
(a) In your own words, describe how Breadth-First Search (BFS) and Depth-First Search (DFS) work.
Does one search algorithm always reach the destination faster than the other? Explain.
(b) Suppose we want to determine a path from vertex 1 (start vertex) to vertex 10 (end vertex).
Using BFS, determine the order in which the vertices will be visited. Using DFS, determine the
order in which the vertices will be visited. Briefly explain your answers.
(c) Suppose that we extend this binary tree to infinitely many levels, so that each vertex k has two
children: 2k (Left) and 2k + 1 (Right).
The path from vertex 1 to vertex 10 can be described by a sequence of Left and Right moves,
namely Left, Right, Left.
Consider the path from vertex 1 to vertex 2021. Determine the sequence of Left and Right moves
for this path. Clearly justify your answer.
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #6 4
Problem #3
In this question, you will create a mini-portfolio consisting of any two LeetCode problems on Graphs,
chosen from the four problems below:
https://leetcode.com/problems/clone-graph/
https://leetcode.com/problems/is-graph-bipartite/
https://leetcode.com/problems/find-the-town-judge/
https://leetcode.com/problems/find-if-path-exists-in-graph/
As always, you may code your algorithms in the programming language of your choice.
Here is how your mini-portfolio will be graded.
There will be a total of 10 points for any of the combination of problems in your 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 (10 points).
Note that you are allowed to work with Teammates on this part of the problem. Make
sure you write all names of the collaborators.
CS5800 – Algorithms Problem Set 7 Solution
Problem #1 (15 points)
In this question you will explore Dijkstra’s Single Source Shortest Path algorithm
(a) Consider the following weighted undirected graph with 7 vertices and 11 edges.
Apply Dijkstra’s Algorithm on the graph above, to determine the shortest distance from vertex G
to each of the other six vertices (A, B, C, D, E, F). Clearly show all of your steps.
(b) Now suppose we change the weight of edge EF from +8 to −8. What happens?
Using this example, explain why Dijkstra’s Algorithm can produce incorrect outputs when one
or more edges is negative.
(c) Determine a precise Loop Invariant for the Dijkstra’s Algorithm, clearly stating your Initialization, Maintenance, and Termination statements. Prove that your loop invariant holds, clearly and
carefully justifying each step in your proof.
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #7 3
Problem #2 (20 points)
In this question you will explore algorithms that generate Minimum-Weight Spanning Trees.
(a) Let G be a graph with V vertices and E edges. One can implement Kruskal’s Algorithm to run in
O(E log V ) time, and Prim’s Algorithm to run in O(E + V log V ) time.
If G is a dense graph with an extremely large number of vertices, determine which algorithm
would output the minimum-weight spanning tree more quickly. Clearly justify your answer.
(b) Consider eight points on the Cartesian two-dimensional x-y plane.
For each pair of vertices u and v, the weight of edge uv is the Euclidean (Pythagorean) distance
between those two points. For example, dist(a, h) = √
4
2 + 12 =
√
17 and dist(a, b) = √
2
2 + 02 = 2.
Using the algorithm of your choice, determine one possible minimum-weight spanning tree and
compute its total distance, rounding your answer to one decimal place. Clearly show your steps.
(c) Because many pairs of points have identical distances (e.g. dist(h, c) = dist(h, b) = dist(h, f) =
√
5), the above diagram has more than one minimum-weight spanning tree.
Determine the total number of minimum-weight spanning trees that exist in the above diagram.
Clearly justify your answer.
(d) Suppose the n points are situated so that each of the
n
2
!
=
n(n − 1)
2
distances are distinct positive
numbers.
Prove that graph G has only one minimum-weight spanning tree. Clearly explain each step in
your proof.
CS5800, Fall 2023 Semester, Jonathan Mwaura – Problem Set #7 4
Problem #3 (15 points)
There are over 200 LeetCode problems on Greedy Algorithms.
In this question, you will create a mini-portfolio consisting of LeetCode problems on Greedy Algorithms, chosen from the following website.
https://leetcode.com/list/50f6p33i/
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 10 points for any of the combination of problems in your 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 (10 points).
Note that you are allowed to work with Teammates on this part of the problem.
Make sure you write all names of the collaborators.
To get the total points for this question, you could submit any of the following options:
• 4 Easy problems
• 2 Easy problems and 1 either hard or medium
• 2 either hard or medium problems or 1 hard and 1 Medium
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 points) For one of the problems you are including in your mini-portfolio, 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.
I ask you to only include new problems that you will solve in the next seven days. However, I will
make an exception if you previously solved a problem in an inefficient way (but still got the solution accepted by LeetCode) and then found a new way to solve the same problem using the methods uncovered
in this module on Greedy Algorithms.
CS5800 – Algorithms Problem Set 8 Solution
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).
CS5800
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%.)
CS5800,
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.
