Take-home Final SOlution



Maximum points: 44 + 8.5 make-up points

Due December 14th, 2017. 10:00 PM. Submit the solutions via GradeScope. No late submissions.


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

  1. 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.

    1. Algorithm Design by Kleinberg and Tardos

  1. 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.

  1. 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.

  1. Guidelines for writing a solution:

    1. Write your solutions neatly. Proofread them before you submit.

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

    1. 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.

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

    1. Provide a detailed proof of correctness.

    1. Analyze the time complexity of your algorithm.

    1. Quality of the high-level description of your algorithm, its correctness and e ciency are the prime determinants of your grade.

  1. Well-written 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 t1; ; tn and p1; ; pk 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 i-th 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 i1 < i2 < < ik n


such that for all 1 j k, we have tij = pj and j=1 v(ij) 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 polynomial-time 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 fx1; x2; : : : ; xng of points on the real line where the point xi has a gain wi 0 and a set of closed intervals [si; fi] for 1 i d where the cost of the i-th interval is ci > 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: Round-robin tournament

Assume that a round-robin 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 Pi beat player Pj and 0 otherwise. It is not possible in general to sort the players, since Pi may beat Pj , Pj may beat Pk, and Pk may beat Pi. 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 (one-one and onto) function on the integers f1; 2; : : : ; ng. In other words, A( (1); (2)) = A( (2); (3)) = = A( (n 1); (n)) = 1. The worst-case running time of the algorithm should be O(n log2 n). Any entry in the matrix can be accessed in constant time.

Design an O(n log2 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 bi 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 cij, which is the cost of interference between the two nodes. Both the bene ts and costs are non-negative 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 polynomial-time algorithm.

Provide a high-level 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 non-negativity, 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 maxq2Q d(q; C) is minimized, that is, the maximum distance from a supplier to a consumer is


minimized. Provide an e cient 3-approximation 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) = minr2R 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 c1; c2; : : : ; cn, nd a partition of f1; 2; : : : ; ng

into two subsets S1 and S2 that minimizes the quantity max(


ci). Consider the following

heuristic for some xed integer k:



  1. Choose the k largest ci’s.

  1. Find the optimal partition of these k integers

  1. Complete this into a partition of f1; 2; : : : ; ng by considering each of the remaining ci’s and adding it to the partition which at the time has the smallest sum.

Prove that this algorithm with O(2k + n) time complexity outputs a sum that is within (k + 3)=(k + 1) fraction of the optimal output.