COMP3027/COMP3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 8 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Extensions of flow networks
(a) What is flow networks with node supplies and demands?
(b) What is a circulation in a network with supplies and demands?
(c) How can one use flow networks to model supply and demand? 2. Reduction.
(a) What is a polynomial time reduction? (b) Is polynomial time reductions transitive?
(c) What is a reduction by simple equivalence? 3. Search vs optimization vs decision problems
(a) What is a search problem?
(b) What is an optimization problem?
(c) What is a decision problem?
(d) What are the search, optimization and decision versions of the max flow problem?
(e) What are the search, optimization and decision versions of other problem?
Tutorial
Problem 1
In the circulation with demands problem, we are given a directed graph G = (V, E), edge capacities c(e) and demands d(v) for each vertex v, where the demands d(v) can be positive, zero, or negative. A circulation is a function f on edges that satisfies:
• 0 ≤ f(e) ≤ c(e) (capacity constraints)
• f (e) − f (e) = d(v) (conservation constraints)
e intov e outofv
The goal is to determine if a circulation exists.
In the circulation with demand and lower bounds problem, we are also given lower bounds l(e) on edges and a circulation has to satisfy f(e) ≥ l(e) in addition to the above constraints.
Give a reduction from the circulation with demand and lower bounds problem to the circulation with demands problem.
Problem 2
Suppose you’re in charge of managing a fleet of airplanes and you’d like to create a flight schedule for them. Here’s a very simple model for this. Your market research has identified a set of m particular flight segments that that would be very lucrative if you could serve them; flight segment j is specified by four parameters: its origin airport, its destination airport, its departure time, and its arrival time. An example of six flights segments you’d like to serve with your planes over the course of a single day may include:
1
1. Brisbane (depart 6 am) – Sydney (arrive 7 am)
2. Sydney (depart 6:30 am) – Melbourne (arrive 8 am)
3. Sydney (depart 8 am) – Cairns (arrive 11 am)
4. Melbourne (depart 12 am) – Adelaide (arrive 2 pm)
5. Townsville (depart 2:15 pm) – Brisbane (arrive 4 pm)
6. Adelaide (depart 4:00 pm) – Perth (arrive 7 pm)
It is possible to use a single plane for a flight segment i, and then later for flight segment j, provided that:
1. the destination of i is the same as the origin of j and there’s enough time to perform maintenance on the plane in between; or
2. you can add a flight segment in between that gets the plane from the destination of i to the origin of j with adequate time in between.
For the example above you can group flights 1, 3, and 5 together by allocating an hour maintaince between each flight and adding an additional 1 hour flight between Cairns and Townsville for example.
Your goal based on the two conditions stated above is to determine if it is possible to service all m flights using at most k planes. In order to do this you will need to reuse planes as efficiently as possible.
Problem 3
We have seen dynamic programming algorithms for several sequence problems.
• In the Longest Common Subsequence (LCS) problem, we are given two sequences A and B and want
to find the longest sequence S that is a subsequence to both A and B.
• In the Longest Increasing Subsequence (LIS) problem, we are given a sequence A of integers and want
to find the longest subsequence S whose elements appear in sorted order from lowest to highest.
• A palindrome is a string that reads the same left to right as right to left. In the Longest Palindrome (LP) problem, we are given a string A and we want to find the longest subsequence S that is a palindrome.
In this tutorial problem, we will show that LIS and LP can be reduced to LCS. Suppose that there exists an algorithm for LCS that runs in time T(N) where N is the length of the longer of the input sequences A and B.
1. Give an algorithm for LIS that runs in T (n) + O(n log n) time, where n is the length of the input sequence A to LIS, by reducing LIS to LCS.
2. [Hard] Give an algorithm for LP that runs in T (n) + O(n) time, where n is the length of the input sequence A to LP, by reducing LP to LCS.
Problem 4
Recall that in the knapsack problem, we are given a set of n items with values and weights (the i-th item has value vi and weight wi), and a weight limit W.
• In the decision version of knapsack Knapsack-D, we are also given a query value q and our task is to determine if there exists a subset of items with total weight at most W and value at least q. Note that the required output is a Boolean (true/false).
2
• In the optimization version of knapsack Knapsack-O, our task is to compute the largest-possible value of any subset of items whose total weight is at most W. Note that the required output is a number.
• The search version Knapsack-S asks to find a subset of items whose total weight is at most W and whose value is as large as possible. Note that the required output is a subset of items.
Just as for the maximum bipartite matching problem, these versions are equivalent under polynomial-time reductions. Your task is to prove the harder direction of the equivalence.
1. Show that Knapsack-O ≤P Knapsack-D, i.e. given a black-box algorithm for Knapsack-D, construct an algorithm for Knapsack-O that uses at most a polynomial number of computational steps and a polynomial number of calls to the black-box algorithm.
2. Show that Knapsack-S ≤P Knapsack-O, i.e. given a black-box algorithm for Knapsack-O, construct an algorithm for Knapsack-S that uses at most a polynomial number of computational steps and a polynomial number of calls to the black-box algorithm.
Problem 5
Decision problems involve answering yes/no questions. For example, the independent set problem is “Given an undirected graph G and a number t, does G have an independent set of size t?”. (An independent set is a subset S of vertices such that no pair of vertices u, v in S share an edge.) In practice we are usually interested in solving optimization problems. For example, the maximum independent set problem is “Given an undirected graph G, find the largest in independent set in G”.
Assuming you have a polynomial time algorithm for the independent set problem, show how to solve the maximum independent set problem.
Problem 6
Consider a generalization of the interval scheduling problem where requests are not a single interval but a collection of d intervals. The objective is to choose a maximum number of requests that do not create any conflicts. More formally, we have n requests. The ith request has associated intervals I1i , I2i , . . . , Idi . A subset Sofrequestsisfeasibleifforalli,j∈S,anda,b∈[1,d]wehaveIai ∩Ibj =∅. Theobjectiveistoselecta maximum size set of feasible requests. In the decision version of this problem, we are also given an integer k and we need to determine if there exists a set of feasible requests of size at least k. Give a polynomial-time reduction from the Independent Set problem to the decision version of this problem.
Problem 7
[Advanced] Write a linear program for the maximum flow problem.
3