Submit a pdf file of your written answers and one py file with your Python codes. All Python
solutions should be clearly commented. Your codes need to run to get credit for your an-
swers.
You should not ask about the exam during the office hours or post any question about it on
Piazza. However, classes on Wednesday, November 29 and Wednesday, December 6 will be
reserved for questions about the exam.
All work on this exam needs to be independent. You may consult the textbook, the lecture
notes and homework sets, but you should not use any other resources. If we suspect that
you collaborated with anyone in the class or on the Internet, we will enforce the honor code
policy strictly. If there is a reasonable doubt about an honor code violation, you will fail this
course.
Problems:
1. (20 points) Given an arrayfa1;a2; ;ang, a reverse is a pair (ai;aj) such that i aj. Design a divide-and-conquer algorithm with a runtime of O(nlogn) for computing
the number of reverses in the array. Your solution to this question needs to include both a
written explanation and a Python implementation of your algorithm, including:
(a) Explain how your algorithm works, including pseudocode.
(b) Implement your algorithm in Python.
(c) Randomly generate an array of 100 numbers and use it as input to run your code. Report
on both the input to your code and on how the output demonstrates the correctness of
your algorithm.
2. (25 points) Suppose that you are assigned a task to do a survey about n important issues
(such as education policy and health insurance mandate), by asking a group of m persons
questions about these issues. Suppose that a person may not have an opinion about all the
issues, and you can ask a person about an issue only if s/he has an opinion about it. We use a
bipartite graph G =fP[I;Egto capture whether a person p2P has an opinion about an
issue i2I or not: (p;i)2E means that p has an opinion about i. For each issue i, in order
to have a reliable survey you need to ask at least li persons about it, but you may have certain
budget constraint so that you can only ask at most ui persons about it. For each person p,
you may ask her/him between bp and tp issues.
Given G and parameters (li;ui); i2I and (bp;tp); p2P, design an algorithm to determine
if these parameters are feasible, by formulating it as a problem of finding a routing with
lower bounds as in Problem 1 of homework set #9. You shall solve the problem according
to the following steps.
(a) Show how to formulate the parameter feasibility problem as a problem of finding a
routing with lower bounds. The resulting problem should be specified by certain graph
G0 = fV 0;E0g with capacity c(e) and lower bound l(e) for each edge e 2 E0 and
demand r(v) at each vertex v2V 0.
1
(b) Further formulate the problem as a maximum flow problem as in Problem 1 of home-
work set #9. The resulting problem should be specified by certain graph ^G =f^V; ^Eg
with source s, sink t and capacity c(e) for each edge e2 ^E.
(c) Implement (a)-(b) in Python. Your code should take the graph G and parameters
(li;ui); i2I and (bp;tp); p2P as the input, and produce the graph ^G with source s,
sink t and capacity c(e); e2 ^E as the output.
(d) Further implement the Ford-Fulkerson Algorithm in Python to find the maximum flow
from s to t over the graph ^G.
(e) Generate a test case of parameters according to the following specifications, and run
your code to see if the parameters generated are feasible.
The number of issues n = 10 and the number of persons m = 1000;
For any person p and for any issue i, s/he has a probability of 50% to have an
opinion about the issue, i.e., there is a 50% probability that there is a link from p
to i in the graph G;
For any person p, denote by hp the number of issues that s/he has an opinion about.
Let bp =bhp=2cand bp = hp;
For each issue i, li is drawn uniformly from the interval [300, 400] and ui uni-
formly from [500, 700].
3. (10 points) Suppose you have been sent back in time and have arrived at the scene of an
ancient Roman battle. It is your job to assign n spears to n Roman soldiers so that each
soldier has a spear. It is best if your assignments minimize the difference in heights between
the height of the man and the height of his spear. That is, if the ith man has height mi, and
his spear has height si, then you want to minimize: Pijmi sij.
(a) Design algorithm to find the optimal, or near optimal, solution without evaluating all
possible combinations. Include an explanation and pseudocode showing how your al-
gorithm works.
(b) Compare the runtime complexity of your algorithm with the complexity of a brute force
solution.
4. (20 points) Consider the following spider-web graph that shows a spider siting at the bottom
of its web, and a fly sitting at the top. On moodle, there is a file called graphExample.py that
implements the graph using a library called NetworkX.
(a) Write an algorithm to determine how many different ways can the spider reach the fly
by moving along the web’s lines in the directions indicated by the arrows?
(b) Implement your algorithm in Python using the NetworkX graph provided as your data
structure. You may need to install NetworkX if it isn’t part of your Python installation.
Do not use any of the NetworkX features that would make this problem trivial as part
of your solution. However, you can use anything in NetworkX to verify your solution.
Your algorithm should return an answer to the question in part (a).
There is more information about NetworkX available here: https://networkx.
github.io/documentation/networkx-1.10/index.html
5. (25 points) There are n 3 people positioned on a field (Euclidean plane) so that each has a
unique nearest neighbor. Each person has a water balloon. At a signal, everybody hurls his
or her balloon at the nearest neighbor. Assume that n is odd and that nobody can miss his or
her target.
2
(a) Write an algorithm to answer the question: Is it true or false that there always remains
at least one person not hit by a balloon?
(b) Implement your algorithm in Python such that it takes a data structure of people and
distances and produces a data structure of who was hit by a balloon.
(c) Prove that your algorithm is correct. Your proof needs to include specific features of
your algorithm.
(d) Analyze the runtime behavior. of your algorithm.