Algorithm design manual solutions

Specifically, the proof needed to make two key points: first, in the recursive call, the median remains in the set of numbers considered; and second, the median value in the recursive call will in fact be the same as the median value in the original call.

Note that the second, stronger point is enough; but a number of people made the only the first poin and not the second. Also, the algorithm needs to keep track of the fact that the databases cannot always be divided evenly in half for the recursive call. Finally, there was a category of solution which worked roughly as follows. A pointer m is kept into database D1. This type of solution is close to something that works correctly; however, to prevent this kind of difficult, it is necessary to keep track of a full interval in each database, rather than just a single pointer.

Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1 ,. We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Give an O n log n algorithm to count the number of significant inversions between two orderings.

The magic of hidden surface removal is that you can often compute things faster than your intuition suggests. You are given n non-vertical lines in the plane, labeled L1 ,. We will make the assumption that no three of the lines all meet at a single point. The accompanying figure gives an example. We first label the lines in order of increasing slope, and then use a divideand-conquer approach. The first and third lines will always be visible; the second will be visible if and only if it meets the first line to the left of where the third line meets the first line.

We first recursively compute the sequence of visible lines among L1 ,. We also compute, in this recursive call, the sequence of points a1 ,.

Notice that a1 ,. We know that Li1 will be visible, because it has the minimum slope among all the lines in this list; similarly, we know that Ljq will be visible, because it has the maximum slope. We merge the sorted lists a1 ,. This takes O n time. Now, for each k, we consider the line that is uppermost in L at x-coordinate ck , and the line that is uppermost in L0 at x-coordinate ck. Since this is what we need to return to the next level of the recursion, the algorithm is complete.

Each smart-card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Assume that the only feasible operations you can do with the cards are to pick two of them and plug them in to the equivalence tester.

Show how to decide the answer to their question with only O n log n invocations of the equivalence tester. We give two solutions for this problem. The first solution is a divide and conquer algorithm, which is easier to think of. The second solution is a clever linear time algorithm. Via divide and conquer: Let e1 ,. We will recursively run the algorithm on the two sides, and will assume that if the algorithm finds an equivalence class containing more than half of the cards, then it returns a sample card in the equivalence class.

So at least one of the two recursive calls will return a card that has equivalence class x. So if a majority card is returned on either side we must test this card against all other cards. If a card is returned then test this against all other cards If no card with majority equivalence has yet been found then call the algorithm recursively for S2.

If a card is returned then test this against all other cards Return a card from the majority equivalence class if one is found The correctness of the algorithm follows from the observation above: that if there is a majority equivalence class, than this must be a majority equivalence class for at least one of the two sides. To analyze the running time, let T n denote the maximum number of tests the algorithm does for any set of n cards. The algorithm has two recursive calls, and does at most 2n tests outside of the recursive calls.

In linear time: Pair up all cards, and test all pairs for equivalence. If n was odd, one card is unmatched. For each pair that is not equivalent, discard both cards. For pairs that are equivalent, keep one of the two. Keep also the unmatched card, if n is odd. We can call this subroutine Eliminate. The observation that leads to the linear time algorithm is as follows. This is true, as when we discard both cards in a pair, then at most one of them can be from the majority equivalence class.

When we are down to a single card, then its 45 equivalence is the only candidate for having a majority. Your clients are distributed between the East Coast and the West Coast, and this leads to the following question. It depends on the distribution of client demands for that month. Given a sequence of n months, a plan is a sequence of n locations — each one equal to either NY or SF — such that the ith location indicates the city in which you will be based in the ith month.

The cost of a plan is the sum of the operating costs for each of the n months, plus a moving cost of M for each time you switch cities. The plan can begin in either city. The problem is: Given a value for the moving cost M , and sequences of operating costs N1 ,. Such a plan will be called optimal. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge.

With each node vi , we associate a positive integer weight wi. Consider, for example, the 5-node path drawn in the figure below. The weights are the numbers drawn next to the nodes. While some node remains in G Pick a node vi of maximum weight.

Add vi to S. Delete vi and its neighbors from G. Let S1 be the set of all vi where i is an odd number. Let S2 be the set of all vi where i is an even number. The running time should be polynomial in n, independent of the values of the weights. The greedy algorithm will pick the middle node, while the maximum weight independent set consists of the first and third. The given algorithm will pick the first and third nodes, while the maximum weight independent set consists of the first and fourth.

Xn is the value we want, and we can compute Sn by tracing back through the computations of the max operator. Since we spend constant time per iteration, over n iterations, the total running time is O n. We say that G is a line-graph if it has the following properties: i Each edge goes from a node with a lower index to a node with a higher index. That is, every directed edge has the form vi , vj with i Long-path n Array M [1.

In your example, say what the correct answer is and also what the above algorithm finds. You should prove that your algorithm works correctly, and include a brief analysis of the running time. Suppose you are managing the construction of billboards on the Stephen Daedalus Memorial Highway, a heavily-traveled stretch of road that runs west-east for M miles.

The possible sites for billboards are given by numbers x1 , x2 ,. You cannot build two billboards within less than 5 miles of one another on the highway. You cannot build a billboard within less than 5 miles of the western or eastern ends of the highway.

A subset of sites satisfying these two restrictions will be called valid. Then the optimal solution would be to place billboards at x1 and x3 , for a total revenue of Give an algorithm that takes an instance of this problem as input, and returns the maximum total revenue that can be obtained from any valid subset of sites. The running time of the algorithm should be polynomial in n. Include a brief analysis of the running time of your algorithm, and a proof that it is correct.

Your job can only run on one of the machines in any given minute. You also have the ability to move your job from one machine to the other; but doing this costs you a minute of time in which no processing is done on your job.

The problem is: Given values a1 , a2 ,. Such a strategy will be called optimal. Note that your plan can start with either of the machines A or B in minute 1. A B Minute 1 10 5 Minute 2 1 1 Minute 3 1 20 Minute 4 10 20 Then the plan of maximum value would be to choose A for minute 1, then move for minute 2, and then B for minutes 3 and 4. EndWhile In your example, say what the correct answer is and also what the above algorithm finds. Here are two examples: A B Minute 1 2 1 Minute 2 10 20 The greedy algorithm would choose A for both steps, while the optimal solution would be to choose B for both steps.

The optimal solution would be to choose A for all four steps. Either on machine A, or in the process of moving from machine B. A symmetric formula holds for Opt i, B. Let Opt i be the maximum value of a plan in minutes 1 through i. Now, in minute i, we ask: when was the most recent minute in which we moved? Each iteration takes O n time to compute the maximum, so the total running time is O n2.

There are a number of variations on the above recurrence, but they all break on this example. Suppose during this time period, they wanted to buy shares on some day, and sell all these shares on some later day. They want to know: when should they have bought and when should they have sold in order to have made as much money as possible?

If there was no way to make money during the n days, you should report this instead. Your investment friends were hoping for something a little better. Show how to find the correct numbers i and j in time O n. For certain possibly large values of k, they want to study what they call k-shot strategies. A k-shot strategy is a collection of m pairs of days b1 , s1 ,. Your goal is to design an efficient algorithm that determines, given the sequence of prices, the k-shot strategy with the maximum possible return.

Since k may be relatively large in these simulations, your running time should be polynomial in both n and k; it should not contain k in the exponent. By transaction i, j , we mean the single transaction that consists of buying on day i and selling on day j. Let P [i, j] denote the monetary return from transaction i, j. Let Q[i, j] denote the maximum profit obtainable by executing a single transaction somewhere in the interval of days between i and j.

Now, let us say that an m-exact strategy is one with exactly m non-overlapping buysell transactions. Let M [m, d] denote the maximum profit obtainable by an m-exact strategy on days 1,. You may assume that the functions fi are non-decreasing: if h We also record the value of k that produces this maximum.

Finally, we output A[n, H], and can trace-back through the entries using the recorded values to produce the optimal distribution of time. A large collection of mobile wireless devices can naturally form a network in which the devices are the nodes, and two devices x and y are connected by an edge if they are able to directly communicate with one another e.

Such a network of wireless devices is a highly dynamic object, in which edges can appear and disappear over time as the devices move around. For instance, an edge x, y might disappear as x and y move far apart from one another and lose the ability to communicate directly. In a network that changes over time, it is natural to look for efficient ways of maintaining a path between certain designated nodes. There are two opposing concerns in maintaining such a path: we want paths that are short, but we also do not want to have to change the path frequently as the network structure changes.

Here is a way we might model this problem. Suppose we have a set of mobile nodes V , and at a particular point in time there is a set E0 of edges among these nodes. As the nodes move, the set of edges changes from E0 to E1 , then to E2 , then to E3 , and so on to an edge set Eb.

We will assume that each of these graphs Gi is connected. Our goal is to produce a sequence of paths P0 , P1 ,. We want the paths to be relatively short. We also do not want there to be too many changes — points at which the identity of the path switches.

Formally, we define changes P0 , P1 ,. We define the cost of the sequence of paths P0 , P1 ,. Give a polynomial-time algorithm to find the shortest such path. While trying to find the last path Pb , we have several choices. Another option is to use the shortest s-t path, call it Sb , in Gb. This adds l Sb and the cost of change K to the cost function. We will use subproblems Opt i to denote minimum cost of the solution for graphs G0 ,. To compute Opt n it seems most useful to think about where the last changeover occurs.

We have to deal separately with the special case when there are no changes at all. The running time of O n2 D is also immediate from the for loops in the problem, there are two nested for loops for for m and one for d. This means that the internal part of the loop gets invoked O nD time. The internal part of this for loop takes O n time, as we explicitly maintain the optimal solutions.

The running time can be improved to O nD by not maintaining the S array, and only recovering the solution later, once the values are known. Give an O mn algorithm to decide whether this alignment is the unique minimum-cost alignment between A and B. Let Q denote the s-t path corresponding to the given alignment. Thus, G0 has the same structure as G, but a new cost function c0.

Now we claim that path Q is a minimum-cost s-t path in G0 if and only if it is the unique minimum-cost s-t path in G. Q is the unique minimum-cost A-B alignment if and only if this cost matches c0 Q. Consider the following inventory problem.

Let di denote the number of sales you expect in month i. You can store at most S trucks, and it costs C to store a single truck for a month. You receive shipments of trucks by placing orders for them, and there is a fixed ordering fee of K each time you place an order regardless of the number of trucks you order. You start out with no trucks. First, storage: it costs C for every truck on hand that is not needed that month.

Scecond, ordering fees: it costs K for every order placed. Give an algorithm that solves this problem in time that is polynomial in n and S. The subproblems will be as follows: The optimum way to satisfy orders 1,.

Let OP T i, s denote the value of the optimal solution for this subproblem. You are consulting for an independently operated gas-station, and it faced with the following situation. They have a large underground tank in which they store gas; the tank can hold up to L gallons at one time.

Ordering gas is quite expensive, so they want to order relatively rarely. For each order they need to pay a fix price P for delivery in addition to the cost of the gas ordered. However, it cost c to store a gallon of gas for an extra day, so ordering too much ahead increases the storage cost.

They are planning to close for winder break, and want their tank to be empty, as they are afraid that any gas left in the tank would freeze over during break. Luckily, years of experience gives them accurate projections for how much gas they will need each day until winter break. Assume that the tank is empty at the end of day 0. Give an algorithm to decide which days they should place orders, and how much to order to minimize their total cost. The following two observations might help. The problem they are currently working on is based on the concatenation of sequences of genetic material.

For this purpose, they have a set of shorter sequences B1 , B2 ,. Give a polynomial-time algorithm for this problem. Suppose we want to replicate a file over a collection of n servers, labeled S1 , S2 ,. The access cost is 0 if Si holds a copy of the file. We will require that a copy of the file be placed at server Sn , so that all such searches will terminate, at the latest, at Sn.

Recall that a copy is always placed at Sn. The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers.

Give a polynomial-time algorithm to find a configuration of minimum total cost. We will say that an enriched subset of V is one that contains at most one node not in X. There are O 2k n enriched subsets. The overall approach will be based on dynamic programming: For each enriched subset Y , we will compute the following information, building it up in order of increasing Y. For such a Y , one can compute f Y in time O n2.

Let T1 ,. Each of these is an enriched set of size less than Y , and T1 , T 0 , and T 00 are the minimum Steiner trees on these sets.

This can be done by looking up values we have already computed, since each of Y1 , Y 0 , Y 00 is a smaller enriched set. If any of these sums is less than f Y , we return the corresponding tree as the minimum Steiner tree; otherwise we return the minimum spanning tree on Y. Your friends have been studying the closing prices of tech stocks, looking for interesting patterns. They have the closing price for a given stock recorded for n days in succession; let these prices be denoted P [1], P [2],.

A rising trend in these prices is a subsequence of the prices P [i1 ], P [i2 ],. Add 1 to L. Endif Endfor In your example, give the actual length of the longest rising trend, and say what the above algorithm returns. The running time of your algorithm should be polynomial in the length of the input.

Consider the Bellman-Ford minimum-cost path algorithm from the text, assuming that the graph has no negative cost cycles. This algorithm is both fairly slow and also memory-intensive. In many applications of dynamic programming, the large memory requirements can become a bigger problem than the running time. The goal of this problem is to decrease the memory requirement. The pseudo-code ShortestPath G, s, t in the text maintains an array M [ This suggests he following idea: can we decrease the memory needs of the algorithm to O n by maintaining only two columns of the M matrix at any time?

Moreover, it uses O n3 time and only O n space. You do not need to prove these facts. The problem is: where is the shortest path? The usual way to find the path involves tracing back through the M [i, v] values, using the whole matrix M , and we no longer have that. The goal of this problem is to show that if the graph has no negative cycles, then there is enough information saved in the last column of the matrix M , to recover the shortest path in O n2 time.

Give an algorithm FindPath t, G, B that uses only the array B and the graph G to find the the minimumcost path from s to t in O n2 time. The problem of searching for cycles in graphs arises naturally in financial trading applications. Consider a firm trades shares in n different companies. Here we allow the rate r to be fractional, i. A trading cycle for a sequence of shares i1 , i2 ,. After such a sequence of trades, one ends up with shares in the same company i1 that one starts with.

Trading around a cycle is usually a bad idea, as you tend to end up with fewer shares than what you started with. But occasionally, for short periods of time, there are opportunities to increase shares. We will call such a cycle an opportunity cycle, if trading along the cycle increases the number of shares. This happens exactly if the product of the ratios along the cycle is above 1.

In analyzing the state of the market, a firm engaged in trading would like to know if there are any opportunity cycles. Give a polynomial time algorithm that finds such an opportunity cycle, if one exists. Hint: a useful construction not covered in lecture is the augmented graph used in the statement 4. The ranking officer decides to postpone the picnic, and must notify everyone by phone. Here is the mechanism she uses to do this. Each ROTC person on campus except the ranking officer reports to a unique superior officer.

Thus, the reporting hierarchy can be described by a tree T , rooted at the ranking officer, in which each other node v has as a parent node u equal to his or her superior officer. Conversely, we will call v a direct subordinate of u. To notify everyone of the postponement, the ranking officer first calls each of her direct subordinates, one at a time. As soon as each subordinate gets the phone call, he or she must notify each of his or her direct subordinates one at a time.

The process continues this way, until everyone has been notified. Note that each person in this process can only call direct subordinates on the phone; for example, in Figure 1, A would not be allowed to call C.

Now, we can picture this process as being divided into rounds: In one round, each person who has already learned of the postponement can call one of his or her direct subordinates on the phone. The number of rounds it takes for everyone to be notified 67 depends on the sequence in which each person calls their direct subordinates. For example, in Figure 1, it will take only two rounds if A starts by calling B, but it will take three rounds if A starts by calling D. Give an efficient algorithm that determines the minimum number of rounds needed for everyone to be notified, and outputs a sequence of phone calls that achieves this minimum number of rounds.

The fastest broadcast scheme is for A to call B in the first round. In the second round, A calls D and B calls C. If A were to call D first, then C could not learn the news until the third round. The ranking officer must notify her subordinates in some sequence, after which they will recursively broadcast the message as quickly as possible to their subtrees. Using the solution to that problem, she should talk to the subordinates in decreasing order of the time it takes for their subtrees recursively to be notified.

Hence, we have the following set of sub-problems: for each subtree T 0 of T , we define x T 0 to be the number of rounds it takes for everyone in T 0 to be notified, once the root has the message.

Suppose now that T 0 has child subtrees T1 ,. The full algorithm builds up the values x T 0 using the recurrence, beginning at the leaves and moving up to the root. If subtree T 0 has d0 edges down from its root i. By tracing back through the sorted orders at every subtree, we can also reconstruct the sequence of phone calls that should be made. Some years ago, never mind how long precisely, having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world.

We have a maximum line length of L. We will assume we have a fixed-width font, and ignore issues of punctuation or hyphenation. A formatting of W consists of a partition of the words in W into lines. Give an efficient to find a partition of a set of words W into valid lines, so that the sum of the squares of the slacks of all lines including the last line is minimized.

This problem is very similar in flavor to the segmented least squares problem. We observe that the last line ends with word wn and has to start with some word wj ; breaking off words wj ,. For each fixed i, we can compute all Si,j in O n time by considering values of j in increasing order; thus, we can compute all Si,j in O n2 time. As noted above, the optimal solution must begin the last line somewhere at word wj , and solve the sub-problem on the earlier lines optimally.

Each iteration of the loop takes time O n , and there are O n iterations. Thus the total running time is O n2. By tracing back through the array OP T , we can recover the optimal sequence of line breaks that achieve the value OP T [n] in O n additional time.

This describes the whole problem; we can make it a little more explicit as follows. We say that a string x0 is a repetition of x if it is a prefix of xk for some number k. We say that a string s is an interleaving of x and y if its symbols can be partitioned into two not necessarily contiguous subsequences s0 and s00 , so that s0 is a repetition of x and s00 is a repetition of y.

So each symbol in s must belong to exactly one of s0 or s Give an efficient algorithm that takes strings s, x, and y, and decides if s is an interleaving of x and y. Our problem can be phrased as: is s an interleaving of x0 and y 0? Let s[j] denote the j th character of s, and let s[1 : j] denote the first j characters of s. We define the analogous notation for x0 and y 0.

We know that if s is an interleaving of x0 and y 0 , then its last character comes from either x0 or y 0. Thus, we consider sub-problems defined by prefixes of x0 and y 0. We can build these up via the following loop. There are O n2 values M [i, j] to build up, and each takes constant time to fill in from the results on previous sub-problems; thus the total running time is O n2.

You are also given a maximum s-t flow in G, defined by a flow value fe on each edge e. Show how to find a maximum flow in the resulting capacitated graph in time O m , where m is the number of edges in G. Consider the following problem.

You are also given a parameter k. Give a polynomial-time algorithm to solve this problem. We identify a minimum s-t cut A, B , and delete k of the edges out of A. Indeed, consider any cut A, B of G0.

However, G can have many minimum cuts, so we have to be careful in how we try making this idea precise. Give an algorithm that takes a flow network G, and classifies each of its nodes as being upstream, downstream, or central.

The running time of your algorithm should be within in a constant factor of the time required to compute a single maximum flow. But this is a contradiction, since no edge in the residual graph can go from the source side to the sink side of any minimum cut.

These are the upstream and downstream nodes respectively; the remaining nodes are central. Give a polynomial time algorithm to decide whether G has a unique minimum s-t cut.

In a standard minimum s-t cut problem, we assume that all capacities are non-negative; allowing an arbitrary set of positive and negative capacities results in an NP-complete problem. Thus, ce can be negative for edges e that have at least one end equal to either s or t.

Give a polynomial-time algorithm to find an s-t cut of minimum value in such a graph. Despite the new non-negativity requirements, we still define the value of an s-t cut A, B to be the sum of the capacities of all edges e for which the tail of e is in A and the head of e is in B. Let mij denote the entry in row i and column j. A diagonal entry is one of the form mii for some i.

Swapping two columns is defined analogously. We say that M is re-arrangeable if it is possible to swap some of the pairs of rows and some of the pairs of columns in any sequence so that after all the swapping, all the diagonal entries of M are equal to 1. Thus, there is a collection of n wireless laptops; there is also have a collection of n wireless access points, to which a laptop can connect when it is in range. To make sure that all the wireless connectivity software is working correctly, you need to try having laptops make contact with access points, in such a way that each laptop and each access point is involved in at least one connection.

This way, by trying out all the connections specified by the pairs in T , we can be sure that each laptop and each access point have correctly functioning software. Then the set of pairs laptop 1, access point 1 , laptop 2, access point 2 , laptop 3, access point 3 would form a test set of size three.

Recall that we assume each laptop is within range of at least one access point, and each access point p has at least one laptop within range of it. Back in the euphoric early days of the Web, people liked to claim that much of the enormous potential in a company like Yahoo! So if the user has told Yahoo! But deciding on which ads to show to which people involves some serious computation behind the scenes. Suppose that the managers of a popular Web site have identified k distinct demographic groups G1 , G2 ,.

These groups can overlap; for example G1 can be equal to all residents of New York State, and G2 can be equal to all people with a degree in computer science. The site has contracts with m different advertisers, to show a certain number of copies of their ads to users of the site.

Now, consider the problem of designing a good advertising policy — a way to show a single ad to each user of the site. Suppose at a given minute, there are n users visiting the site. Give an efficient algorithm to decide if this is possible, and if so, to actually choose an ad to show each user.

P j rj , and the sink has a demand of P j rj. Now, if there is a valid circulation in this graph, then there is an integer circulation.

In such a circulation, one unit of flow on the edge vi , wj means that we show an ad 75 from advertiser j to person i. With this meaning, each advertiser shows their required number of ads to the appropriate people.

Conversely, if there is a way to satisfy all the advertising contracts, then we can construct a valid circulation as follows. We place a unit of flow on each edge vi , wj for which i is shown an ad from advertiser j; we put a flow on the edge wj , t equal to the number of ads shown from advertiser j; and we put a unit of flow on each edge s, vi for which person i sees an ad.

Thus, there is a valid circulation in this graph if and only if there is a way to satisfy all the advertising contracts; and the flow values in an integer-valued circulation can be used, as above, to decide which ads to show to which people. So if the situation were really this simple, your friends would just port all n applications, P achieving a total benefit of i bi.

Nevertheless, it might still pay off to port some of the other applications, accruing the associated benefit and incurring the expense of the interaction between applications on different systems. So this is the question they pose to you: which of the remaining applications, if any, should be moved?

Now, let X, Y be the minimum s-v1 cut in G. Consider a variation on the previous problem. Consider the following definition. We are given a set of n countries that are engaged in trade with one another. For each country i, we have the value si of its budget surplus; this number may be positive or negative, with a negative number indicating a deficit. For each pair of countries i, j, we have the total value eij of all exports from i to j; this number is always non-negative.

We say that a subset S of the countries is free-standing if the sum of the budget surpluses of the countries in S, minus the total value of all exports from countries in S to countries not in S, is non-negative. Give a polynomial-time algorithm that takes this data for a set of n countries, and decides whether it contains a non-empty free-standing subset that is not equal to the full set.

We define the following flow network. There will be a node vi for each country i, plus a source s and sink t. We will say that a set of checks constitutes a reconciliation if for each person i, the total value of the checks received by i, minus the total value of the checks written by i, is equal to the imbalance of i.

Let there be an edge u, v if person u owes person v money and let the cost of this edge be the amount of money owed. Note that if u, v exists, then v, u does not exist since we may just adjust for the difference.

Let G be the undirected graph obtained from G by ignoring the directions of the edges. We repeatedly run BF S on G to find undirected cycles and eliminate them as specified below. Since there are m edges, we go through the outer loop at most m times. Note that in each iteration, we preserve all imbalances; so at the end we will have a reconciliation.

Further, we preserve the direction of the edges since we modify according to the direction and only by the minimum cost edge in the cycle; thus, at the end, we will have a consistent reconciliation. There were three key points in the proof. First, imbalances are preserved as each cycle is processed. Second, directions of edges are never reversed, so the resulting reconciliation is consistent.

It seems hard to find a rule for choosing augmenting paths that will guarantee this, and also hard to prove that this property holds. Of course, if one explicitly cancels cycles after finding the flow, then this would be correct by analogy with the above solution. Consider a set of mobile computing clients in a certain town who each need to be connected to one of several possible base stations. 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. Your goal is to design a polynomial-time algorithm for the following problem.

Given two sets S1 and S2 each of size n , and a number x , describe an O n log n algorithm for finding whether there exists a pair of elements, one from S1 and one from S2 , that add up to x. The mode of a set of numbers is the number that occurs most frequently in the set. The set 4, 6, 2, 4, 3, 1 has a mode of 4. Give an efficient and correct algorithm to compute the mode of a set of n numbers.

Assume that we are given n pairs of items as input, where the first item is a number and the second item is one of three colors red, blue, or yellow. Further assume that the items are sorted by number. Give an O n algorithm to sort the items by color all reds before all blues before all yellows such that the numbers for identical colors stay sorted.

For example: 1,blue , 3,red , 4,blue , 6,yellow , 9,red should become 3,red , 9,red , 1,blue , 4,blue , 6,yellow. Take a sequence of 2n real numbers as input. Design an O n log n algorithm that partitions the numbers into n pairs, with the property that the partition minimizes the maximum sum of a pair. Learn more. Asked 10 years, 10 months ago. Active 1 year, 2 months ago. Viewed 88k times. Steve Steve 4, 10 10 gold badges 53 53 silver badges 79 79 bronze badges. Link is working now: www2.

The solutions are up once again! Add a comment. Active Oldest Votes.