• The assignment is due at the time and date specified. Late assignments will not be accepted.
• You must work on all the problems and write the solutions by yourself! Finding solutions to homework
problems on the web, or by asking students in and outside the course is strictly prohibited. This would be
defeat the purpose of learning by doing the assignment.
• You must submit typed solutions. You may use plain text or a word processor like Microsoft Word or LaTeX
for your submissions. You may hand-sketch and scan any diagrams that you support your answer.
• If you are not comfortable with Word or Latex, please solve these problems by hand before devoting time to
typing them. Do not waste precious time investigating typesetting up front!
We are currently investigating some suspected cases of plagiarism. You have reached
the end of the semester. Don’t waste your hard work and your reputation by giving in to
last-week and final grade stress and cheat on this assignment, including Problem 3.
1. (30 points)
Spencer Gilpin is sucked into the game Jumanji as Smolder Bravestone (see here for more context:
https://en.wikipedia.org/wiki/Jumanji:_Welcome_to_the_Jungle). The objective of Jumanji is to
return the Jaguar’s eye (a jewel) which is a particular landmark in the Jumanji world. This world has
several landmarks and ways to travel between them (not directly). The landmarks are not arranged
sequentially, and thus there are multiple ways of getting to the Jaguar’s eye. However several (but not all)
landmarks are death-traps. If a player reaches a death-trap, it will kill the player. The player is reborn at
the same landmark instantaneously, which is not deadly anymore. The game has a total of n such deadly
landmarks, and Smolder has k lives, with k < n. If Smolder dies k times before reaching the Jaguar’s eye, the game is over (and Spencer will be trapped forever in the virtual game). There is no incentive to reaching the Jaguar’s eye with extra lives. Smolder is talented and brave enough to travel between landmarks successfully, but he must be careful about which landmarks he chooses to go to. Fortunately (only for Smolder), you are also part of the game as Sheldon Oberon and have entered with him at the same place and time. Sheldon is a cartographer, has a map of the entire Jumanji world and has k lives as well. You need Smolder’s bravery and fighting skills and will always stick with him (i.e. both of you live and die together). You can help him by planning your journey with him from the landmark that you both entered from, to the Jaguar’s eye. Both of you wish to return to the real world as soon as possible. Devise an algorithm that computes the quickest way for you to reach the destination alive, given all the travel times between landmarks. 1 Hint: Can Spencer and Sheldon get there without dying at all? How about dying once? 2. (20 points) Fall 2018 is upon us! The new graduate student orientation has organized dinner at the end of the orientation, and they have put tables where students from different cities can sit together and mingle. However every year students from the same city who know each other already sit together. Professor Shesh wants each table to have students from different cities so that everybody makes new friends. Danni has determined that students come from n different cities, with ai students from city i, such that 1 ≤ i ≤ n. There are m tables with seating capacities t1, t2, ...tm respectively. Professor Shesh wants no more than 3 students at any table to be from the same city. How can he formulate this problem as a flow network and determine the seating arrangement? Your answer must contain a description of the flow network, and how you will use it to determine the seating arrangement. Hint: Think about what restricts the flow in a flow network, and how you can use it to impose constraints. 3. (Extra credit: 10 points) A simple path in a graph G is a path between two vertices with each vertex appearing at most once. A simple cycle is defined similarly, except there is an edge from the last vertex to the first one. The distance between two vertices in a graph is the least number of edges that must be traversed to reach one vertex from the other. The diameter of a graph G, denoted as diam(G) is defined as the length of the longest simple path the maximum distance between any two vertices in the graph. If G is a connected, undirected graph that is not a tree, then prove that any there is a cycle in G of length at most 2 ∗ diam(G) + 1. 2