Description
Algorithms Homework 1 CS5800 Solved Assignment with Solution
Problem #1 – Happy Question!
Hello! I’m the Happy Question, a unique puzzle in your journey of complexity and code. You earn 8
marks just by reading me! Isn’t that a delightful linear algorithmic problem to solve?
In the world of algorithms, where efficiency and speed often reigns supreme, it’s easy to get caught
up in the pursuit of optimal solutions. But what about the journey itself? Sometimes, the most rewarding experiences aren’t about the final destination, but the process we embark upon. This concept, known
as delayed gratification, is the idea of forgoing immediate pleasure for a larger, more satisfying reward in
the future.
Invitation: Before we dive into our algorithmic puzzle, let’s explore the idea of delayed gratification a bit further. Take a few minutes to read about the ”Marshmallow Experiment” here: https:
//jamesclear.com/delayed-gratification
Puzzle: Now, let’s consider the world of algorithms through the lens of delayed gratification. Can
you identify and describe an algorithm that:
• Prioritizes immediate gratification: Perhaps an algorithm that seeks a quick solution, even if it’s
not the most efficient or accurate.
• Embraces delayed gratification: An algorithm that might take more time or computational resources
upfront, but ultimately leads to a superior outcome.
Wondering what should you submit for this question? Nothing!
Remember, in the midst of searching for optimal solutions, it’s okay to pause and appreciate the
journey. After all, in Algorithm Land, the Happy Question reminds us that sometimes, being
present and engaged is a reward in itself!
CS5800
Problem #2 – Hybrid Sort
Background In this assignment, we’ll explore an advanced hybrid sorting algorithm that combines
the strengths of multiple sorting techniques to achieve both efficiency and guaranteed worst-case
performance. This algorithm is used in some standard library implementations of sorting functions.
Algorithm Description:
The algorithm works as follows:
– Start with a divide-and-conquer approach similar to Quicksort.
– Track the recursion depth during the sorting process.
– If the recursion depth exceeds a certain threshold (typically 2 log2
(n), where n is the number
of elements), switch to a heap-based sorting method.
– For small subarrays (typically less than 16 elements), use an insertion-based sorting method.
Note: You don’t need to implement Insertion sort, Quicksort or Heapsort from scratch.
(a) Implement the described hybrid sorting algorithm in a programming language of your choice
(Preferably Python). Include helper functions for the divide-and-conquer approach, heapbased sorting, and insertion-based sorting.
(b) Analyze the time complexity of this hybrid algorithm. Discuss best-case, average-case, and
worst-case scenarios.
(c) Conduct an empirical analysis:
– Generate arrays of various sizes (e.g., 100, 1000, 10000, 100000 elements) with random,
nearly sorted, and reverse sorted data.
– Compare the performance of this hybrid algorithm with standard Quicksort, Heapsort,
and Insertion Sort). Present your results in tables or graphs.
(d) Briefly discuss general trends and observation from (c) and suggest one or two practical realworld applications where this hybrid algorithm might be particularly useful.
CS5800,
Problem #3 – Guess My Number
Play one or more games of “Guess My Number”, which you can do so on this website:
https://www.mathsisfun.com/games/guess_number.html
What you will do is change the Range of numbers from 1 to 1000, and then click on Start. The
computer will pick a random integer between 1 and 1000, with each number equally likely to be
chosen.
After each guess, the computer will tell you whether your guess was correct, whether it was too high,
or whether it was too low. The game stops when you have correctly guessed the computer’s number.
For example, when I did this game, I was able to get the computer’s number in 10 guesses.
(a) Attach a screenshot of you winning this game in at most 10 guesses. (No proof or explanation
is necessary – all you need to do is insert a .jpg image, just as I did above.)
(b) Suppose the range of numbers is between 1 and n, where n is a positive integer. If n = 15,
prove that the game can always be won in at most 4 guesses, no matter what the computer’s
number is. Clearly explain how your “guessing algorithm” works.
(c) Let T(n) be the maximum number of guesses required to correctly identify an integer between
1 and n. For example, you have shown above that T(15) = 4. Determine a recurrence relation
for T(n), and apply the Master Theorem to show that T(n) = Θ(log n).
(d) For each integer n, let A(n) be the average number of guesses required to correctly guess the
computer’s number, where each of the target numbers from 1 to n is equally likely to be chosen.
For example, you can show that A(15) = 49
15 using your algorithm from part (b).
Determine the exact value of A(1023), carefully justifying all of the steps in your calculation.
CS5800,
Problem #4 – Tree recurrence
(a) Draw the recurrence tree for the following recurrence formula (only the first three levels):
(b) Write the recurrence for the following recurrence tree:
(c) 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 such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n0.
Determine if the following statements are correct or incorrect, and briefly justify your answer
in each case.
– 4
n = O(2n
)
– n
1000 = O(2n
)
CS5800,
Problem #5 – Divide and Conquer: Optimal Timing in Investment
Problem:
An investment company has an AI-powered model that predicts stock prices for n consecutive days.
Given these predictions, determine the maximum possible profit that can be made by buying and
selling a single stock. Note: Due to potential tax implications associated with day trading, we
assume that only a single purchase and sale are allowed. Your solution should just return the maximum possible profit.
Sample Input: [100, 115, 90, 120, 85, 130]
Sample Output: 35
Explanation: The maximum profit can be achieved by buying at 85 and selling at 130, resulting in
a profit of 130 – 85 = 35.
(a) Naive Approach: Describe (single paragraph) the idea and logic behind your brute force
solution and its time complexity.
(b) Pseudocode: Now, design a DAC algorithm and provide detailed pseudocode for your algorithm, ensure that the pseudocode is comprehensive, and add comments when necessary to
enhance its readability. Design a O(n log n) DAC algorithm for this problem to qualify for full
credit.
(c) Algorithm Analysis: Analyze the time complexity of your proposed DAC algorithm from
part (b). Write the recurrence relation for your algorithm and apply the Master Theorem to
determine its complexity.
CS5800,
Extra Challenge Question (practice ONLY )
Closest Pair Problem in Supply Chain Management
Attention: This question is crafted for students seeking an extra challenge.
You’re welcome to skip this and submission is NOT required.
In our class, we explored the standard closest pair problem in a 2D plane. Now, let’s consider a
practical application in the field of supply chain management. Imagine a scenario with numerous
suppliers and vendors dispersed across a geographical region. These suppliers might be factories
or farms producing goods, while vendors could be markets or retail stores requiring these goods.
A key goal in this context is to enhance supply chain efficiency by reducing transportation costs
and time. Minimizing travel distance is crucial not only for cost reduction but also for lowering
environmental impact.
(a) Modified Algorithm: Discuss how you would modify the standard closest pair algorithm to
address the needs of the stakeholders in the scenario described above. Focus on the aspects
of the algorithm that would be adapted or enhanced to optimize matching between suppliers
and vendors, taking into account factors like distribution of locations and varying supply and
demand.
(b) Algorithm Analysis: Analyze the time complexity of your proposed algorithm from part a.
Write the recurrence relation for your algorithm and apply the Master Theorem to determine
its complexity. Compare this with the complexity of the standard closest pair algorithm, and
explain any differences or similarities.
(c) Pseudocode: Provide a detailed pseudocode for your modified algorithm, similar to the
one discussed in class. Ensure that the pseudocode is comprehensive and reflects all the
modifications you proposed in part a. Highlight any steps that specifically address the supply
chain scenario.
Algorithms Homework 2 CS5800 Solved Assignment with Solution
Problem #1 – A New Sorting Algorithm
Two Northeastern University students Elizabeth and James have proposed the following new sorting
algorithm:
(a) Prove that the call NEW-SORT(A, 1, n) correctly sorts the input array A[1 : n], where n represent
length of A.
(b) Give a recurrence for the worst-case running time of NEW-SORT and a tight asymptotic Θ-notation)
bound on the worst-case running time.
(c) Compare the worst-case running time of NEW-SORT with that of insertion sort, merge sort, heapsort, and quicksort. Do the students deserve a straight A in the course?
CS5800 Algorithms Homework 1 Solutions – Solved
Problem #2 – Players′ Rating
In our Algorithms class, 8 students are avid chess players.
Each of these 8 students has a “rating” that measures their quality as a chess player. The higher
the rating, the better they are.
For the purposes of this problem, assume that everyone keeps their chess rating a private secret; however,
when two players have a chess match, the person with the higher rating wins 100% of the time.
These highly-competitive students have asked you to create various comparison-based algorithms to resolve some questions they have about their relative chess ratings.
For each of these questions, your algorithm will be a sequence of matches (e.g. A vs. B, C vs. D)
that will solve the problem in the most efficient way.
(a) The students want you to sort them according to their chess rating, from best (1st) to worst (8th).
Prove that there does not exist an algorithm that is guaranteed to solve this problem in 15 or
fewer matches.
(b) The students want you to determine which player has the highest chess rating and which player has
the lowest chess rating.
Create an algorithm that is guaranteed to solve this problem in 10 matches, and clearly explain why
there does not exist an algorithm that is guaranteed to solve this problem in 9 or fewer matches.
(c) The students want you to determine which player has the highest chess rating and which player has
the second-highest chess rating.
Create an algorithm that is guaranteed to solve this problem in 9 matches, and clearly explain
why there does not exist an algorithm that is guaranteed to solve this problem in 8 or fewer matches.
Problem #3 – Counting Sort and Stability
Let A be an array of n non-negative integers, where the maximum element is k.
If k = O(n), then Counting Sort is an O(n) time algorithm to sort our array A. This is a significant improvement over comparison-based sorting algorithms which are at best O(n log n).
(a) Let A = [4, 5, 0, 1, 3, 4, 3, 4, 3, 0, 3]. Walk through each step of the Counting Sort algorithm on this
input array, to produce the correct output of [0, 0, 1, 3, 3, 3, 3, 4, 4, 4, 5].
(b) We say that a sorting algorithm is stable provided that whenever there are two equal elements (x
and y), where x appears before y in the input, then x must appear before y in the sorted output.
For example, in the above input array A, if we highlight the three numbers marked 4 using the
colors red, white, and blue (in that order), then in the sorted output array, our 4’s will be listed
red, white, and blue (in that order).
Clearly explain why the Counting Sort algorithm is stable.
(c) Consider Quicksort and Heapsort. For each of these two sorting algorithms, explain whether the
algorithm is stable. If the answer is YES, briefly explain why. If the answer is NO, provide a simple
counterexample to show that stability is not guaranteed.
Problem #4 – Build a Portfolio on Dynamic Programming
LeetCode (www.leetcode.com) is a popular website for Northeastern MSCS students, especially when
preparing for job interviews.
https://leetcode.com/problemset/algorithms/
There are over a thousand “coding challenges” from which students can practice and improve their skills
in Algorithm Analysis and Design, and the website supports numerous programming languages, including
C, Java, and Python.
In this Programming Project, you will create a portfolio consisting of TWO LeetCode problems on
Dynamic Programming you will solve over the next two weeks. You can choose ANY set of TWO problems from the following site (click on ”Dynamic Programming” to filter the results), but see the following
note first.
Important Note: You can pick anything excluding the DP problems except the problems we will
discuss in class during Week 5 − 6:
• Fibonacci or Climbing Stairs
– Leetcode 70. Climbing Stairs
– Leetcode 509. Fibonacci Number
• Rod Cutting
– Leetcode 1547. Minimum Cost to Cut a Stick (similar problem)
• Longest Common (or Increasing) Sub-sequence
– Leetcode 1143. Longest Common Subsequence
– Leetcode 300. Longest Increasing Subsequence
• Activity-Selection
– Leetcode 435. Non-overlapping Intervals (closest equivalent)
• Knapsack or Coin Change
– Leetcode 322. Coin Change
– Leetcode 416. Partition Equal Subset Sum (0/1 Knapsack variant)
• House Robber
– Leetcode 198. House Robber
NOTE: To maximize your learning and problem-solving skills, we encourage you to explore these concepts through fresh challenges. The idea is for you to get more exposure to problem-solving, so for your
own benefit, please stay away from these problems!
[Read Carefully] This HW offers a lot of flexibility but there are four important rules:
(I) If the problem took you less than 30−40 minutes to solve, you may not include it in your portfolio.
(Since then the question was an exercise for you, rather than a problem or a challenge.)
(II) You may only include problems you have solved after Sep 22, 2024.
(III If you click on the LeetCode “Solution” or “Discuss” button before you solve the problem or look at
any online resources for hints to solve a LeetCode problem, especially sites such as Chegg, GitHub,
Stack Overflow, and Quora, you cannot include it in your portfolio. (You may look at these sites
after you solve the problem.)
(IV) Under no circumstance may you use Co-Pilot, LLMs or any other AI-assisted programming tools.
Here is how your portfolio will be assessed.
(a) (8 marks) For each of the problems you are including in your portfolio (two problems), provide
the problem number, problem title, difficulty level, and the screenshot (showing all the details,
submission time, etc) of you getting your solution accepted by LeetCode. You will receive up to 4
marks for each problem you submit.
Here is an example from a sample portfolio: Longest Palindromic Substring (medium)
You will get full credit for any correct solution accepted by LeetCode, regardless of the difficulty
of the problem, and regardless of how well your runtime and memory usage compares with other
LeetCode participants.
(b) (2 marks) For one of the two problems you solved, 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. Reflect on what might be causing the
obstacle (e.g. lack of familiarity with a particular data structure, lack of knowledge about a fast
and efficient algorithm, etc.)
Note: For your reflections, write a minimum of 250 words.
Extra Challenge Question (practice ONLY )
Alice in a Coding Interview
Attention: This question is crafted for students seeking an extra challenge.
You’re welcome to skip this and submission is NOT required.
Alice is a second-year M.S. of Computer Science student in our beautiful Vancouver Campus. She has
recently participated in a coding interview with a tech company in Vancouver.
During the interview, she faces the following question which also happens to be one of the main topics
of Week 3 of our Algorithm class.
• Let’s say you are running an e-commerce platform, and you want to identify the top k most popular
products in your store based on customer purchase history. Given an integer array nums and an
integer k, return the k most (frequently sold) popular product IDs. You may return the answer in
any order.
If you were Alice, how would you approach this question?
(a) First, try to quickly come up with a brute-force solution. This should not take more than 10 minutes. Your only concern should be the correctness of your algorithm, not its efficiency.
– Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python.
(b) Now, try to see if you can optimize your algorithm in (a), and come up with a more efficient solution. There is no requirement on how fast your solution needs to be, it just needs to be better than
the one given in (a).
– Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python.
(c) Finally, with the learning from the previous two steps, I want you to come up with a decent solution
for this problem. Note that your algorithm’s time complexity must be better than O(nlogn), where
n is the array’s size.
– Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python.
Algorithms Homework 3 CS5800 Solved Assignment with Solution
Problem #1 – Longest Subsequence Problem (Week 4: Dynamic Prog.)
Difficulty: ■■■■□
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) (2 marks) 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) (3 marks) 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 k in your sequence, define (x(k), y(k)), where x(k) and y(k) are lengths of longest increasing and decreasing subsequences starting with k, respectively. Note that each pair is unique. Explain why
different numbers in your sequence cannot have identical (x(k), y(k)) pairs.
(c) (3 marks) 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?)
Let’s look into the general case. Specifically, if S is a sequence of n distinct integers, show 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.
BONUS (1 mark – 3%) [You Can SKIP this]: The results of part (c) immediately give 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).
Algorithms Homework 3 CS5800 Solved Assignment with Solution
Problem #2 – Fractional Knapsack Problem
Difficulty: ■■□□□
The knapsack problem is a classic optimization problem in computer science and mathematics. While
we have explored the 0-1 knapsack problem using dynamic programming and brute force approaches, in
this question, we will focus on the fractional knapsack problem and its relation to greedy algorithms.
Recall that in the fractional knapsack problem, items can be broken into smaller pieces, allowing you to
take fractions of items to maximize the total value while staying within the weight limit.
(a) (3 marks) Provide a clear pseudocode of a greedy algorithm for the fractional knapsack problem.
Your implementation should:
• Take as input:
– A list of items, where each item is represented by its weight and value
– The maximum weight capacity of the knapsack
• Return:
– The maximum value that can be achieved
– The list of items (and fractions thereof) selected to achieve this maximum value
(b) (2 marks) Analyze the time and space complexity of your algorithm. Briefly Justify your answer.
(c) (3 marks) Compare and contrast the fractional knapsack problem with the 0-1 knapsack problem.
Provide a brief proof of why a greedy approach works for the fractional knapsack but not for the
0-1 knapsack. Your explanation should include:
• A brief discussion of the key differences between the two problems
• A counterexample showing why the greedy approach doesn’t work for the 0-1 knapsack
• A brief proof on why greedy approach is optimal for the fractional knapsack problem
Problem #3 – Sleepy Cat (Week 6: Graph Algo.)
Difficulty: ■■□□□
For an m × n matrix, each cell could be either empty, or placed with a lovely cat. While some cats are
awake, others are still in dreams. Every minute the sleeping cats next to an awake cat will be woken up
(by next to it means the up/down/left/right positions).
In the following example, there’re 1 awake cat and 2 sleeping cats. After the first minute, the sleeping cat on the bottom left corner will be woken up. Then after the second minute, the sleeping cat on
the bottom right corner will be woken up too. Now all cats are awake for a total of 2 minutes.
(a) (3 marks) For such a matrix and a sleeping cat in one cell, how long does it take for it to get
woken up? Assume the matrix is m × n and the cell is located at (x, y), cell values are either 0 (for
empty), 1 (for awake cats) or −1 (for sleeping cats). Briefly describe your algorithm and write a
clear pseudocode.
(b) (3 marks) How long does it take for all cats to be awake? Briefly describe your algorithm and
write a clear pseudocode and provide a brief analysis of its running time.
(c) (2 marks) Continue with the case in part a, can you track down how the sleeping cat gets woken
up from the beginning? There could be multiple ways, but you only need to figure out one of them.
In the above example, the path would be [(0, 0),(1, 0),(1, 1)]. Can you provide a solution for this?
Briefly describe your algorithm and write a clear pseudocode.
Problem #4 – Build a Portfolio on Greedy Programming (Week 5)
Difficulty: □□□□□ (flexible)
LeetCode (www.leetcode.com) is a popular website for Northeastern MSCS students, especially when
preparing for job interviews.
https://leetcode.com/problemset/algorithms/
There are over a thousand “coding challenges” from which students can practice and improve their skills
in Algorithm Analysis and Design, and the website supports numerous programming languages, including
C, Java, and Python.
In this Programming Project, you will create a portfolio consisting of TWO LeetCode problems on
Greedy Programming you will solve over the next two weeks. You can choose ANY set of TWO problems
from the following site (click on ”Greedy Programming” to filter the results), but see the following note
first.
Important Note: You can pick anything excluding the Greedy/DP problems we will discuss in class
during Week 5 − 6:
• Fibonacci or Climbing Stairs
– Leetcode 70. Climbing Stairs
– Leetcode 509. Fibonacci Number
• Rod Cutting
– Leetcode 1547. Minimum Cost to Cut a Stick (similar problem)
• Longest Common (or Increasing) Sub-sequence
– Leetcode 1143. Longest Common Subsequence
– Leetcode 300. Longest Increasing Subsequence
• Activity-Selection
– Leetcode 435. Non-overlapping Intervals (closest equivalent)
• Knapsack or Coin Change
– Leetcode 322. Coin Change
– Leetcode 416. Partition Equal Subset Sum (0/1 Knapsack variant)
• House Robber
– Leetcode 198. House Robber
NOTE: To maximize your learning and problem-solving skills, we encourage you to explore these concepts through fresh challenges. The idea is for you to get more exposure to problem-solving, so for your
own benefit, please stay away from these problems!
[Read Carefully] This HW offers a lot of flexibility but there are four important rules:
(I) If the problem took you less than 30−40 minutes to solve, you may not include it in your portfolio.
(Since then the question was an exercise for you, rather than a problem or a challenge.)
(II) You may only include problems you have solved after Friday, Oct 04, 2024.
(III If you click on the LeetCode “Solution” or “Discuss” button before you solve the problem or look at
any online resources for hints to solve a LeetCode problem, especially sites such as Chegg, GitHub,
Stack Overflow, and Quora, you cannot include it in your portfolio. (You may look at these sites
after you solve the problem.)
(IV) Under no circumstance may you use Co-Pilot, LLMs or any other AI-assisted programming tools.
Here is how your portfolio will be assessed.
(a) (8 marks) For each of the problems you are including in your portfolio (two problems), provide
the problem number, problem title, difficulty level, and the screenshot (showing all the details,
submission time, etc) of you getting your solution accepted by LeetCode. You will receive up to 4
marks for each problem you submit.
Here is an example from a sample portfolio: Longest Palindromic Substring (medium)
You will get full credit for any correct solution accepted by LeetCode, regardless of the difficulty
of the problem, and regardless of how well your runtime and memory usage compares with other
LeetCode participants.
(b) (2 marks) For one of the two problems you solved, 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. Reflect on what might be causing the
obstacle (e.g. lack of familiarity with a particular data structure, lack of knowledge about a fast
and efficient algorithm, etc.)
Note: For your reflections, write a minimum of 250 words.
CS5800: Mini-Homework 4 Greedy/Dynamic & Graph | Algorithms Assignment Solution
Question 1: Happy Question – The Networking Adventure! [6 points]
Hello again! I’m the Networking Adventure, a special opportunity in your journey through
the world of computer science and technology. You can earn 6 marks just by stepping out of
your comfort zone and into the exciting realm of tech events!
In our fast-paced digital world, it’s easy to forget the value of face-to-face interactions and
real-world experiences. But remember our discussion about the importance of networking
and engaging with the tech community? Well, here’s your chance to put that into practice!
Invitation: We invite you to attend any tech event of your choice. It could be a local meetup,
a tech conference, a workshop, or even a virtual event. The goal is to expose yourself to new
ideas, meet fellow enthusiasts and professionals, and broaden your horizons.
Task:
1. Find a tech event that interests you happening either in Oct or Nov 2024.
• Hint: To begin with you can just look at our campus calendar to see what’s
happening on our campus. Also you don’t have to pay for this, many events are
free, especially for students!)
2. Register for the event.
3. Attend the event (or at least part of it if it’s a multi-day conference), network and build
at least 3 connections.
Submission: To claim your 6 marks, simply submit the screenshot of your event registration
or attendance proof. That’s it!
Remember, in the world of technology, sometimes the most valuable algorithms are the ones
that connect us with others in our field. Your career is not just about what you know, but
also who you know and the experiences you gather along the way.
So go forth, explore, connect, and most importantly, enjoy the adventure of being part of the
tech community!
Mini Homework CS5800:
3
Question 2: Graph Design [6 points]
Context: In computer science and mathematics, we often encounter problems where we
need to assign values or group items while satisfying certain conditions. This question
explores a specific type of constraint satisfaction problem that can be represented using
graph theory.
You are given a set of n variables 𝒙𝟏, 𝒙𝟐, 𝒙𝟑, . .. , 𝒙𝒏. These variables could represent
anything from people in a social network to nodes in a computer network. Your task
is to determine if it’s possible to assign values to these variables while satisfying two
types of constraints:
• Equality constraints ( 𝒎𝟏 of them): These are of the form 𝒙𝒊 = 𝒙𝒋, meaning
variables xᵢ and xⱼ must be assigned the same value or be in the same group.
• Inequality constraints ( 𝒎𝟐 of them): These are of the form 𝒙𝒊 ≠ 𝒙𝒋, meaning
variables xᵢ and xⱼ must be assigned different values or be in different groups.
You are given a set of n variables 𝒙𝟏, 𝒙𝟐, 𝒙𝟑, . .. , 𝒙𝒏 and a set of 𝒎𝟏 equality constraints of
the form 𝒙𝒊 = 𝒙𝒋 and a set of 𝒎𝟐 inequality constraints of the form 𝒙𝒊 ≠ 𝒙𝒋. Is it possible to
satisfy all of them?
For example, it is impossible to satisfy the constraints: 𝒙𝟏, = 𝒙𝟐, 𝒙𝟐, = 𝒙𝟑, 𝒙𝟏, ≠ 𝒙𝟑.
Q2 [6 points]:
a) [4 points] Design an algorithm (via pseudocode and 1 paragraph description (few
sentences only)) that takes as input the 𝒎𝟏 + 𝒎𝟐 constraints and decides whether
the constraints can be satisfied.
b) [2 points] Provide a brief analysis of the running time.
Mini Homework CS5800
4
Clarification:
• You don’t need to find the actual values or groupings; you just need to
determine if it’s possible to do so.
• The variables don’t have a specific range of values. You can think of them as
being able to take on any value or belong to any group, as long as the
constraints are satisfied.
• A constraint system is considered satisfiable if there exists at least one way to
assign values or group the variables that doesn’t violate any constraint.
Additional Examples:
• Satisfiable example:
o Variables: x₁, x₂, x₃, x₄
o Constraints: x₁ = x₂, x₃ = x₄, x₁ ≠ x₃
o This is satisfiable because we can group x₁ and x₂ together, and x₃ and
x₄ together, satisfying all constraints.
• Unsatisfiable example:
o Variables: x₁, x₂, x₃, x₄
o Constraints: x₁ = x₂, x₂ = x₃, x₃ = x₄, x₁ ≠ x₄
o This is unsatisfiable because the equality constraints force all variables
to be equal, contradicting the last constraint.
Mini Homework CS5800
5
Question 3: Greedy & Dynamic Programing [6 points]
You work for a small manufacturing company and have recently been placed in charge of
shipping items from the factory, where they are produced, to the warehouse, where they are
stored. Every day the factory produces 𝑛 items which we number from 𝟏 𝐭𝐨 𝒏 in the order that
they arrive at the loading dock to be shipped out. As the items arrive at the loading dock over
the course of the day they must be packaged up into boxes and shipped out. Items are boxed up
in contiguous groups according to their arrival order; for example, items 𝟏 . . 𝟔 might be placed
in the first box, items 𝟕 . . 𝟏𝟎 in the second, and 𝟏𝟏 . . 𝟒𝟐 in the third.
Items have two attributes, value and weight, and you know in advance the values 𝒗𝟏 . . 𝒗𝒏 and
weights 𝒘𝟏 . . 𝒘𝒏 of the 𝒏 items. There are two types of shipping options available to you:
Value-Restricted Boxes: One of your shipping companies offers insurance on boxes and hence
requires that any box shipped through them must contain no more than 𝑉 units of value.
Therefore, if you pack items into such a “value-restricted” box, you can place as much weight in
the box as you like, as long as the total value in the box is at most 𝑉.
Weight-Restricted Boxes: Another of your shipping companies lacks the machinery to lift
heavy boxes, and hence requires that any box shipped through them must contain no more than
𝑊 units of weight. Therefore, if you pack items into such a “weight-restricted” box, you can place
as much value in the box as you like, as long as the total weight inside the box is at most 𝑊.
Please assume that every individual item has a value at most 𝑉 and a weight at most 𝑊. You may
choose different shipping options for different boxes. Your job is to determine the optimal way
to partition the sequence of items into boxes with specified shipping options, so that
shipping costs are minimized.
Q2.1 [6 points]: Suppose limited-value and limited-weight boxes each cost $1 to ship.
a) [2 points]: Briefly describe a Greedy Algorithm that can determine a minimum-cost
set of boxes to use for shipping the items
b) [4 points] Write a pseudocode for your algorithm and explain the time complexity
of your solution (don’t just say O(…), justify that briefly).
Note: Your algorithm should produce an optimal solution, but you do NOT need to prove that!
For Practice ONLY [No Need to submit]: Suppose limited-value boxes cost $𝐶’ and limitedweight boxes cost $𝐶(. Assume you want to design 𝑂(𝑛)) Dynamic Programing algorithm that
can determine the minimum cost required to ship the 𝑛 items.
– Give the formula for the optimal substructure of this problem. Here is an example
of such formula for LCS.
– Write a pseudocode for your algorithm.
Mini Homework CS5800
6
Question 4: Leetcode on BFS, DFS, MST or Shortest Paths [6 points]
In this homework, you will pick your own choice of only ONE LeetCode problem from the
following site (click on ”Breadth First Search” or ”Depth First
Search” or ”Minimum Spanning Tree” to filter the results):
• https://leetcode.com/problem-list/breadth-first-search/
• https://leetcode.com/problem-list/depth-first-search/
• https://leetcode.com/problem-list/shortest-path/
• https://leetcode.com/problem-list/minimum-spanning-tree/
[Read Carefully] This HW offers a lot of flexibility but there are four important rules:
I. If the problem took you less than 30 − 40 minutes to solve, you may not include it in
your portfolio.(Since then the question was an exercise for you, rather than a problem
or a challenge.)
II. You may only include problems you have solved after Oct 16, 2024.
III. (III If you click on the LeetCode “Solution” or “Discuss” button before you solve the
problem or look at any online resources for hints to solve a LeetCode problem,
especially sites such as Chegg, GitHub, Stack Overflow, and Quora, you cannot include
it in your portfolio. (You may look at these sites after you solve the problem.)
IV. Under no circumstance may you use Co-Pilot, LLMs or any other AI-assisted
programming tools.
Mini Homework CS5800
7
(a) [2 points]: For the selected problem provide the problem number, problem title,
difficulty level, and the screenshot (showing all the details, submission time, etc) of you
getting your solution accepted by LeetCode. You will receive up to 4 marks for each problem
you submit.
Here is an example from a sample portfolio: Longest Palindromic Substring (medium)
You will get full credit for any correct solution accepted by LeetCode, regardless of the
difficulty of the problem, and regardless of how well your runtime and memory usage
compares with other LeetCode participants.
(b) [4 points]: 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. Reflect on what might be causing the obstacle
(e.g. lack of familiarity with a particular data structure, lack of knowledge about a fast and
efficient algorithm, etc.)
Note: For your reflections, write a minimum of 250 words.
