...

Problem Set 6

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Problem Set 6
COS 423
Theory of Algorithms
Spring 2013
Problem Set 6
This assignment is due Wednesday, April 17 at 11pm via electronic submission. Collaboration is
permitted, according
the rules specified in the syllabus.
Kidney to
exchange
Read Section 7.13 in Algorithm Design.
1. Kidney exchange problem. The kidney-exchange graph is a directed graph G = (V, E) in
which a vertex v ∈ V corresponds to a donor-patient pair and an edge (v, w) ∈ E means
that the donor kidney from v is immunologically compatible with the patient from w. Let
pvw > 0 be a weight that measures the utility of the donor kidney from v to the patient
from w. A directed cycle in the graph represents a possible swap, with each patient in the
cycle obtaining the kidney from the previous donor. A kidney exchange is a collection of
node-disjoint cycles.1 The cycles must be disjoint because no donor can give more than one
kidney and no patient should receive more than one kidney. Thekidney exchange problem is
to find a kidney exchange of maximum weight. Design an O n3 algorithm for the problem
by formulating it as an assignment problem.
1
2
2
3
5
4
9
7
5
3
8
4
1
6
1
2
6
5
9
4
weight = 3 + 5 + 7 + 8 + 4 = 27
2
3
7
5
3
8
6
4
1
6
weight = 2 + 5 + 8 + 6 + 1 + 9 = 31
8
Note that in an optimal solution, some patients may not receive kidneys (e.g., if the weight
of edge 3 → 5 is increased to 9).
2. A double-ended queue or deque is a data type in which elements can be inserted or removed
from either the front or back. It supports the following four core operations: InsertFront,
RemoveFront, InsertBack, and RemoveBack. Prove that you can implement a deque
with three stacks so that each deque operation takes a constant amortized number of stack
operations. That is, starting from an empty deque, any sequence of n deque operations takes
O (n) stack operations. You may use only O (1) extra memory beyond the memory for the
three stacks.
You must prove this using a potential function argument.
1
Remark: in the real version of the problem, there is a constraint on the length of the cycles because the transplants
must be performed simultaneously (to prevent donor-patient pairs from backing out of the exchange after receiving
their kidneys).
1
3. Analyze the algorithm described below for a data type that supports the following operations:
• Insert(x): insert element x into the dictionary.
• Search(x): is element x in the dictionary?
The data structure consists of a sequence of arrays, where array ai has length 2i . Each array
is sorted and is either empty or full. The array ai is full if and only if the ith least-significant
bit in the binary representation of n is one. For example, if the array contains the n = 11
Dictionary
elements {10, 3, 44, 55, 56, 61, 70, 77, 88, 89, 96}, then there will be arrays of size 1, 2, and 8,
perhaps populated as in this diagram:
insert 55
a0
96
a1
10
a0
a1
70
a2
a3
33
44
55
56
61
77
88
89
a2
10
55
70
96
a3
33
44
55
56
n = 1110 = 10112
61
77
88
89
n = 1210 = 11002
• Search(x): do a binary search in each full array.
• Insert(x): create a new array of size 1 with the new key. If array a0 is empty, then set
a0 equal to the new array; otherwise merge the new array with a0 to create a new array
of size 2. If a1 is empty, set a1 equal to the new array of size 2; otherwise, merge the
new array of size 2 with a1 to create a new array of size 4. Repeat until reaching an
empty array.
1
Prove that, starting from an empty dictionary, any sequence of n insert operations takes
O (n log n) time in the worst case. Also prove that searching in a data structure with n
elements takes O log2 n time in the worst case.
4. Modify the binomial heap data structure to achieve the following asymptotic amortized running times.
operation
Make-Heap
Insert
Extract-Min
Decrease-Key
Union
Find-Min
time
1
1
log n
log n
1
1
You must prove this using an accounting-based argument.
2
Fly UP