Assigned: March 15, 2020
Due: March 30, 2020
CIS 121 — Data Structures and Algorithms Homework Assignment 6
Note: The homework is due electronically on Gradescope on March 30, 2020 by 11:59 pm ET. For late submissions, please refer to the Late Submission Policy on the course webpage. You may submit this assignment up to 2 days late.
A. Gradescope: You must select the appropriate pages on Gradescope. Gradescope makes this easy for you: before you submit, it asks you to associate pages with the homework questions. Forgetting to do so will incur a 5% penalty, which cannot be argued against after the fact.
B. LATEX: You must use the LaTex template provided on the course website, or a 5% penalty will be incurred. Handwritten solutions or solutions not typeset in LaTex will not be accepted.
C. Solutions: Please write concise and clear solutions; you will get only a partial credit for correct solutions that are either unnecessarily long or not clear. Please refer to the Written Homework Guidelines for all the requirements.
D. Algorithms: Whenever you present an algorithm, your answer must include 3 separate sections.
1. A precise description of your algorithm in English. No pseudocode, no code. 2. Proof of correctness of your algorithm
3. Analysis of the running time complexity of your algorithm
E. Collaboration: You are allowed to discuss ideas for solving homework problems in groups of up to 3 people but you must write your solutions independently. Also, you must write on your homework the names of the people with whom you discussed. For more on the collaboration policy, please see the course webpage.
F. Outside Resources: Finally, you are not allowed to use any material outside of the class notes and the textbook. Any violation of this policy may seriously affect your grade in the class. If you’re unsure if something violates our policy, please ask.
March 15, 2020 Homework Assignment 6 2 1. [15 pts] Welcome to Six Graphs
Ayyah is building an amusement park called Six Graphs for students to enjoy after finishing CIS 121. She has already constructed n ≥ 2 attractions which are connected by m undirected pathways. Each pathway connects exactly two attractions, and Ayyah has designed the park such that any pair of attractions are reachable from one another. However, upon examining her income statement and consulting with Rajiv, she realizes she will operate on a loss if she does not get rid of exactly k attractions including any pathways incident upon those k attractions, where k is a positive integer. Ayyah still wants to have her amusement park set up in such a way that the students can still walk from attraction to attraction. Note that you may treat k as a constant and k < n.
Help Ayyah design an O(n + m) algorithm to find k such attractions that she can remove in her amusement park.
2. [15 pts] Dana’s Piazza Dash
Dana is in CIS 371 lecture in Towne 100 when she gets a Piazza alert on her phone. Due to a mysterious bug, she is unable to answer the question from her phone. She decides she must immediately head home, where she left her computer, to answer the Piazza question.
Dana consults a map on her phone, and sees that there are n buildings (including Towne 100 and her house) and m undirected streets. She also notices that each street is labeled with a positive integer, de- scribing the time in minutes it takes to travel. It turns out that each street takes no more than k minutes to walk. Note you can assume there exists a path from Towne 100 to Dana’s house.
Dana knows she can simply use Dijkstra’s algorithm to find the shortest path from Towne 100 to her house, but she thinks it will take too long. Without using a modified Dijkstra’s algorithm, help her find an algorithm that runs in O(n + km) time to find the shortest path from Towne 100 to her house.
3. [20 pts] Going Viral
To help boost his popularity among young voters in the race for CIS President, Michael BloomSong decides to hire an Instagram influencer to promote his campaign. The only way Michael can win the race is if he hires a “viral” influencer. We consider a certain Instagram user “viral” if every Instagram user either follows them directly, or indirectly follows them. We define a user t as indirectly following user u if t directly follows some other user that directly or indirectly follows u. Note that Michael can only see if a user directly follows another.
Help Michael figure out his options by providing an efficient algorithm that outputs the set of all “viral” Instagram users. No proof of correctness is required, but please do justify the run- time of your algorithm.
4. [25 pts] Christina’s Cookie Swap
In honor of Penn Engineering’s 170th year anniversary, Dean Kumar decides to organize a dessert potluck in which the faculty in each building prepare a signature cookie to share with the other buildings. Christina is working to deliver these cookies between every pair of buildings on campus. There are n buildings on campus with m one-way streets connecting them, each with a positive distance.
March 15, 2020 Homework Assignment 6 3 Note that there may be a unique street from Huntsman to Hill with distance w1, but there may also
be a unique street from Hill to Huntsman with distance w2.
Christina is enlisted to help bring cookies from each building to every other building, but she decides that each cookie must be wrapped nicely with a bow before being delivered to its final destination. The bows are all stored in a box in Quain Courtyard, meaning that Christina must stop in Quain Courtyard along her delivery route every time she is delivering a cookie. You may assume that such a route exists between any given pair of buildings.
Help Christina come up with an O(n2 + m log n) algorithm that finds the length of the shortest route between every pair of buildings, while ensuring that each route passes through Quain Courtyard (which we can denote as building v∗).
5. [25 pts] Andrew and Andrew’s Parade Problem
Andrew F. and Andrew S. are leading a parade around campus and are currently deciding how to lay out the directions for the parade’s route. They have a map of campus, which includes a set of B buildings and P undirected streets between them. Note that a single street connects exactly two buildings. They decide they don’t want the parade to go around in circles, so Andrew F. begins assigning one-way directions to each of the undirected streets.
He is able to successfully assign directions to a subset of streets P1 of P such that they alone do not create a cycle. However, there is still a set of streets P2 = P − P1 that have unassigned directions. Andrew S. needs to finish the job and assign a direction for each of the streets in P2 such that the resulting directed streets of P do not include any cycles.
Give an algorithm to help Andrew S. finish assigning directions to the remaining undirected streets in O(|B| + |P |) time. Note that you have access to G(B, P1) and G(B, P2) as separate adjacency lists.
[0 pts] Feedback: No feedback form for this assignment. Feel free to reach out to the Head TAs if you have any comments/concerns.