Introduction to Algorithms 3rd Edition solutions

Introduction to Algorithms 3
Comparison of running times For each function \(f(n)\) and time \(t\) in the following table, determine the largest size n of a problem that can be solved in time \(t\), assuming that the algorithm to solve the problem takes \(f(n)\) microseconds.

Introduction to Algorithms 3
Independent set An independent set of a graph G D .V; E/ is a subset V 0 V of vertices such that each edge in E is incident on at most one vertex in V 0 . The independent-set problem is to find a maximum-size independent set in G. a. Formulate a related decision problem for the independent-set probl

Introduction to Algorithms 3
Escape problem An n n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in Figure 26.11. We denote the vertex in the ith row and the j th column by .i; j /. All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points .i

Introduction to Algorithms 3
Ordering by asymptotic growth rates a. Rank the following functions by order of growth; that is, find an arrangement \(g_1,g_2,...,g_{30}\) of the functions satisfying \(g_1=\Omega (g_2),g_2=\Omega (g_3),...,g_{29}=\Omega (g_{30})\). Partition your list into equivalence classes such that functions \(

Introduction to Algorithms 3
Printing neatly Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n 406 Chapter 15 Dynamic Programming words of lengths l1; l2;:::;ln, measured in characters. We want to print this paragraph

Introduction to Algorithms 3
Weighted median For n distinct elements x1; x2;:::;xn with positive weights w1; w2;:::;wn such that Pn iD1 wi D 1, the weighted (lower) median is the element xk satisfying X xi <xk wi < 1 2 and X xi >xk wi 1 2 : For example, if the elements are 0:1; 0:35; 0:05; 0:1; 0:15; 0:05; 0:2 and each element e

Introduction to Algorithms 3
Inventory Planning The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for

Introduction to Algorithms 3
Algorithmic consulting Professor Gore wants to open up an algorithmic consulting company. He has identified n important subareas of algorithms (roughly corresponding to different portions of this textbook), which he represents by the set A D fA1; A2;:::;Ang. In each subarea Ak, he can hire an expert

Introduction to Algorithms 3
Radix trees Given two strings a D a0a1 :::ap and b D b0b1 :::bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either 1. there exists an integer j , where 0 j min.p; q/, such that ai D bi for all i D 0; 1; : : : ; j 1

Introduction to Algorithms 3
The 0-1 sorting lemma and columnsort A compare-exchange operation on two array elements Ai and Aj , where i<j , has the form COMPARE-EXCHANGE.A; i; j / 1 if Ai > Aj 2 exchange Ai with Aj After the compare-exchange operation, we know that Ai Aj . An oblivious compare-exchange algorithm operates solely

Introduction to Algorithms 3
Quicksort with equal element values The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not. a. Suppose that all element values are equal. What would be randomized quick

Introduction to Algorithms 3
Scheduling to minimize average completion time Suppose you are given a set S D fa1; a2;:::;ang of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be

Introduction to Algorithms 3
Viterbi algorithm We can use dynamic programming on a directed graph G D .V; E/ for speech recognition. Each edge .u; / 2 E is labeled with a sound .u; / from a fi- nite set of sounds. The labeled graph is a formal model of a person speaking Problems for Chapter 15 409 a restricted language. Each pa

Introduction to Algorithms 3
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U.S. dollars. Then, by c

Introduction to Algorithms 3
Planning an investment strategy Your knowledge of algorithms helps you obtain an exciting job with the Acme Computer Company, along with a $10,000 signing bonus. You decide to invest this money with the goal of maximizing your return at the end of 10 years. You decide to use the Amalgamated Investmen

Introduction to Algorithms 3
Chip testing Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professors test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip alway

Introduction to Algorithms 3
Nesting boxes A d-dimensional box with dimensions .x1; x2;:::;xd / nests within another box with dimensions .y1; y2;:::;yd / if there exists a permutation  on f1; 2; : : : ; dg such that x.1/ < y1, x.2/ < y2,..., x.d / < yd . a. Argue that the nesting relation is transitive. b. Describe an efficient

Introduction to Algorithms 3
Minimum path cover A path cover of a directed graph G D .V; E/ is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. A minimum path cover of G is a path cover containing the f

Introduction to Algorithms 3
Longest-probe bound for hashing Suppose that we use an open-addressed hash table of size m to store n m=2 items. a. Assuming uniform hashing, show that for i D 1; 2; : : : ; n, the probability is at most 2k that the ith insertion requires strictly more than k probes. b. Show that for i D 1; 2; : : :

Introduction to Algorithms 3
Longest simple path in a directed acyclic graph Suppose that we are given a directed acyclic graph G D .V; E/ with realvalued edge weights and two distinguished vertices s and t. Describe a dynamicprogramming approach for finding a longest weighted simple path from s to t. What does the subproblem gr