Solutions of algorithm design manual

ArrayList; import java. BLUE ; lp. RED ; lp. Solution for this problem is first sort the input and choose x[0], x[length-1] , x[1], x[length-2] Arrays; import java. Follow Following. Avi's Programming Blog Join other followers. Sign me up. The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis.

The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms.

The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography. The second edition contains enough material to serve as the textbook for a standard Introduction to Algorithms course. I assume the reader has completed the equivalent of a second programming course, typically titled Data Structures or Computer Science II.

The book, and associated supporting material, stresses design over analysis. A full set of lecture slides integrated with audio and video lectures are freely available on line. Let me help teach your course! I have made several pedagogical improvements throughout the book. Solution One basic idea is to use two events with equal probability eight times and count one of these events and use this as our number.

Now zero and one happen with equal probability. We now generate enough numbers and count the ones which will be the number in rng How many calls do we need? Assume that all edges in the graph have distinct edge weights i.

Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample. Our minimum spanning tree is marked by the thick edges.

We are interested in the path between B and D. Would this change our MST? It would be our MST if , i. Your algorithm should run in O n time to receive full credit.

Solution We are interested into each path going from u to v. Now we can check which one is shorter and take this one. Prove the statement or give a counterexample. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit.

At such a time, a smart trader can trade one U. Thanks in , Words In breadth-first and depth-first search, an undiscovered node is marked discovered when it is first encountered, and marked processed when it has been completely searched.

At any given moment, several nodes might be simultaneously in the discovered state. Note, there may also be discovered nodes. Given pre-order and in-order traversals of a binary tree, is it possible to reconstruct the tree? If so, sketch an algorithm to do it.

If not, give a counterexample. Repeat the problem if you are given the pre-order and post-order traversals. Solution I made this example to simplify the process of reconstructing the binary tree. C, B and D have to be in the left subtree. Therefore B is the left child. Now we have C and D left in the left subtree. So C has to be the far left node and because B is the left child D have to be the right child of B. Now we have to find out where E and F belong.

We know that they belong to a right subtree to A. If you look at the preorder sequence you see that E has to be the root of the left subtree. Finally we look at the inorder sequence and see that F is before E. Present correct and efficient algorithms to convert an undirected graph G be- tween the following graph data structures. You must give the time complexity of each algorithm, assuming n vertices and m edges. Solution a addEdge start , end This algorithm also takes time.

Suppose an arithmetic expression is given as a tree. Give an O n algorithm for evaluating such an expression, where there are n nodes in the tree. Consider a set of movies M1, M2,. There is a set of customers, each one of which indicates the two movies they would like to see this weekend.

Movies are shown on Saturday evening and Sunday evening. Now, from any graph G, we can build a large graph H as follows. The nodes of H are the spanning trees of G, and there is an edge between two nodes of H if the corresponding spanning trees are neighbors. Is it true that for any connected graph G, the resulting graph H is connected?

Give a proof that H is always connected, or provide an example with explanation of a connected graph G for which H is not connected. Yes, H will always be connected. To show this, we prove the following Fact 3. Then there is a path in H from T to T 0 of length k. Each edge e is a fiber-optic cable that is owned by one of two companies — creatively named X and Y — and leased to CluNet.

Their plan is to choose a spanning tree T of G, and upgrade the links corresponding to the edges of T. CluNet management now faces the following problem: It is not at all clear to them whether there even exists a spanning tree T meeting these conditions, and how to find one if it exists. So this is the problem they put to you: give a polynomial-time algorithm that takes G, with each edge labeled X or Y , and either i returns a spanning tree with exactly k edges labeled X, or ii reports correctly that no such tree exists.

We begin by noticing two facts related to the graph H defined in the previous problem. Second, the solution given above in fact provides a polynomial-time algorithm to construct a T -T 0 path in H. We call a tree feasible if it has exactly k X-edges.

Our algorithm to search for a feasible tree is as follows. Using a minimum-spanning tree algorithm, we compute a spanning tree T with the minimum possible number a of X-edges. We then compute a spanning tree T with the maximum possible number b of X-edges. If k b, then there clearly there is no feasible tree. Give a proof or a counterexample. Label the edges arbitrarily as e1 ,. Note that all edge weights are now distinct, and the sorted order of the new weights is the same as some valid ordering of the original weights.

Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear through the coming winter. In the winter, people are high enough up in the mountains that they stop worrying about the length of roads and start worrying about their altitude — this is really what determines how difficult the trip will be.

So each road — each edge e in the graph — is annotated with a number ae that gives the altitude of the highest point on the road. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j. One year, they hit upon the following conjecture: The minimum spanning tree of G, with respect to the edge weights ae , is a minimum-altitude connected subgraph.

In an earlier problem, we claimed that there is a unique minimum spanning tree when the edge weights are distinct. Thus, thanks to the assumption that all ae are distinct, it is okay for us to speak of the minimum spanning tree. Initially, this conjecture is a somewhat counter-intuitive claim, since the minimum spanning tree is trying to minimize the sum of the values ae , while the goal of minimiz- 33 ing altitude seems to be asking for a fairly different thing.

But lacking an argument to the contrary, they begin considering an even bolder second conjecture: A subgraph V, E 0 is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree. Note that this second conjecture would immediately imply the first one, since the minimum spanning tree contains its own edges. Give a proof or a counter-example with explanation. Thus, T must be a minimum-altitude connected subgraph.

Deleting e from T partitions T into two connected components; and these two components represent a partition of V into sets A and B. The edge e is the minimum-altitude edge with one end in A and the other in B. Since any path in H from u to v must cross at some point from A to B, and it cannot use e, it must have height greater than ae. It follows that H cannot be a minimum-altitude connected subgraph.

The minimum spanning tree problem, on the other hand, is a minimization problem of a very different flavor: there are now just a finite number of possibilities for how the minimum might be achieved — rather than a continuum of possibilities — and we are interested in how to perform the computation without having to exhaust this huge finite number of possibilities.

One can ask what happens when these two minimization issues are brought together, and the following question is an example of this. Thus, at time t, it has cost fe t. Observe that the set of edges constituting the minimum spanning tree of G may change over time. A natural problem then becomes: find a value of t at which cG t is minimized. Your algorithm should run in time polynomial in the number of nodes and edges of the graph G.

First, we observe the following fact. It follows that for our time-changing edge costs, the set of edges in the minimum spanning tree only changes when two edge costs change places in the overall sorted order. This only happens when two of the parabolas defining the edge costs intersect. Moreover, we can enumerate all these crossing points in polynomial time. So our algorithm is as follows.

Finally, minimizing over the best solution found in each interval gives us the desired tree and value of t. We build a rooted tree T with n leaves, and we associate with each node v of T both leaves and internal nodes a height hv. We place each point in P at a distinct leaf in T.

Consider the pi -pj path P in the minimum spanning tree. Let p be the node immediately preceding p on P. You may assume all edge lengths are distinct.

A useful fact. The solution to b involves a sum of terms the sum of node degrees that we want to show is asymptotically sub-quadratic. Lemma: Let a1 , a2 ,. For each edge u, v on Q, we replace it with the path Puv , and then short-cut any loops that arise.

Summing the length edge-by-edge, the resulting path has length at most 3 times that of Q. One proof goes as follows. For suppose not, and consider any node v of H. Let S denote the set of neighbors of v. Notice that there is no edge joining two nodes of S, or we would have a cycle of length 3. Now let N S denote the set of all nodes with a neighbor in S. The weight of the Steiner tree is the weight of the tree T. Show that the problem of finding a minimum-weight Steiner tree on X can be solved in time O nO k.

We first claim that each extra node has degree at least 3 in T ; for if not, then the triangle inequality implies we can replace its two incident edges by an edge joining its two neighbors. Here we will consider the case in which G is a directed acyclic graph; that is, it contains no directed cycles. Can we conclude that A itself must be a minimum-cost arborescence in G? Give a proof, or a counter-example with explanation. We can conclude that A must be a minimum-cost arborescence.

We claim that in a directed acyclic graph, any set of edges satisfying i must also satisfy ii. Note that this is certainly not true in an arbitrary directed graph.

For surpose that A satisfies i but not ii , and let v be a node not reachable from r. Then if we repeatedly follow edges backwards starting at v, we must re-visit a node eventually, and this would be a cycle in G. In this problem we consider variants of the min-cost arborescence algorithm. Argue briefly that instead of looking for cycles, we can instead identify and contract strongly connected components of this subgraph. This new change is likely to turn more edges 0 cost. Suppose, now we find an arborescence T of 0 cost.

Prove that this T has cost at most twice the cost of the minimum cost arborescence in the original graph. Contract all 0-cost strongly connected components, and recursively apply the same procedure on the resulting graph till an arborescence is found.

Also, suppose that G has a node r such that there is a path from r to each other node in G. You are also given an integer k. Give a polynomialtime algorithm that either constructs an arborescence rooted at r of cost exactly k, or reports correctly that no such arborescence exists. Let V, F and V, F 0 be distinct arborescences rooted at r. Consider the set of edges that are in one of F or F 0 but not the other; and over all such edges, let e be one whose distance to r in its arborescence is minimum.

In V, F , there is some other edge w, v entering v. We claim that V, F 00 is also an arborescence rooted at r. Clearly F 00 has exactly one edge entering each node, so we just need to verify that there is an r-x path for every node x.

For those x such that the r-x path in V, F does not use v, the same r-x path exists in F Now consider an x whose r-x path in V, F does use v. Note that all the edges of P belong to F 00 , since they all belong to F and w, v is not among them. Performing a sequence of these operations, we can thereby transform V, F into V, F 0 one edge at a time. But each of these operations changes the cost of the arborescence by at most 1 since all edges have cost 0 or 1.

The swapping strategy is a little complicated — choosing the highest edge that is not in both arborescences — but some complication of this type seems necessary. You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values — so there are 2n values total — and you 40 may assume that no two values are the same.

However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the k th smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible. Give an algorithm that finds the median value using at most O log n queries.

First, let us compare the medians of the two databases. Let k be d 21 ne, then A k and B k are the medians of the two databases. Suppose A k B k would be the same with interchange of the role of A and B. Then one can see that B k is greater than the first k elements of A.

Therefore B k is at least 2k th element in the combine databases. Also they are less than the last d 12 ne elements of A. It means that they are less than the median and we ican eliminate them as well.

Let h 1 0 A be the remaining parts of A i. Now we eliminate b 12 nc elements that are less than the median, and the same number of elements that are greater than median. It is clear that the median of the remaining elements is the same as the median of the original set of elements. We can find a median in the remaining set using recursion for A0 and B 0.

Formally, the algorithm is the following. Let Q n be the number of queries asked by our algorithm to evaluate median n,a,b. Most people had the overall structure of the solution right, but a number of solutions were missing some of the central ideas in the proof. 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.