Assigned: January 16, 2020
Due: January 27, 2020
CIS 121 ¡ª Data Structures and Algorithms Homework Assignment 1
Note: The homework is due electronically on Gradescope on January 27, 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. Piazza will also contain a complete sample solution in a pinned post.
D. Algorithms: Whenever you present an algorithm, your answer must include 3 separate sections. Please see Piazza for an example complete solution.
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.
January 16, 2020 Homework Assignment 1 2 1. [10 pts] Bob Ross ¡Á Paint By Number
(a) Bob Ross is painting a new picture and wants to color the objects in the scene so that each element is differentiated by color from its surroundings. He knows that in this painting, each object is only adjacent to a maximum of k other objects. This painting can be represented as an undirected graph G with vertices representing elements in the painting and edges connecting adjacent elements, in which the maximum degree of any vertex is k. Prove by construction that G is (k + 1)-colorable, i.e., give an algorithm to color the vertices of G in a way such that no two adjacent vertices share the same color and at most k+1 colors are used. You must argue the correctness of your algorithm.
(b) Provide an example of a graph G with max degree k and chromatic number strictly less than k + 1 for which your algorithm may use exactly k + 1 colors. That is, trace through an instance of your algorithm that needs all k + 1 colors to color G, though G has a strictly lower chromatic number.
2. [20 pts] To Bead or Not to Bead
Helen is making a necklace by placing n blue beads and n red beads randomly onto the circular necklace. Here, n ¡Ý 2. For each part below, be sure to justify your answer.
(a) What is the minimum number of blue beads that could be placed next to red beads? (b) What is the maximum number of blue beads that could be placed next to red beads?
(c) What is the expected number of blue beads that could be placed next to red beads?
3. [20 pts] UPennAlert: Burglary at Towne Bldg. Use caution, police on scene, avoid area.
President Amy Gutmann suspects that Ishaan has been regularly stealing chairs from n classrooms in Towne. To stop these thefts, she decides to use a small fraction of her salary to hire n security guards to guard the n rooms. She then sets up a schedule S of m time slots for each security guard such that at each slot, they are either guarding a room or taking a break outside (you may assume that m > n). This schedule has been organized such that each guard visits each room exactly once and at any time slot no more than one guard is at any given room.
She decides, however, that in order to avoid having the security guards move around rooms all the time, she wants to modify her original schedule into a new schedule S¡ä. Specifically, she wants each security guard si assigned a room ri such that si will follow their original schedule until they reach room ri, at which point they will remain in this room for the rest of the schedule (i.e., they will not guard any more rooms). Amy now only cares about ensuring that S¡ä is constructed such that each room is still only being guarded by at most one person at a time.
Provide an algorithm to help our president construct schedule S¡ä from S by reducing this problem to an instance of the stable matching problem and running the GS algorithm.
4. [20 pts] Sneaky Steve
The 121 TAs all wish to apply for research positions at Penn next summer. They learn that there are exactly the same number of research positions available as there are TAs and they begin fighting over who gets which position. Upon further investigation, they find that the department solves this issue by creating a system to assign each applicant to a position. Each TA submits a list of their preferences for the positions, and each open position has a preference list of the applicants. Then, the department
January 16, 2020 Homework Assignment 1 3
uses the Gale-Shapley algorithm to produce a stable matching, where each research position hiring manager goes through their preference list until they are matched with a TA who accepts the position, and this process repeats until all positions and TAs are matched.
After learning of this system, Steven thinks he might be able to fool the department into getting the position he wants by misrepresenting his preferences. Suppose Steven prefers position p to p¡ä, but both p and p¡ä are low on his list of preferences (i.e., not first). Can it be the case that if he misrepresents his preferences and switches the order of p and p¡ä on his list of preferences, when the algorithm is run, Steven will be matched with a position which he prefers over the position he would otherwise be given?
You should either:
a. Give a proof that, for any instance of the stable matching problem, no TA can improve their position by switching the order of a pair of positions on their list; or
b. Give an example of a set of preference lists for which Steven can improve his position by switching the ordering of a pair of positions on his list. Be sure to explain why this example is correct.
5. [30 pts] CIS Waitlist – Stable Matching Programming Exercise
Click here for instructions. Collaboration is NOT allowed on this question.
6. [10 pts] k-regular Bipartite Graph
A k-regular graph is a graph in which each vertex has degree exactly k. Let G be a k-regular bipartite graph, where k ¡Ý 1. It can be shown using Hall¡¯s theorem that G has a perfect matching. Given this fact, show via induction that the edge set of G can be partitioned into k disjoint perfect matchings.
[0 pts] Feedback: No feedback form for this assignment. Feel free to reach out to the Head TAs if you have any comments/concerns.