Description
EECS215 Homework 1
Practicing Topics from Chapters 1, 2, 3
1. (25 Points) Chapter 1 – Stable Marriage. Consider the following preference lists for
men and women:
Man # Preference List
1 1 2 3 4
2 2 1 4 3
3 3 4 1 2
4 4 3 2 1
Woman # Preference List
1 4 3 2 1
2 3 4 1 2
3 2 1 4 3
4 1 2 3 4
(a) (5 Points) Find the man optimal stable matching. Show some intermediate steps of your
answer.
(b) (5 Points) Find the woman optimal stable matching. Justify your answer
(c) (5 Points) Suppose that in another problem setting all men have identical preferences.
How many steps does it take for the algorithm to converge? Justify your answer.
(d) (10 Points) Truthfulness in Stable Marriage.
The classic stable matching problem assumes that all men and women state their true
preferences. Let us now consider a version of the problem in which people can lie about
their preference. More specifically, let us consider the following restricted scenario.
Consider three men m1, m2, m3 and three women w1, w2, w3. Everybody states their
true preferences except for woman w3, who can lie to some extent: she can look at her
true preference list and switch the place of two men in her list with each other (she can
only flip a pair). Woman w3 has no control over the true preference lists (her own or
other people’s). The only decisions she can make are: (1) whether to lie or not (in the
way mentioned above, i.e., switching a pair of men in her list); and (2) if she decides to
lie, she can also choose which pair (among all three pairs of men) to switch in her list.
The GS algorithm then runs with input the declared preference lists and produces as
output a stable matching.
The question is: can woman w3 get a better match by lying about her preferences?
Resolve this question by doing one of the following:
i. (5 Points) Prove that, for any set of preference lists, switching the order of a pair
on the list cannot improve a woman’s partner in the GS algorithm; or
ii. (5 Points) Give an example of a set of preference lists for which, there is a switch
that would improve the partner of a woman who switched preferences. And if she
decides to lie, which pair of men should she switch in her preference list?
1
2. (40 Points) Chapter 2 – Running Time Analysis.
(a) (20 Points) Growth Rates Order the functions in ascending order of growth rate. That
is, if function g(n) immediately follows function f(n) in your list, then it should be the
case that f(n) is O(g(n)).
g1(n) = 2
√logn, g2(n) = 2n, g3(n) = n(logn)
3, g4(n) = n
4
3 , g5(n) = nlogn, g6(n) = 22n
, g7(n) = 2n2
(b) (20 Points) Consider the problem below:
You’re given an array A consisting of n integers A[1], A[2], …, A[n]. You’d like to output
a two-dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array
entries A[i] through A[j]–that is, the sum A[i] + A[i + 1] + … + A[j]. (The value of array
entry B[i, j] is left unspecified whenever i ≥ j, so it doesn’t matter what is output for
these values.)
Here’s a simple algorithm to solve this problem:
for i= 1, 2,…, n do
for j= i+1, i+2,…, n do
Add up array entries A[i] through A[j]
Store the result in B[i, j]
end for
end for
(1) For some function f that you should choose, give a bound of the form O(f(n)) on
the running time of this algorithm on an input of size n (i.e. a bound on the number of
operations performed by the algorithm).
(2) For this same function f, show that the running time of the algorithm on an input
of size n is also Ω(f(n)). (This shows an asymptotically tight bound of Θ(f(n)) on the
running time.)
(3) Although the algorithm you analyzed in parts (1) and (2) is the most natural way to
solve the problem – after all, it just iterates through the relevant entries of the array B.
filling in a value for each – it contains some highly unnecessary sources of inefficiency.
Give a different algorithm to solve this problem, with an asymptotically better running
time. In other words, you should design an algorithm with running time O(g(n)), where
limn→∞ g(n)
f(n) = 0.
So in particular, you are required to:
i. (10 Points) Analyze the simple algorithm described there (steps (1) and (2)).
ii. (10 Points) Design a faster algorithm and analyze its running time (step (3)).
3. (35 Points) Chapter 3 – Graphs.
(a) (10 Points) DFS vs. BFS : Given a connected graph G = (V, E), and a specific node
u ∈ V . You run BFS from u, and you find the BFS tree T rooted at u. You run DFS
from u, and you find the same DFS tree T rooted at u. Prove that G = T, i.e., G cannot
contain any edges that do not belong to T.
(b) (10 Points) Connectivity : Consider an undirected graph G = (V, E) with |V | = n
nodes. Assume that there are two nodes s and t with distance between them strictly
greater than n
2 .
2
• Prove that there must exist some node v, different from s,t, such that deleting v
from G disconnects s from t.
• Draw one example of G, s,t, v.
• Provide an algorithm that finds such a node v in O(m + n) time.
(c) (5 points) You are visiting Irvine and you want to explore the city of Irvine and visit as
much places as possible. You start your special tour from one place and you need to end
your special tour at the same place. You want to minimize the effort so you don’t want
to visit the same place twice (except for the start point). Assume that the city of Irvine
is represented as a directed graph with N node and M edges. Where a node is one place
to visit and an edge is the route to take to this place. Your special tour in this graph
starts at node u is a simple path that begins and ends at the same node u. Formally, a
special tour is path u, v1, v2, …, vi, …, u where vi are distinct and not equal to u for all i.
For every node in the given graph, tell whether it is possible for you to do
your special tour starting at that node.
Given: N = 5, M = 6
Graph represented as adjacency list as follows:
1 2
2 3
3 4 1
4 2 5
5
(d) (5 points) Indicate which one of these two graphs is bipartite. Justify your answer.
(e) (5 points) Robotics Motion Planning
In autonomous robot navigation problem, you want to design a controller that can navigate the robot within a bounded space. Assume that you have a localization algorithm
running. Basically the robot can localize itself within this room. Assume you can discritize the space of your room into discrete number of squares. The robot does not know
the structure of the room. Hence, you can not just draw a line between the initial position and the destination that the robot can follow. The visual capability of the robot
can only let it see the neighboring discrete locations. Can you design a controller on the
robot that can take the robot from one initial position to a destination position?
i. (2 points) Specify one of the algorithms that you learnt in the class to plan the
motion of the robot.
3
ii. (2 points) Draw the route that the robot will take to reach its destination.
iii. (1 points) After the robot reached its destination (From C to F) as indicated in the
discretized space below, the robot wants to go back to its initial location. Draw the
path that the robot will take. What is the distance that the robot had to cover (in
terms of discretized blocks) to return to its initial location?
Initial
location
Destination
Room with finite edges Space can be discretized
Food for the thought! – No Credit
We studied the stable matching problem. A variant to it is when you have unequal number of men
and women and the men and women only list who they are willing to marry to (not everyone and
not in order of preference). Now suppose that the bipartite graph you indicated in question 3.e,
if the blue set is the men and the red set is the women. The edge indicates a possible marriage
between this man and this woman. How many compatible marriages are possible at the same time,
and how can we find such an optimal matching?
In graph theory, this is called a matching problem of maximum cardinality. In the example
3.e, try to think of an algorithm to find this number; the maximum cardinality of the matching.
4
EECS215 Homework 2
Practicing Chapter 3 and 4
1. (5 Points) Chapter 3: Topological Order Consider the directed acyclic graph G in the figure
below. How many topological orderings does it have? Explain how you get computed it. List
the topological order.
a
b
d
c
e
f
2. (25 Points) Chapter 4: Scheduling
You have n distinct jobs, labeled J1, J2, …, Jn, which can be performed completely independently of one another. Each job consists of two stages: first it needs to be preprocessed on a
supercomputer, and then it needs to be finished on one of a local PCs. Let’s say that job Ji
needs pi seconds of time on the supercomputer, followed by fi seconds of time on a PC.
There are at least n PCs available on the premises, the finishing of the jobs can be performed
fully in parallel–all the jobs can be processed at the same time. However, the supercomputer
can only work on a single job at a time, so the system managers need to work out an order
in which to feed the jobs to the supercomputer. As soon as the first job in order is done on
the supercomputer, it can be handed off to a PC for finishing; at that point in time a second
job can be fed to the supercomputer; when the second job is done on the supercomputer, it
can proceed to a PC regardless of whether or not the first job is done (since the PCs work in
parallel); and so on.
(a) (10 Points) Design a schedule for the ordering of the jobs for the supercomputer that
minimize thecompletion time of the schedule. The definition of the completion time
of the schedule is the earliest time at which all jobs will have finished processing on the
PCs.
(b) (5 Points) What is the running time of your algorithm?
(c) (10 Points) Prove that the schedule that you designed is optimal.
Hint: 1- Think of an order of the jobs with some rational explained and try to find a counter
example until you find a good order. 2- You can use the exchange of argument to prove the
optimality the same way that we did in for minimizing the max. lateness problem.
1
3. (35 Points) Chapter 4 – Trees on Graphs (Midterm, Fall 2011).
Consider the undirected graph shown in the following figure. It consists of six nodes A,B,C,D,E,F
and nine edges with the shown edge costs.
A C E 6 5
1
2 3 4
4
5
F
2 3 4
B
5
D F 2 4
(a) (10 Points) Run Dijkstra’s algorithm to find the shortest paths from node A to all other
nodes. (Show the final answer and briefly describe the intermediate steps.)
(b) (10 Points) Run an algorithm of your choice (e.g., Kruskal, Prim, Reverse-Delete) and
find a minimum spanning tree. (Show the final answer and briefly describe how you got
there.)
(c) (10 Points) Is the minimum spanning tree of this graph unique? Justify your answer,
i.e., if the answer is yes, provide a proof; if the answer is no, provide a counter-example
and explain why this is the case.
(d) (5 Points) Consider the average distance from A to all other nodes, first by following
edges on the shortest path tree (a), let’s call it davg
SPT ; and then following edges on the
minimum spanning tree found in (b), let’s call it davg
MST . Which one is greater, davg
SPT or
davg
MST ? Does the same answer hold for any graph G = (V, E) and node A ∈ V , or is it
specific to this example?
4. (20 points) Chapter 4 – (Midterm, Fall 2019).
Consider the undirected graph below.
(a) (10 Points) Use an algorithm of your choice to find a Minimum Spanning Tree (MST)
for this graph. Show the final answer (draw the tree and write down its cost) and briefly
describe how you got the answer (which algorithm you used and some intermediate
steps).
(b) (10 Points) Is the MST for this graph unique? Justify your answer, i.e., if the answer is
yes, provide a proof; if the answer is no, provide a second MST as a counter-example.
2
5. (15 Points) Combinatorial Structure of Spanning Trees: Let G be a connected graph,
and T and T ′ two different spanning trees of G. We say that T and T ′ are neighbors if T
contains exactly one edge that is not in T ′
, and T ′ contains exactly one edge that is not in
T .
Now, from any graph G, we can build a (large) graph H as follows. The nodes of H are
the spanning trees of G, and there is an edge between two nodes of H if the corresponding
spanning trees are neighbors.
Is it true that, for any connected graph G, the resulting graph H is connected? Give a proof
that H is always connected, or provide an example (with explanation) of a connected graph
G for which H is not connected.
3
EECS215 Homework 3
Practicing Chapter 5 (DC) and 6 (DP)
1. (15 Points) Asymptotic running time of divide-and-conquer algorithms:
(a) (10 Points) Master Theorem. If T(n) = aT(n/b) + O(nd) for some constants a >
0, b > 1, d ≥ 0, then prove that it is:
T(n) =
!
“#
“$
O(nd) if d > logba
O(ndlogn) if d = logba
O(nlogba) if d < logba
(b) (5 Points) Then show that the divide-and-conquer algorithms we did in class Mergesort,
Binary Search, Matrix multiplication (classic) and Fast Matrix Multiplication (Strassen)
are all special cases of the Master Theorem. In particular, for each of these problems:
(i) give the parameters a, b, d for each algorithm and (ii) write down the recursive and
closed form equation for T(n).
2. (20 Points) Chapter 5: More recursions: Solve the following recurrence relations and
give a O bound for each of them:
(a) (5 Points) T(n) = 2T(n/3) + 1
(b) (5 Points) T(n) = 5T(n/4) + n
(c) (5 Points) T(n) = 9T(n/3) + n2
(d) (5 Points) T(n) = 2T(n − 1) + 1
3. (5 points) Chapter 6: Dynamic Programming: WIS via DAG Consider the intervals
below, each interval i has start time and a finish time and a weight vi indicated on top of the
interval i in the figure.
1
(a) (2.5 points) First create a DAG for these intervals as follows: Each node represents one
interval. For each interval i add edge (i, p(i)) of the length/weight of vi. You will need
two extra nodes One dummy sink node 0 for interval 0 (Remember in solving WIS we
say that p(1) = 0, so we need to have a dummy 0 interval as a sink node), plus another
dummy source node s connected with the last interval (node) 5. Add an edge from s
to 5 of length 0. For each interval i add edge (i, i − 1) of length 0. Second what is the
running time of creating this DAG, assuming that the intervals were initially sorted.
nlogn
(b) (2.5 points) Now given a general interval problem instance I let and let G(I) denote a
DAG constructed similar to the one you did in the previous problem. You need to find
the optimal solution for the weighted interval scheduling. Can you solve this problem
by running Dijkstra? Why?
4. (30 Points) Chapter 5: Variations of Knapsack Problem: Multidimensional Knapsack. Consider each item i = 1, …n has a weight wi, a volume zi and a value vi. You still
want to choose a subset of the n items so as to maximize total value. However, you now need
to meet two constraints: (1) the total weight of the selected items should not exceed a given
W and (2) the total volume of the selected items should not exceed a given Z.
(a) (10 Points) Design a DP algorithm that finds the optimal solution to this problem.
(b) (5 Points) Prove that your algorithm finds indeed the optimal solution.
(c) (5 Points) Analyze the running time.
(d) (10 Points) Consider the example problem from class: there are n = 5 items with values
{v1 = 1, v2 = 6, v3 = 18, v4 = 22, v5 = 28} and weights {w1 = 1, w2 = 2, w3 = 5, w4 =
6, w5 = 7}; the constraint on the total weight is W = 11. In addition, consider that the
items have volumes {z1 = 1, z2 = 10, z3 = 3, z4 = 2, z5 = 2} and that the total allowed
volume is Z = 15. Apply your algorithm to solve this example.
5. (30 Points) Chapter 5: Variations of Knapsack Problem: Knapsack with Repetition.
(a) (10 Points) Given n types of items (with weights w1, …, wn and values v1, …, vn, respectively), describe a DP algorithm that finds the most valuable set of items, subject to a
total weight constraint W. You are allowed to use repetition, i.e., to use items of the
same type multiple times. What is the asymptotic running time of your solution? Apply
your algorithm to the example with the following n = 4 items and capacity W = 10:
Item i 1 2 3 4
Weight wi 6 3 4 2
Value vi 30 14 16 9
(b) (10 Points) For the above example, draw the graph with nodes the DP subproblems and
edges the dependencies between them. Is it a DAG? Can you re-state this particular
variant of the KP problem as finding a path on this graph?
(c) (10 Points) Implement one of your DP algorithms, in Python, and run it on the example
above. You should submit your code – the grader should be able to run your code
with the input text file (format and example provided on Canvas – see KP all.ZIP and
README therein) and test that it gives the correct output!
2
(a) (10 Points) Given n types of items (with weights w1, …, wn and values v1, …, vn, respectively), describe a DP algorithm that finds the most valuable set of items, subject to a
total weight constraint W. You are allowed to use repetition, i.e., to use items of the
same type multiple times. What is the asymptotic running time of your solution? Apply
your algorithm to the example with the following n = 4 items and capacity W = 10:
Item i 1 2 3 4
Weight wi 6 3 4 2
Value vi 30 14 16 9
(b) (10 Points) For the above example, draw the graph with nodes the DP subproblems and
edges the dependencies between them. Is it a DAG? Can you re-state this particular
variant of the KP problem as finding a path on this graph?
(c) (10 Points) Implement one of your DP algorithms, in Python, and run it on the example
above. You should submit your code – the grader should be able to run your code
with the input text file (format and example provided on Canvas – see KP all.ZIP and
README therein) and test that it gives the correct output!
3
EECS215 Homework 4
Topic: Bellman-Ford SP & Network Flow (Ch.7)
1. (30) Shortest Paths on Graphs using Bellman-Ford Algorithm. Consider the
directed graph shown. The numbers on the edges indicate costs of these edges.
(a) (15 Points) Find the shortest paths from all nodes to destination t, using the BellmanFord algorithm. Show (some of) your intermediate steps and the final result in the
following form: [next hop][distance to t] for every node.
(b) (15 Points) After the algorithm reaches steady state, somebody cuts off edges e-t
and b-d at the same time. Use Bellman-Ford to recalculate the paths to t after the
change. Does the algorithm converge? If yes, show your calculations and the final
“[next hop][destination] for every node. If not, explain why.
2. (45 Points) Finding Max Flow. Consider the directed graph shown in the figure below.
The numbers on the edges indicate capacities.
(a) (15 Points) Find the max-flow from the source (node 1) to the sink (node 7).
(b) (15 Points) Identify the min-cut corresponding to the max-flow you found in (a).
(c) (15 Points) Now assume that the capacity of edge 2-6 changes from 9 to 2. Find the
max flow on this new graph without recomputing it from scratch, but starting from the
solution you found in (a) and incrementally updating it.
i. Describe an algorithm that does that incremental update.
1
ii. Argue that it indeed finds the optimal solution (max flow for the new graph).
iii. Analyze its running time (it should be less than running Ford-Fulkerson from scratch).
iv. Run your algorithm and report the new max flow.
3. (25 Points) Consider a set of mobile computing clients who need to be connected to one of
several possible base stations. We’ll suppose there are n clients, with the position of each
client specified by its (x, y) coordinates in the plane. There are also k base stations; the
position of each of these is specified by (x, y) coordinates as well.
For each client, we wish to connect it to exactly one of the base stations. Our choice of
connections is constrained in the following ways. There is a range parameter r ; a client can
only be connected to a base station that is within distance r. There is also a load parameter
L; no more than L clients can be connected to any single base station.
(a) (10 Points) Design a polynomial-time algorithm for the following problem. Given the
positions of a set for clients and a set of base stations, as well as the range and load parameters, decide whether every client can be connected simultaneously to a base station,
subject to the range and load conditions.
(b) (10 Points) Write the condition of the feasible solution (i.e., connecting all clients to
base stations).
(c) (5 Points) Analyze the running time of your algorithm.
2
EECS215 Homework 5
Topic: NP and NP-Completeness
1. (10 Points) Interval Scheduling. Consider the decision version of the problem:
Given a collection of intervals in the timeline, and a bound k, does the collection
contain a subset of non-overlapping intervals of size at least k?
For each statement below, state whether it is “True”, “False”, or “Unknown”, and briefly
justify your answer.
(a) (2 Points) Interval Scheduling is in P.
(b) (2 Points) Interval Scheduling is in NP.
(c) (2 Points) Interval Scheduling is NP-complete.
(d) (2 Points) Interval Scheduling ≤p Vertex Cover.
(e) (2 Points) Independent Set ≤p Interval Scheduling.
2. (35 Points) Vertex Cover on Trees.
For a graph G = (V, E) with |V | = n nodes and |E| = m edges, a vertex cover is defined as a
subset of nodes S ⊂ V s.t. that all edges e are covered (i.e., each edge is touched by at least
one node in S). Let us restrict our attention specifically to graphs that are trees.
(a) (15 Points) Design a greedy algorithm that finds the minimum size vertex cover on a
tree; or argue that such an algorithm does not exist.
(b) (15 Points) Design a dynamic programming algorithm that finds a minimum size vertex
cover on a tree in O(m +n) time. (Note: justify why the running time of your algorithm
is indeed O(m + n).)
(c) (5 Points) Is the polynomial time algorithm in (b) in contradiction with the fact that
the vertex cover is a well-known NP-complete problem? Please explain.
3. (30 Points) The Path Selection Problem.
Consider the path selection problem stated below:
Given a directed graph G = (V, E), a set of paths P1, P2, …Pc, and an integer k > 0,
is it possible to select at least k out of the c paths so that no two of the selected
paths share any nodes?
(a) (20 points) Prove that the path selection problem is NP-complete.
(b) (10 points) Is this a decision or an optimization problem? In which of the six broad
categories of NP-complete problems does this problem belong?
1
4. (25 Points) The Traveling Salesman Problem.
Let’s consider the optimization version of the traveling salesman problem (TSP) : We are
given a graph G(V, E) with n = |V | nodes. Each edge of the graph has an associated distance
dij . The goal is to find a tour, i.e., a cycle that passes through every node exactly once, with
minimum total distance.
(a) (6 Points) State the decision version of the TSP problem. Show that the decision version
of TSP is in NP.
(b) (6 Points) How would you solve the TSP problem using a brute force approach? What
would be the running time of that approach?
(c) (13 Points) Develop a dynamic programming approach that solves this problem and
report the running time of your algorithm.
2