## Description

Instructions:

• 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