1 Million+ Step-by-step solutions

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A [2]. Continue in this manner for the first n - 1 elements of A. Write pseudo code for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n – 1 element’s rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ- notation.

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

Insertion sort can be expressed as a recursive procedure as follows. In order to sort A [1 ¬ n], we recursively sort A [1 ¬n -1] and then insert A[n] into the sorted array A [1 ¬ ¬n – 1]. Write a recurrence for the running time of this recursive version of insertion sort.

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudo code either iterative or recursive, for binary search, argue that the worst-case running time of binary search is Θ (lg n).

Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1 ¬ j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(n lg n)?

Describe a Θ (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

How can we modify almost any algorithm to have a good best-case running time?

Let f (n) and g (n) be asymptotically nonnegative functions. Using the basic definition of Θ- notation, prove that max (f (n), g (n)) = Θ (f (n) + g (n)).

Show that for any real constants a and b, where b > 0, (3.2) (n + a)b = Θ (nb).

Explain why the statement, "The running time of algorithm A is at least O (n2)," is meaningless.

Is 2n+1 = O (2n’’)? Is 22n = O (2n’’)?

We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions O(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m) for all n ≥ n0 and m ≥ m0}. Give corresponding definitions for Ω (g(n, m)) and Θ (g(n, m)).

Is the function ⌈lg n⌉! Polynomially bounded? Is the function ⌈lg lg n⌉! Polynomially bounded?

Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + cn, where c is a constant, is Ω(n lg n) by appealing to a recursion tree.

Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 - α)n) + cn, where α is a constant in the range 0 <α < 1 and c > 0 is also a constant.

Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly one time? What is the probability that you will hire exactly n times?

In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly twice?

Use indicator random variables to solve the following problem, which is known as the hatcheck problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hatcheck person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?

Let A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.

Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray contains no 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RANDOMIZE-IN-PLACE so that it’s associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.5 for your procedure.

Suppose that instead of swapping element A[i] with a random element from the subarray A[i ..n], we swapped it with a random element from anywhere in the array:

PERMUTE-WITH-ALL (A)

1 n ← length [A]

2 for i ← 1 to n

3 do swap A[i] ↔ A [RANDOM (1, n)]

Does this code produce a uniform random permutation? Why or why not?

PERMUTE-WITH-ALL (A)

1 n ← length [A]

2 for i ← 1 to n

3 do swap A[i] ↔ A [RANDOM (1, n)]

Does this code produce a uniform random permutation? Why or why not?

Professor Armstrong suggests the following procedure for generating a uniform random permutation:

PERMUTE-BY-CYCLIC (A)

1 n ← length [A]

2 offset ← RANDOM (1, n)

3 for i ← 1 to n

4 do dest ← i + offset

5 if dest > n

6 then dest ← dest -n

7 B[dest] ← A[i]

8 return B

Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

PERMUTE-BY-CYCLIC (A)

1 n ← length [A]

2 offset ← RANDOM (1, n)

3 for i ← 1 to n

4 do dest ← i + offset

5 if dest > n

6 then dest ← dest -n

7 B[dest] ← A[i]

8 return B

Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.

What are the minimum and maximum numbers of elements in a heap of height h?

Show that an n-element heap has height [lg n].

Show that in any sub tree of a max-heap, the root of the sub tree contains the largest value occurring anywhere in that sub tree.

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n). (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)

Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = ¬5, 13, 2, 25, 7, 17, 20, 8, 4¬.

Illustrate the operation of MAX-HEAP-INSERT (A, 10) on the heap A = 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1. Use the heap of Figure 6.5 as a model for the HEAP-INCREASE-KEY call.

Show that the running time of QUICKSORT is Θ (n2) when the array A contains distinct elements and is sorted in decreasing order.

Suppose that the splits at every level of quick sort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)

Why do we analyze the average-case performance of a randomized algorithm and not its worst-case performance?

Show that quick sort's best-case running time is Ω (n lg n).

Show that there is no comparison sort whose running time is linear for at least half of the n! input of length n. What about a fraction of 1/n of the inputs of length n? What about a fraction 1/2n?

Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a ¬ b] in O (1) time. Your algorithm should use Θ (n + k) preprocessing time.

You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. Show an Ω (n lg k) lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)

Which of the following sorting algorithms are stable: insertion sort, merge sort, heap sort, and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Show how to sort n integers in the range 0 to n2 - 1 in O (n) time.

What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(n lg n)?

Show that the second smallest of n elements can be found with n + ⌈lg n⌉ - 2 comparisons in the worst case.

In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.

Show how quick sort can be made to run in O (n lg n) time in the worst case.

Suppose that you have a "black-box" worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.

Let X [1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O (lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.

Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. From each well, a spur pipeline is to be connected directly to the main pipeline along a shortest path (either north or south), as shown in Figure 9.2. Given x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline (the one that minimizes the total length of the spurs)? Show that the optimal location can be determined in linear time.

We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time.

Suppose we use a hash function h to hash n distinct keys into an array T of length m, assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of {{k, l} : k ≠ l and h(k) = h(l)}?

Suggest how storage for elements can be allocated and deal located within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O (1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

Consider a version of the division method in which h (k) = k mod m, where m = 2p – 1 and k is a character string interpreted in radix 2p. Show that if string x can be derived from string y by permuting its characters, then x and y hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.

Define a family ℋ of hash functions from a finite set U to a finite set B to be ¬-universal if for all pairs of distinct elements k and l in U, Pr {h(k) = h(l)} ≤ ¬, where the probability is taken over the drawing of hash function h at random from the family ℋ. Show that an ¬-universal family of hash functions must have

What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or why not.

Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

An in order tree walk of an n-node binary search tree can be implemented by finding the minimum element in the tree with TREE-MINIMUM and then making n-1 calls to TREESUCCESSOR. Prove that this algorithm runs in Θ (n) time.

We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an in order tree walk. What are the worst-case and best-case running times for this sorting algorithm?

Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. If we color the root of T black but make no other changes to T, is the resulting tree a red-black tree?

Suppose that we "absorb" every red node in a red-black tree into its black parent, so that the children of the red node become children of the black parent. (Ignore what happens to the keys.) What are the possible degrees of a black node after all its red children are absorbed? What can you say about the depths of the leaves of the resulting tree?

Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.

Show that any arbitrary n-node binary search tree can be transformed into any other arbitrary n-node binary search tree using O (n) rotations. (Hint: First show that at most n - 1 right rotation suffices to transform the tree into a right-going chain.)

Suppose that the black-height of each of the sub trees α, β, γ, δ, ε in Figures 13.5 and 13.6 is k. Label each node in each figure with its black-height to verify that property 5 is preserved by the indicated transformation.

Professor Teach is concerned that RB-INSERT-FIXUP might set color [nil [T]] to RED, in which case the test in line 1 would not cause the loop to terminate when z is the root. Show that the professor's concern is unfounded by arguing that RB-INSERT-FIXUP never sets color [nil [T]] to RED.

Suggest how to implement RB-INSERT efficiently if the representation for red-black trees includes no storage for parent pointers.

Case 2 falls through into case 3, and so these two cases are not mutually exclusive.

Given an element x in an n-node order-statistic tree and a natural number i, how can the ith successor of x in the linear order of the tree be determined in O(lg n) time?

Observe that whenever the size field of a node is referenced in either OS-SELECT or OSRANK, it is used only to compute the rank of the node in the sub tree rooted at that node. Accordingly, suppose we store in each node its rank in the sub tree of which it is the root. Show how this information can be maintained during insertion and deletion. (Remember that these two operations can cause rotations.)

Show how to use an order-statistic tree to count the number of inversions (see Problem 2-4) in an array of size n in time O (n lg n).

Can the black-heights of nodes in a red-black tree be maintained as fields in the nodes of the tree without affecting the asymptotic performance of any of the red-black tree operations? Show how, or argue why not.

Can the depths of nodes in a red-black tree be efficiently maintained as fields in the nodes of the tree? Show how, or argue why not.

Describe an efficient algorithm that, given an interval i, returns an interval overlapping i that has the minimum low endpoint, or nil [T] if no such interval exists.

Show how to maintain a dynamic set Q of numbers that supports the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in Q. For example, if Q = {1, 5, 9, 15, 18, 22}, then MIN-GAP(Q) returns 18 - 15 = 3, since 15 and 18 are the two closest numbers in Q. Make the operations INSERT, DELETE, SEARCH, and MIN-GAP as efficient as possible, and analyze their running times.

VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that a representation of a rectangle consists of its minimum and maximum x- and y-coordinates. Give an O (n lg n)-time algorithm to decide whether or not a set of rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect.

Let R(i, j) be the number of times that table entry m[i, j] is referenced while computing other table entries in a call of MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is

Which is a more efficient way to determine the optimal number of multiplications in a matrix chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIXCHAIN? Justify your answer.

Show how to compute the length of an LCS using only 2 · min (m, n) entries in the c table plus O (1) additional space. Then show how to do this using min (m, n) entries plus O (1) additional space.

Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for which FASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station number j. Assuming that all transfer costs ti, j are nonnegative, show that the professor is wrong.

1 and aj < bj, or

2. p < q and ai = bi for all i = 0, 1, ..., p.

2. p < q and ai = bi for all i = 0, 1, ..., p.

The next two parts will prove inequality (2.3).

b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubble sort? How does it compare to the running time of insertion sort?

b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubble sort? How does it compare to the running time of insertion sort?

Let A[1 ¬ n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

a. List the five inversions of the array ¬2, 3, 8, 6, 1¬.

b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ (n lg n) worst-case time. (Hint: Modify merge sort.)

a. List the five inversions of the array ¬2, 3, 8, 6, 1¬.

b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ (n lg n) worst-case time. (Hint: Modify merge sort.)

a. Rank the following functions by order of growth; that is, find an arrangement g1, g2, ..., g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), ..., g29 = Ω(g30). Partition your list into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).

b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n) is neither O(gi(n)) nor Ω(gi(n)).

b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n) is neither O(gi(n)) nor Ω(gi(n)).

Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers.

Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

With a b-bit counter, we can ordinarily only count up to 2b – 1. With R.

Morris's probabilistic counting, we can count up to a much larger value at the expense of some loss of precision. We let a counter value of i represent a count of ni for i = 0, 1,..., 2b -1, where the ni form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0,

representing a count of n0 = 0. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If i = 2b - 1, then an overflow error is reported.

Otherwise, the counter is increased by 1 with probability 1/(ni+1 - ni), and it remains unchanged with probability 1 - 1/(ni+1 - ni).

If we select ni = i for all i ≥ 0, then the counter is an ordinary one. More interesting situations arise if we select, say, ni = 2i-1 for i > 0 or ni = Fi (the ith Fibonacci number-see Section 3.2). For this problem, assume that n2b-1 is large enough that the probability of an overflow error is negligible.

a. Show that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n.

b. The analysis of the variance of the count represented by the counter depends on the sequence of the ni. Let us consider a simple case: ni = 100i for all i ≥ 0. Estimate the variance in the value represented by the register after n INCREMENT operations have been performed

Morris's probabilistic counting, we can count up to a much larger value at the expense of some loss of precision. We let a counter value of i represent a count of ni for i = 0, 1,..., 2b -1, where the ni form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0,

representing a count of n0 = 0. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If i = 2b - 1, then an overflow error is reported.

Otherwise, the counter is increased by 1 with probability 1/(ni+1 - ni), and it remains unchanged with probability 1 - 1/(ni+1 - ni).

If we select ni = i for all i ≥ 0, then the counter is an ordinary one. More interesting situations arise if we select, say, ni = 2i-1 for i > 0 or ni = Fi (the ith Fibonacci number-see Section 3.2). For this problem, assume that n2b-1 is large enough that the probability of an overflow error is negligible.

a. Show that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n.

b. The analysis of the variance of the count represented by the counter depends on the sequence of the ni. Let us consider a simple case: ni = 100i for all i ≥ 0. Estimate the variance in the value represented by the register after n INCREMENT operations have been performed

The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:

BUILD-MAX-HEAP'(A)

1 heap-size [A] ← 1

2 for i ← 2 to length [A]

3 do MAX-HEAP-INSERT (A, A[i])

a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.

b. Show that in the worst case, BUILD-MAX-HEAP' requires Θ (n lg n) time to build an n-element heap.

BUILD-MAX-HEAP'(A)

1 heap-size [A] ← 1

2 for i ← 2 to length [A]

3 do MAX-HEAP-INSERT (A, A[i])

a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.

b. Show that in the worst case, BUILD-MAX-HEAP' requires Θ (n lg n) time to build an n-element heap.

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.

a. How would you represent a d-ary heap in an array?

b. What is the height of a d-ary heap of n elements in terms of n and d?

c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.

d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.

e. Give an efficient implementation of INCREASE-KEY (A, i, k), which first sets A[i] ← max (A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.

a. How would you represent a d-ary heap in an array?

b. What is the height of a d-ary heap of n elements in terms of n and d?

c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.

d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.

e. Give an efficient implementation of INCREASE-KEY (A, i, k), which first sets A[i] ← max (A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.

The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After the call to PARTITION, the left subarray is recursively sorted and then the right subarray is recursively sorted. The second recursive call in QUICKSORT is not really necessary; it can be avoided by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quick sort, which simulates tail recursion.

QUICKSORT'(A, p, r)

1 while p < r

2 do ▸ Partition and sort left subarray.

3 q ← PARTITION (A, p, r)

4 QUICKSORT'(A, p, q - 1)

5 p ← q + 1

a. Argue that QUICKSORT'(A, 1, length[A]) correctly sorts the array A. Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O (1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

b. Describe a scenario in which the stack depth of QUICKSORT' is Θ (n) on an n-element input array.

c. Modify the code for QUICKSORT' so that the worst-case stack depth is Θ (lg n). Maintain the O (n lg n) expected running time of the algorithm.

QUICKSORT'(A, p, r)

1 while p < r

2 do ▸ Partition and sort left subarray.

3 q ← PARTITION (A, p, r)

4 QUICKSORT'(A, p, q - 1)

5 p ← q + 1

a. Argue that QUICKSORT'(A, 1, length[A]) correctly sorts the array A. Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O (1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

b. Describe a scenario in which the stack depth of QUICKSORT' is Θ (n) on an n-element input array.

c. Modify the code for QUICKSORT' so that the worst-case stack depth is Θ (lg n). Maintain the O (n lg n) expected running time of the algorithm.

a. Suppose that each leaf of TA is labeled with the probability that it is reached given a random input. Prove that exactly n! Leaves are labeled 1/n! And that the rest are labeled 0.

b. Let D(T) denote the external path length of a decision tree T ; that is, D(T) is the sum of the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and let LT and RT be the left and right sub trees of T. Show that D(T) = D(LT) + D(RT) + k.

f. Show that for any randomized comparison sort B, there exists a deterministic comparison sort A that makes no more comparisons on the average than B does.

b. Let D(T) denote the external path length of a decision tree T ; that is, D(T) is the sum of the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and let LT and RT be the left and right sub trees of T. Show that D(T) = D(LT) + D(RT) + k.

f. Show that for any randomized comparison sort B, there exists a deterministic comparison sort A that makes no more comparisons on the average than B does.

Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. It is your task to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if they are of the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.

a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O (n) time.

b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O (n) time. (Note that the desired order here is the standard alphabetical order; for example, a < ab < b.)

b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O (n) time. (Note that the desired order here is the standard alphabetical order; for example, a < ab < b.)

Given a set of n numbers, we wish to find the i largest in sorted order using a comparison based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.

a. Sort the numbers, and list the i largest.

b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.

c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.

a. Sort the numbers, and list the i largest.

b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.

c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.

For n distinct elements x1, x2, ..., xn with positive weights w1, w2, ..., wn such that Σni =1 wi = 1, the weighted (lower) median is the element xk satisfying

a. Argue that the median of x1, x2, ..., xn is the weighted median of the xi with weights wi = 1/n for i = 1,2, ..., n.

b. Show how to compute the weighted median of n elements in O (n lg n) worst-case time using sorting.

c. Show how to compute the weighted median in Θ (n) worst-case time using a linear time median algorithm such as SELECT from Section 9.3.

The post-office location problem is defined as follows. We are given n points p1, p2, ..., pn with associated weights w1, w2, ..., wn. We wish to find a point p (not necessarily one of the input points) that minimizes the sum, where d(a, b) is the distance between points a and b.

d. Argue that the weighted median is a best solution for the 1-dimensional post-office location problem, in which points are simply real numbers and the distance between points a and b is d(a, b) = |a - b|.

e. Find the best solution for the 2-dimensional post-office location problem, in which the points are (x, y) coordinate pairs and the distance between points a = (x1, y1) and b = (x2, y2) is the Manhattan distance given by d (a, b) = |x1 - x2| + |y1 - y2|.

a. Argue that the median of x1, x2, ..., xn is the weighted median of the xi with weights wi = 1/n for i = 1,2, ..., n.

b. Show how to compute the weighted median of n elements in O (n lg n) worst-case time using sorting.

c. Show how to compute the weighted median in Θ (n) worst-case time using a linear time median algorithm such as SELECT from Section 9.3.

The post-office location problem is defined as follows. We are given n points p1, p2, ..., pn with associated weights w1, w2, ..., wn. We wish to find a point p (not necessarily one of the input points) that minimizes the sum, where d(a, b) is the distance between points a and b.

d. Argue that the weighted median is a best solution for the 1-dimensional post-office location problem, in which points are simply real numbers and the distance between points a and b is d(a, b) = |a - b|.

e. Find the best solution for the 2-dimensional post-office location problem, in which the points are (x, y) coordinate pairs and the distance between points a = (x1, y1) and b = (x2, y2) is the Manhattan distance given by d (a, b) = |x1 - x2| + |y1 - y2|.

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small relative to n, we can implement a different procedure that uses SELECT as a subroutine but makes fewer comparisons in the worst case.

a. Describe an algorithm that uses Ui (n) comparisons to find the ith smallest of n elements, where.

b. Show that, if i < n/2, then Ui (n) = n + O (T (2i) lg (n/i))..

c. Show that if i is a constant less than n/2, then Ui (n) = n + O (lg n)..

d. Show that if i = n/k for k ≥ 2, then Ui (n) = n + O (T (2n/k) lg k)..

a. Describe an algorithm that uses Ui (n) comparisons to find the ith smallest of n elements, where.

b. Show that, if i < n/2, then Ui (n) = n + O (T (2i) lg (n/i))..

c. Show that if i is a constant less than n/2, then Ui (n) = n + O (lg n)..

d. Show that if i = n/k for k ≥ 2, then Ui (n) = n + O (T (2n/k) lg k)..

A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution.

a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.

b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.

c. Show that Pr{X > 2lg n} ≤ 1/n.

d. Show that the expected length E[X] of the longest probe sequence is O (lg n).

a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.

b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.

c. Show that Pr{X > 2lg n} ≤ 1/n.

d. Show that the expected length E[X] of the longest probe sequence is O (lg n).

Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O (lg n/lg lg n) upper bound on E[M], the expected value of M.

a. Argue that the probability Qk that exactly k keys hash to a particular slot is given by Qk = (1/n)k(1 – 1/n) n–k (n/k)..

b. Let Pk be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that Pk ≤ n Q k..

c. Use Stirling's approximation, equation (3.17), to show that Qk < ek / kk..

d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk < 1/n2< for k ≥ k0 = c lg n/ lg lg n..

e. Argue that

Conclude that E[M] = O(lg n/ lg lg n)..

a. Argue that the probability Qk that exactly k keys hash to a particular slot is given by Qk = (1/n)k(1 – 1/n) n–k (n/k)..

b. Let Pk be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that Pk ≤ n Q k..

c. Use Stirling's approximation, equation (3.17), to show that Qk < ek / kk..

d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk < 1/n2< for k ≥ k0 = c lg n/ lg lg n..

e. Argue that

Conclude that E[M] = O(lg n/ lg lg n)..

Suppose that we are given a key k to search for in a hash table with positions 0, 1, ..., m - 1, and suppose that we have a hash function h mapping the key space into the set {0, 1, ..., m -1. The search scheme is as follows.

1. Compute the value i ← h(k), and set j ← 0.

2. Probe in position i for the desired key k. If you find it, or if this position is empty, terminate the search.

3. Set j ← (j + 1) mod m and i ← (i + j) mod m, and return to step 2. Assume that m is a power of 2.

a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants c1 and c2 for equation (11.5).

b. Prove that this algorithm examines every table position in the worst case.

1. Compute the value i ← h(k), and set j ← 0.

2. Probe in position i for the desired key k. If you find it, or if this position is empty, terminate the search.

3. Set j ← (j + 1) mod m and i ← (i + j) mod m, and return to step 2. Assume that m is a power of 2.

a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants c1 and c2 for equation (11.5).

b. Prove that this algorithm examines every table position in the worst case.

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called persistent. One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better. Consider a persistent set S with the operations INSERT, DELETE, and SEARCH, which we implement using binary search trees as shown in Figure 13.8(a). We maintain a separate root for every version of the set. In order to insert the key 5 into the set, we create a new node with key 5. This node becomes the left child of a new node with key 7, since we cannot modify the existing node with key 7. Similarly, the new node with key 7 becomes the left child of a new node with key 8 whose right child is the existing node with key 10. The new node with key 8 becomes, in turn, the right child of a new root r′ with key 4 whose left child is the existing node with key 3. We thus copy only part of the tree and share some of the nodes with the original tree, as shown in Figure 13.8(b).

Figure 13.8: (a) A binary search tree with keys 2, 3, 4, 7, 8, 10. (b) The persistent binary search tree that results from the insertion of key 5. The most recent version of the set consists of the nodes reachable from the root r′, and the previous version consists of the nodes reachable from r heavily shaded nodes are added when key 5 is inserted. Assume that each tree node has the field’s key, left, and right but no parent field. (See also Exercise 13.3-6.)

a. For a general persistent binary search tree, identify the nodes that need to be changed to insert a key k or delete a node y.

b. Write a procedure PERSISTENT-TREE-INSERT that, given a persistent tree T and a key k to insert, returns a new persistent tree T′ that is the result of inserting k into T.

c. If the height of the persistent binary search tree T is h, what are the time and space requirements of your implementation of PERSISTENT-TREE-INSERT? (The space requirement is proportional to the number of new nodes allocated.)

d. Suppose that we had included the parent field in each node. In this case, PERSISTENT-TREE-INSERT would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT would then require Ω (n) time and space, where n is the number of nodes in the tree.

e. Show how to use red-black trees to guarantee that the worst-case running time and space are O (lg n) per insertion or deletion.

Figure 13.8: (a) A binary search tree with keys 2, 3, 4, 7, 8, 10. (b) The persistent binary search tree that results from the insertion of key 5. The most recent version of the set consists of the nodes reachable from the root r′, and the previous version consists of the nodes reachable from r heavily shaded nodes are added when key 5 is inserted. Assume that each tree node has the field’s key, left, and right but no parent field. (See also Exercise 13.3-6.)

a. For a general persistent binary search tree, identify the nodes that need to be changed to insert a key k or delete a node y.

b. Write a procedure PERSISTENT-TREE-INSERT that, given a persistent tree T and a key k to insert, returns a new persistent tree T′ that is the result of inserting k into T.

c. If the height of the persistent binary search tree T is h, what are the time and space requirements of your implementation of PERSISTENT-TREE-INSERT? (The space requirement is proportional to the number of new nodes allocated.)

d. Suppose that we had included the parent field in each node. In this case, PERSISTENT-TREE-INSERT would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT would then require Ω (n) time and space, where n is the number of nodes in the tree.

e. Show how to use red-black trees to guarantee that the worst-case running time and space are O (lg n) per insertion or deletion.

Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point that has the largest number of intervals in the database overlapping it.

a. Show that there will always be a point of maximum overlap which is an endpoint of one of the segments.

b. Design a data structure that efficiently supports the operations INTERVAL-INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of maximum overlap.

a. Show that there will always be a point of maximum overlap which is an endpoint of one of the segments.

b. Design a data structure that efficiently supports the operations INTERVAL-INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of maximum overlap.

a. Suppose that m is a constant. Describe an O (n)-time algorithm that, given an integer n, outputs the (n, m)-Josephus permutation.

b. Suppose that m is not a constant. Describe an O (n lg n)-time algorithm that, given integers n and m, outputs the (n, m)-Josephus permutation.

b. Suppose that m is not a constant. Describe an O (n lg n)-time algorithm that, given integers n and m, outputs the (n, m)-Josephus permutation.

The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7- point problem. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time (see Chapter 34).

Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, with length approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the same set of points. Its length is approximately 25.58. J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible.

Describe an O (n2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate.

Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, with length approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the same set of points. Its length is approximately 25.58. J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible.

Describe an O (n2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate.

Join SolutionInn Study Help for

1 Million+ Textbook Solutions

Learn the step-by-step answers to your textbook problems, just enter our Solution Library containing more than 1 Million+ textbooks solutions and help guides from over 1300 courses.

24/7 Online Tutors

Tune up your concepts by asking our tutors any time around the clock and get prompt responses.