Archives

8. Consider the following map: a b c d 9. Design an algorithm for the following problem: Given a set of points in the Cartesian plane, determine whether all of them lie on the same circumference. 10. Write a program […]

This file contains the exercises, hints, and solutions for Chapter 1 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 1.1 1. Do some research on al-Khorezmi (also al-Khwarizmi), the man from whose name […]

3. a. The maximum-flow problem may have more than one optimal solution. In fact, there may be infinitely many of them if we allow (as the definition does) non-integer edge flows. For example, for any 0≤≤1,theflow depicted in the diagram […]

This file contains the exercises, hints, and solutions for Chapter 10 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 10.1 1. Consider the following version of the post office location problem: (Prob- lem […]

8. A crucial observation is that for any edge between a leaf and its parent there is a maximum matching containing this edge. Indeed, consider a leaf and its parent .Letbe a maximum matching in the tree. If ()is in […]

number of moves made by any algorithm that doesn’t disconnect already connected pieces is equal to −1 20 Note 2: This puzzle was published in Mathematics Magazine, vol. 26, p. 169. See also Problem 11 in Exercises 5.3 for a […]

This file contains the exercises, hints, and solutions for Chapter 11 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 11.1 1. Prove that any algorithm solving the alternating-disk puzzle (Problem 14 inExercises3.1)mustmakeatleast(+1)2moves to […]

8. The first-fit decreasing (FFD) approximation algorithm for the bin packing problem starts by sorting the items in nonincreasing order of their sizes and then acts as the first-fit algorithm. a. Apply FFD to the instance 9. a.BDesign a simple […]

This file contains the exercises, hints, and solutions for Chapter 12 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 12.1 1. a. Continue the backtracking search for a solution to the four-queens problem, […]

This file contains the exercises, hints, and solutions for Chapter 2 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 2.1 1. For each of the following algorithms, indicate (i) a natural size metric […]

The initial condition is verified immediately: (1) = 12=1 b. ()=(−1) + 1 for 1(1) = 0Solving it by backward substitutions (it’s almost identical to the factorial example–see Example 1 in the section) or by applying the formula for the […]

10. Mental arithmetic A10×10 table is filled with repeating numbers on its diagonals as shown below. Calculate the total sum of the table’s numbers in your head. (after [Cra07, Question 1.33]) 2 3 3 10 10 9 9 11 12 […]

The remaining ones are 2, 1, 3, 4 cost = 2+6+1+4 = 13 2, 1, 4, 3 cost = 2+6+8+9 = 25 2, 3, 1, 4 cost = 2+3+5+4 = 14 2, 3, 4, 1 cost = 2+3+8+7 = 20 […]

(a) Does the Hamming distance satisfy the three axioms of a distance metric listed in Problem 4? 6. BOdd pie fight There are ≥3people positioned in a field (Euclidean plane) so that each has a unique nearest neighbor. Each person […]

This file contains the exercises, hints, and solutions for Chapter 3 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 3.1 1. a. Give an example of an algorithm that should not be considered […]

Hints to Exercises 4.3 1. Use standard formulas for the numbers of these combinatorial objects. For 2. We traced the algorithms on smaller instances in the section. 3. See an outline of this algorithm in the section. 4. a. Trace […]

b. The recurrence relation for the number of weighing ()needed in the worst case is as follows: ()=(d3e)+1 for 1(1) = 0 For =3 the recurrence becomes (3)=(3−1)+1Solving it by backward substitutions yields (3)==log 3 c. The ratio of the […]

This file contains the exercises, hints, and solutions for Chapter 4 of the book ”Introduction to the Design and Analysis of Algorithms,” 3d edition, by Exercises 4.1 1. Ferrying soldiers A detachment of soldiers must cross a wide and deep […]

Solutions to Exercises 5.3 1. Algorithm Levels () //Computes recursively the number of levels in a binary tree 2. The algorithm is incorrect because it returns 0 for any binary tree; in particular, it returns 0 instead of 1 for […]

This file contains the exercises, hints, and solutions for Chapter 5 of the book ”Introduction to the Design and Analysis of Algorithms,” 3d edition, by Exercises 5.1 1. a. Write pseudocode for a divide-and-conquer algorithm for finding the position of […]

11. a. Any feasible state of the board can be described by an ×binary matrix, in which the element in the th row and th column is equal to 1 if and only if the corresponding panel is lit. Let […]

11. n/a 12. a. After the bunch of spaghetti rods is put in a vertical position on a tabletop, repeatedly take the tallest rod among the remaining ones out until no more rods are left. This will sort the rods […]

This file contains the exercises, hints, and solutions for Chapter 6 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 6.1 1. Consider the problem of finding the distance between the two closest num- […]

This file contains the exercises, hints, and solutions for Chapter 7 of the Exercises 7.1 1. Is it possible to exchange numeric values of two variables, say, and , without using any extra storage? 2. Will the comparison-counting algorithm work […]

b. The Boyer-Moore algorithm must compare the remaining −1char– 10. n/a 11. a. The following brute-force algorithm is based on straightforward check- ing of the circular shift definition. Algorithm RightCyclicShift([0 −1][0 −1]) //Checks by brute force whether string is a […]

for the number of binary trees mentioned in Section 8.3. Nor is it sur- prising that their solutions are very similar, too: namely, ()=(−1) for ≥1 where ()is the number of binary trees with nodes. Let us prove this assertion […]

This file contains the exercises, hints, and solutions for Chapter 8 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 8.1 1. What does dynamic programming have in common with divide-and-conquer? What is a […]

capacity  0123456 0 0 000000 8. For the problem of computing a binomial coefficient, we know in advance which cells of the table need to be computed. Therefore unnecessary computations can be avoided by the bottom-up dynamic programming algorithm […]

d. False (see, for example, the graph of Problem 1a). 3. Since the number of edges in a minimum spanning forest of a graph with ||vertices and ||connectedcomponentsisequalto||−||(this for- 4. Both algorithms work correctly for graphs with negative edge weights. […]

This file contains the exercises, hints, and solutions for Chapter 9 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by Exercises 9.1 1. Write pseudocode of the greedy algorithm for the change-making problem, with an […]

8. a. Write a program that constructs a Huffman code for a given English text and encode it. 9. Card guessing Design a strategy that minimizes the expected number of questions asked in the following game [Gar94]. You have a […]