$30.00
Description
Maximum points: 44 + 8.5 makeup points
Due December 14th, 2017. 10:00 PM. Submit the solutions via GradeScope. No late submissions.
Instructions:

There are six problems in the test. Solve exactly ve problems. All problems carry equal weight.

You are only allowed to consult the following textbook, your own course (Fall 2017 CSE 202) lecture notes and the course website. You should not consult any other source including the Web. You are also not allowed to consult with any other person.


Algorithm Design by Kleinberg and Tardos


This test is designed to give you an opportunity to demonstrate your understanding of the principles of algorithm design, analysis and application. Consequently, you are required to work by yourself in answering the problems. Group work or consultation with others is not allowed.
You can check with the instructor or the TAs for any clari cation during the o ce hours. Please do not send any email or questions over Piazza regarding the nal examination.

Each problem requires that you achieve an algorithm with certain complexity (for example, polynomial time, linear time, etc.). To the extent the problem permits latitude in terms of complexity (for example, polynomial time provides considerable latitude), obtain the most e cient algorithm.

Guidelines for writing a solution:


Write your solutions neatly. Proofread them before you submit.



Write a highlevel description of your algorithm. State the main ideas and strategies used in developing your algorithm. Include all important details.



Describe brie y how you would implement your algorithm providing important implementation details. You may sparingly use pseudo code to describe the details of your implementation if you believe the code will bring more clarity.

We are not expecting you to write down the obvious details of your implementation. Describe only the unusual aspects of your implementation.


If you are using a modi ed version of a wellknown algorithm, show clearly what your modi cations are. If you are using a wellknown algorithm without any modi cations, it is enough to specify how you plan to apply the algorithm.



Provide a detailed proof of correctness.



Analyze the time complexity of your algorithm.



Quality of the highlevel description of your algorithm, its correctness and e ciency are the prime determinants of your grade.


Wellwritten solutions will be rewarded. Characteristics of good solutions: correct solution, logical coherence, an appropriate balance between completeness and succinctness, and an orderly presentation of ideas. Excessively long solutions will be penalized. We do not expect you to include information not relevant to the solution.
1

If you include two di erent solutions to the same problem, we are not obligated to consider both the solutions.
Problem 1: Sequence matching
Let T and P be respectively two sequences t_{1}; ; t_{n} and p_{1}; ; p_{k} of characters such that k n. The characters range over a nite alphabet . With each position of T , we associate a nonnegative value. Let v(i) denote the value for the ith position in T for 1 i n. Find a matching subsequence of T for the pattern P that maximizes the sum of values. That is, nd the sequence of indices 1 i_{1} < i_{2} < < i_{k} n
P_{k}
such that for all 1 j k, we have t_{i}_{j} = p_{j} and _{j=1} v(i_{j}) is maximized. Design an e cient algorithm for this problem, prove its correctness and analyze its complexity.
To deserve any credit, you must present a polynomialtime algorithm along with a complete solution.
You must strive for as e cient an algorithm as possible.
Problem 2: Covering points with gain
Describe an e cient algorithm that, given a set fx_{1}; x_{2}; : : : ; x_{n}g of points on the real line where the point x_{i} has a gain w_{i} 0 and a set of closed intervals [s_{i}; f_{i}] for 1 i d where the cost of the ith interval is c_{i} > 0, select a set of closed intervals so that the sum of the gains of the points covered by the selected intervals less the sum of the costs of the selected intervals is maximized. Design an e cient algorithm, prove its correctness and determine its complexity.
Note: You can assume that the gains and costs are nonnegative integers.
Problem 3: Roundrobin tournament
Assume that a roundrobin tournament is played among n players. That is, each player plays once against all n 1 other players. There are no draws and the results of all games are given in a matrix A. Entry A(i; j) is 1 if player P_{i} beat player P_{j} and 0 otherwise. It is not possible in general to sort the players, since P_{i} may beat P_{j} , P_{j} may beat P_{k}, and P_{k} may beat P_{i}. In other words, the results are not necessarily transitive. We are interested in a weak sorting as follows. Design an algorithm to arrange the
players in an order P _{(1)}; P _{(2)}; : : : ; P _{(n)} such that P _{(1)} beat P _{(2)}, P _{(2)} beat P _{(3)}, : : :, P _{(n} _{1)} beat P _{(n)} where is a permutation (oneone and onto) function on the integers f1; 2; : : : ; ng. In other words, A( (1); (2)) = A( (2); (3)) = = A( (n 1); (n)) = 1. The worstcase running time of the algorithm should be O(n log_{2} n). Any entry in the matrix can be accessed in constant time.
Design an O(n log_{2} n) algorithm and prove its correctness.
Problem 4: Cellular network
Consider the problem of selecting nodes for a cellular network. Any number of nodes can be chosen from a nite set V of potential sites. We are also given an undirected graph G = (V; E) over the set of sites where an edge ij 2 E connects sites i and j. We know the bene t b_{i} 0 of selecting a node at site i. However, if sites i and j are selected as nodes and if there is an edge ij 2 E between them, then the bene t is o set by c_{ij}, which is the cost of interference between the two nodes. Both the bene ts and costs are nonnegative integers. Find an e cient algorithm to determine the subset of sites as the nodes for the cellular network such that the sum of the node bene ts less the interference costs is as large as possible.
Design an e cient polynomialtime algorithm.
Provide a highlevel description of your algorithm, prove its correctness, and analyze its time complexity.
Problem 5: Center selection with producers and consumers
Consider the following variation of the center selection problem. You are given a set V of n vertices and a distance function d(:; 🙂 that satis es the nonnegativity, symmetry and triangle inequality properties. However, the vertices are partitioned into two categories, producers and consumers. Let P V denote the set of vertices corresponding to the producers and Q = V P denote the set of vertices corresponding to the consumers. You are also given an integer k 1. The objective is to select a set C of k producers so that max_{q2Q} d(q; C) is minimized, that is, the maximum distance from a supplier to a consumer is
2
minimized. Provide an e cient 3approximation algorithm for the problem. Prove its correctness, bound its approximation ratio and determine its complexity.
For a set of points R and a point s, we de ne d(s; R) = min_{r2R} d(s; r). You can assume that the distance between two vertices can be computed in constant time.
Problem 6: Approximation algorithm
Consider the following optimization problem: Given n integers c_{1}; c_{2}; : : : ; c_{n}, nd a partition of f1; 2; : : : ; ng
into two subsets S_{1} and S_{2} that minimizes the quantity max( 
c_{i}; 
c_{i}). Consider the following 
heuristic for some xed integer k: 
^{P}i2S_{1} 
^{P}i2S_{2} 

Choose the k largest c_{i}’s.

Find the optimal partition of these k integers

Complete this into a partition of f1; 2; : : : ; ng by considering each of the remaining c_{i}’s and adding it to the partition which at the time has the smallest sum.
Prove that this algorithm with O(2^{k} + n) time complexity outputs a sum that is within (k + 3)=(k + 1) fraction of the optimal output.
3