We have put together several stub files –– click here to download them.
5 files to submit: Question1.java, Question2.java, Question3.java,
Question4.java, and Question5.java
Please do not submit any additional files.
Be sure to follow these guidelines:
package src;).[compilation], and
two free submissions on the autograder marked [full].This homework is intended to help you review and apply concepts you learned throughout the semester, and to help you prepare for algorithmic programming interviews you may encounter.
Learning Objectives:
You will notice that these questions are very similar to the written questions you had to do for various assignments in this course. This time around, you will actually implement your algorithms!
Often times, this comes with some challenges. Sure, we can just say “run BFS” as a black box, but implementing it on the fly is a bit different, especially if you need to apply it to a certain problem. This assignment will give you practice applying what you’ve learned.
We are not asking you to submit unit tests for this homework. However, we still expect that you write test cases as it will be very difficult to do well on this homework without thoroughly testing your code on a variety of inputs. In short, you should still be unit testing even if we aren’t asking you to submit your tests.
To help you out a bit, we will be providing one test case per question, which is sometimes common practice in on-line coding samples. This test is only there to make sure you are understanding the problem correctly, and that you are hopefully headed in the right direction. These tests are explained in the write-up after each problem below, and will be available on Gradescope.
Each solution will be manually reviewed by a TA to ensure it meets our target runtime. Solutions that meet our target runtime will not be deducted any points manually. Partial credit (and possibly some efficiency penalties) will be given for incorrect and/or inefficient solutions. Note that brute force and extremely inefficient solutions are not likely to receive many points (even if they pass our automated tests).
In order to make this assignment as useful as possible, we would like you to think about these questions primarily on your own, without debugging help from TAs at office hours. High-level questions related to logic are okay, but if you come to office hours requesting debgging help, your question will be denied. These problems are challenging, but you will get the most of out them if you spend time coming up with these solutions on your own!
Should you require any clarification on a problem, feel free to ask on Ed.
In this section, you will be implementing five algorithmic programming questions. All
instructions are both below and in the respective question’s .java file. The one provided
test case per question is also listed below. Make sure to take a look at the test
case to confirm your understanding of the question.
You must think about and implement these questions completely on your own (it is also against course policy to consult other sources, including your friends and the Internet).
This is likely your first time implementing these types of questions, so we want you to walk yourself through the entire process of solving one of these questions.
Please be sure to read through the entirety of this article, so you understand the thought process needed to solve these sorts of questions, and how you should actually go about implementing them.
Some tips to keep in mind:
Please do not continue until you have read the article above carefully, and have understood the solution.
File to Submit: Question1.java
Target Runtime: $O(m + n)$, where $n = \texttt{numFlights}$ and
$m = \texttt{conditions.length}$.
Please read the documentation for Question1.java below carefully, and then
confirm your understanding of the problem by reading the test case below.
You are the newest flight dispatcher recruit, and given your computer science background your manager assigns you a task to complete on day one. She’s tired of manually figuring out what order the planes can depart in given some restrictions, so she enlists your help in automating this process.
More formally, there are n planes waiting to take off labeled 0 -> n - 1. Some
flight plans have conditions that must be met. For example, for flight 0 to take off, flight 7
must have taken off already. This is expressed as the pair [0, 7].
Given the number of flights waiting to take off and a list of condition pairs, design and implement an algorithm to schedule all the flights. Sometimes, multiple flight schedules might exist – in that case, return any one of them. If it’s not possible to schedule all the flights, then return an empty list.
In order to ensure that you fully understand the problem, we’ve made the following test case public. This test case is basic, so please don’t rely on it. Note: You will be deducted 4 points if you hard-code this test case.
Input: numFlights = 4, conditions = [[3, 2], [1, 2], [0, 3], [0, 1]]
Output: [2, 3, 1, 0] or [2, 1, 3, 0], as for flight 0 to have departed,
flights 3 and 1 should have departed before as well. Additionally, flights 3 and
1 should have left after flight 2, so those are the two options we have.
File to Submit: Question2.java
Target Runtime: $O(n\lg n)$, where $n$ is the number of pairs. Note: without the
constraint below, it is possible to do better in expectation.
Other Constraints: You may use $O(1)$ additional space other than your output set. Should you
choose to use it, you may assume that Java’s built-in sorting method is in-place (even though in
reality it often times uses more than $O(1)$ space). You may also not use the set’s contains() method.
Please read the documentation for Question2.java below carefully, and then
confirm your understanding of the problem by reading the test case below.
You may use a HashSet for the output set ONLY!
Penn Residential Services (aka Penn RES) seeks your help for matching roommates. They give you a 2d-array of pairs of the form (student, requested roommate).
Each student is only allowed to request one roommate. Penn RES wants to save time, so they want to automatically
match all students who mutually request each other.
Your task will be to return a set of pairs of students who mutually requested each other, given a 2d-array of pairs, in $O(n\lg n)$ time.
In order to ensure that you fully understand the problem, we’ve made the following test case public. This test case is basic, so please don’t rely on it. Note: You will be deducted 4 points if you hard-code this test case.
Input: requests[][] = { {"Steven", "Will"}, {"Helen", "Caroline"}, {"Caroline", "Monal"}, {"Will", "Steven"} }
Output: {("Steven", "Will")} or {("Will", "Steven")} (either order is fine) since Steven requested Will
and Will requested Steven. There is no other pair who mutually requested each other.
File to Submit: Question3.java
Target Runtime: $O(n^2)$ where $n = \texttt{city.length}$
Please read the documentation for Question3.java below carefully, and then
confirm your understanding of the problem by reading the test case below.
A bunny is stuck in Center City and is trying to get back home to Penn as quickly as possible. The bunny has a map of the city, which happens to be an $n \times n$ 2d-array of positive integers, where each entry defines how many cells the bunny can hop up or to the left when that entry is reached (note that bunny must hop exactly that many cells, not more and not less).
Center City happens to be the bottom right corner of the 2d-array, and Penn happens to be the top left corner, so the bunny’s goal is to reach the top-left corner in the fewest number of hops.
Your goal here is to determine what the minimum number of hops would be, given a $n\times n$ 2d-array of the city, in $O(n^2)$ time. If no path is possible, you should return -1 to indicate so.
In order to ensure that you fully understand the problem, we’ve made the following test case public. This test case is basic, so please don’t rely on it. Note: You will be deducted 4 points if you hard-code this test case.
Input:
city[][] = { {1, 6, 2},
{1, 6, 4},
{1, 9, 2} }
Output: 2 because the minimum number of hops is from city[2][2] $\rightarrow$ city[0][2]
$\rightarrow$ city[0][0]. Note that another path exists, namely city[2][2] $\rightarrow$ city[2][0]
$\rightarrow$ city[1][0] $\rightarrow$ city[0][0]. However, this path is longer and would require 3 hops.
File to Submit: Question4.java
Target Runtime: Expected $O(n^2)$, where $n = |\texttt{codes}|$. An expected
$O(n)$ solution exists, but we are not requiring it for full credit.
While waiting for their plane to take off, the TAs decide to play a game they called “Airport Code Change” which is played as follows. Given two 3 letter airport codes (ex: PHL, JFK) and a set of all airport codes they were all familiar with, their goal was to find the smallest chain of words to link the two airport codes such that:
1) Two adjacent words differ by exactly one letter
2) Each word must exist in the set of airport codes
You decide that you want to beat them all, so you code up a solution getSmallestChain,
which given the two 3 letter airport codes and a set of all familiar airport codes returns the
shortest chain.
Sometimes, it may happen that there is no solution. In this case, your algorithm will return
null. You can assume that if multiple solutions exist, the “shortest” one will be unique.
In order to ensure that you fully understand the problem, we’ve made the following test case public. This test case is basic, so please don’t rely on it. Note: You will be deducted 4 points if you hard-code this test case.
Input: code1 = MIA, code2 = BLE, codes = {MIA, JFK, MLA, MLE, BLE}
Output: [MIA, MLA, MLE, BLE], as that sequence of changes is the shortest
way of getting from MIA to BLE through one letter changes given that set of
airport codes.
File to Submit: Question5.java
Target Runtime: $O(n)$, where $n$ is the number of family members
Please read the documentation for Question5.java below carefully, and then
confirm your understanding of the problem by reading the test case below.
Due to your interest in genealogy, many families have recently approached you with their family trees. In all of these family trees, spouses are not included, so all members of the tree are blood related. These families have all managed to trace their ancestry pretty far back. Each person in each family has a unique favorite number. The unique number is a number from where is the number of family members.
The governor of your city has decided to make a competition that the family with the most number of odd sized sub-trees wins 1 million dollars! Due to your popularity, thousands of families are now sending their extensive family trees to you so you can check how many odd sized sub-trees they have, in exchange for a portion of the 1 million dollars.
Your goal, then, is to write an efficient $O(n)$ algorithm that returns how many odd sized sub-trees a given family tree has.
In order to ensure that you fully understand the problem, we’ve made the following test case public. This test case is basic, so please don’t rely on it. Note: You will be deducted 4 points if you hard-code this test case.
Input: Your input will be given to you as an adjacency list where the list at index stores the children of . The number for each node represents the unique favorite number of each family member. Remember, the favorite numbers go from , they are unique, and represents the number of family members. This is the visualized tree:
tree = 0 <-- root
/ \
1 3
/ | \ \
2 4 5 6
Output: 5. The sub-trees rooted at 0, 2, 4, 5, and 6 all have odd size.