Northeastern University
CS5800 – Algorithms
Spring 2026
Problem Set #2
This Problem Set is due at 11:59 PM on Wednesday 2/25, and will be submitted on Canvas. This
Problem Set will be marked out of 15 and is worth 3% of the inal course grade.
There are four problems. Problems #1 and #2 and #3 are to be completed individually, while Problem
#4 is to be completed in your assigned groups.
Please type (or neatly handwrite) your solutions on standard 8.5 × 11 paper, with your name(s) at the
top of each solution. Submit four separate PDF iles on Canvas, with a separate PDF for each problem you
submit. Make sure you label your Problem Set #2 submissions appropriately - e.g. [Link], john
[Link], john [Link], and john [Link].
Given that the last problem is done in a group, your inal PDF ile will be identical to some of your
classmates. (For example, [Link] might be identical to [Link] and [Link]). This is
completely ine, and enables you to have a record of all of your submitted work in this course. However,
the video recording should be done individually as explained in the requirements of Problem 4. Students
should discuss the group problems with their groupmates and work out the solution together. Group
problems are not meant to be solved by one student and copied by other group members!
While a solution must be absolutely perfect to receive full marks, I will be generous in awarding partial
marks for incomplete solutions that demonstrate progress. Full marks cannot be given to answers
written without proper derivation and explanation, which means you should show the various
derivation steps and write sentences explaining your thought process.
So that there is no ambiguity, there are two non-negotiable rules. A violation of either rule constitutes
plagiarism and will result in you receiving an F for this course.
(a) If you meet with a classmate to discuss one of the Individual Problems, the articulation of your
thought process (i.e., what you submit to me), must be an individual activity, done in your own
words, away from others. Please remember that the solution-writing process is where so much of
your learning will occur in this course.
(b) This Problem Set has been designed to be challenging, because struggling through problems is how
we learn best. Your educational experience is cheapened by going online and inding the solution to
a problem; even using the Internet to look for a “small hint” is unacceptable. In return, the TAs and I
will be readily available during of ice hours, and upon request, I will happily post hints to any
questions you have on our class Piazza.
f
f
f
f
f
f
f
CS5800 – Problem Set #3 2
Problem #1 – INDIVIDUAL
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 inal 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 this question, we will use the Lomuto Partition Method from class. Also 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 = [18, 9, 27, 32, 26, 14, 21], showing how
eventually the algorithm outputs the sorted array [9,14,18,21,26,27,32]. Clearly show all of your
steps, and substeps.
f
CS5800 – Problem Set #3 3
(b) Determine an example 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.
CS5800 – Problem Set #3 4
(c) Determine an example input array with 7 elements for which Quicksort requires the maximum
number of total comparisons.
Clearly demonstrate why your input array requires the maximum number of comparisons.
CS5800 – Problem Set #3 5
Problem #2 – INDIVIDUAL
In addition to being a talented Computer Scientist, Flora has a successful side-business where she sells
lower bouquets.
Each of Flora’s lower bouquets consists of a certain number of red roses, with a minimum of 1 and a
maximum of 5. This is the pro it Flora makes from each of her bouquets, which is a function of the
number of red roses in that bouquet.
Roses 1 2 3 4 5
Pro it $5 $13 $24 $30 $35
For each positive integer n, let f (n) be the maximum pro it that Flora can make with n roses.
For example, if n = 10, Flora can make numerous bouquet combinations, including two 5-rose bouquets
(total pro it of $70), and a 4-rose bouquet with three 2-rose bouquets (total pro it of $69).
(a) Provide two different algorithms for calculating f (n): one using Recursion, and one using Dynamic
Programming. Explain why both algorithms are guaranteed to return the correct value of f (n).
(b) Using the Dynamic programming algorithm, determine the value of f(11). Draw a table showing
all combinations of bouquet you are checking, the selected combination that gives maximum pro it,
and the maximum pro it for bouquet sizes from 1 to 11.
f
f
f
f
f
f
f
f
f
CS5800 – Problem Set #3 6
(c) Explain what it means for an algorithm to exhibit optimal substructure and contain overlapping
subproblems. Show that your Dynamic Programming algorithm exhibits both properties and is
therefore much faster than your recursion-based algorithm.
(d) Consider the “recursion tree” and “subproblem graph” for our two algorithms. The case n = 4 is
illustrated below.
CS5800 – Problem Set #3 7
For the case n = 4, the recursion tree has 16 vertices and 15 edges, while the subproblem graph has 5
vertices and 10 edges.
For the case n = 11, determine the number of vertices and edges in the recursion tree, as well as
the number of vertices and edges in the subproblem graph for this problem. Clearly justify your
answers.
CS5800 – Problem Set #3 8
Problem #3 – INDIVIDUAL
What is the best number of total matches needed to rank 12 players?
Explain your work.
CS5800 – Problem Set #3 9
Problem #4 – GROUP
In this question, you will solve the following LeetCode problem on Dynamic Programming.
Maximum Product Subarray:
[Link]
programming
You may code your algorithm in the programming language of your choice. Your solution should use dynamic
programming.
You should provide the code, and the screenshot of you getting your solution accepted by LeetCode (screenshot
must show your name, date and acceptance).
Note: Problem 2 is a group question, so you should discuss it and solve it with your group members. Then
each student should record a video individually explaining in their own words the code of this Leetcode
problem and showing how the code solves an example of your choice. You can use Zoom to record your
video on the cloud as you did for Assignment 0, then copy in this solution the link and passcode of your
cloud recording.