Questions and Answers of Practical Introduction To Data Structures

Consider the so-called "algorithm for algorithms" in Section 15.1. Is this really an algorithm? Review the definition of an algorithm from Section 1.4. Which parts of the definition apply, and which
Single-elimination tournaments are notorious for their scheduling difficulties. Imagine that you are organizing a tournament for \(n\) basketball teams (you may assume that \(n=2^{i}\) for some
Explain why the cost of splitting a list of six into two lists of three to find the minimum and maximum elements requires eight comparisons, while splitting the list into a list of two and a list of
Write out a table showing the number of comparisons required to find the minimum and maximum for all divisions for all values of \(n \leq 13\).
Present an adversary argument as a lower bounds proof to show that \(n-1\) comparisons are necessary to find the maximum of \(n\) values in the worst case.
Present an adversary argument as a lower bounds proof to show that \(n\) comparisons are necessary in the worst case when searching for an element with value \(X\) (if one exists) from among \(n\)
Section 15.6 claims that by picking a pivot that always discards at least a fixed fraction \(c\) of the remaining array, the resulting algorithm will be linear. Explain why this is true. Hint: The
Show that any comparison-based algorithm for finding the median must use at least \(n-1\) comparisons.
Show that any comparison-based algorithm for finding the second-smallest of \(n\) values can be extended to find the smallest value also, without requiring any more comparisons to be performed.
Show that any comparison-based algorithm for sorting can be modified to remove all duplicates without requiring any more comparisons to be performed.
Show that any comparison-based algorithm for removing duplicates from a list of values must use \(\Omega(n \log n)\) comparisons.
Given an undirected graph GGGG, the problem is to determine whether or not GGGG is connected. Use an adversary argument to prove that it is necessary to look at all
(a) Write an equation to describe the average cost for finding the median.(b) Solve your equation from part (a).
(a) Write an equation to describe the average cost for finding the \(i\) th-smallest value in an array. This will be a function of both \(n\) and \(i, \mathbf{T}(n, i)\).(b) Solve your equation from
Suppose that you have \(n\) objects that have identical weight, except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of the scale and see
Imagine that you are organizing a basketball tournament for 10 teams. You know that the merge insert sort will give you a full ranking of the 10 teams with the minimum number of games played. Assume
Write the complete algorithm for the merge insert sort sketched out in Section 15.7.Data From Section 15.7:We will use binary insert to place the losers. However, we are free to choose the best
Here is a suggestion for what might be a truly optimal sorting algorithm. Pick the best set of comparisons for input lists of size 2 . Then pick the best set of comparisons for size 3 , size 4 , size
Implement the median-finding algorithm of Section 15.6. Then, modify this algorithm to allow finding the \(i\) th element for any value \(i
Solve Towers of Hanoi using a dynamic programming algorithm.
There are six permutations of the linesin floyd's algorithm. Which ones give a correct algorithm? for (int k=0; k
Show the result of running Floyd's all-pairs shortest-paths algorithm on the graph of Figure 11.25. 10 3 2 3 2 20 5 15 6 10 3 5 11
The implementation for Floyd's algorithm is inefficient for adjacency lists because the edges are visited in a bad order when initializing array \(\mathrm{D}\). What is the cost of of this
State the greatest possible lower bound that you can for the all-pairs shortestpaths problem, and justify your answer.
Show the Skip List that results from inserting the following values. Draw the Skip List after each insert. With each value, assume the depth of its corresponding node is as given in the list. value
If we had a linked list that would never be modified, we can use a simpler approach than the Skip List to speed access. The concept would remain the same in that we add additional pointers to list
What is the expected (average) number of pointers for a Skip List node?
Write a function to remove a node with given value from a Skip List.
Write a function to find the \(i\) th node on a Skip List.
Complete the implementation of the Skip List-based dictionary begun in Section 16.3.1.Section 16.3.1: 16.3.1 Skip Lists Skip Lists are designed to overcome a basic limitation of array-based and
Implement both a standard \(\Theta\left(n^{3}ight)\) matrix multiplication algorithm and Strassen's matrix multiplication algorithm. Using empirical testing, try to estimate the constant factors for
Consider this algorithm for finding the maximum element in an array: First sort the array and then select the last (maximum) element. What (if anything) does this reduction tell us about the upper
Use a reduction to prove that squaring an \(n \times n\) matrix is just as expensive (asymptotically) as multiplying two \(n \times n\) matrices.
Use a reduction to prove that multiplying two upper triangular \(n \times n\) matrices is just as expensive (asymptotically) as multiplying two arbitrary \(n \times n\) matrices.
(a) Explain why computing the factorial of \(n\) by multiplying all values from 1 to \(n\) together is an exponential time algorithm.(b) Explain why computing an approximation to the factorial of
Consider this algorithm for solving the CLIQUE problem. First, generate all subsets of the vertices containing exactly \(k\) vertices. There are \(O\left(n^{k}ight)\) such subsets altogether. Then,
Write the 3 SAT expression obtained from the reduction of SAT to 3 SAT described in Section 17.2.1 for the expression\[(a+b+\bar{c}+d) \cdot(\bar{d}) \cdot(\bar{b}+\bar{c}) \cdot(\bar{a}+b)
Draw the graph obtained by the reduction of SAT to the CLIQUE problem given in Section 17.2.1 for the expression\[(a+\bar{b}+c) \cdot(\bar{a}+b+\bar{c}) \cdot(\bar{a}+b+c)
A Hamiltonian cycle in graph \(\mathbf{G}\) is a cycle that visits every vertex in the graph exactly once before returning to the start vertex. The problem HAMILTONIAN CYCLE asks whether graph
Assuming that VERTEX COVER is \(\mathcal{N} \mathcal{P}\)-complete, prove that CLIQUE is also \(\mathcal{N} \mathcal{P}\)-complete by finding a polynomial time reduction from VERTEX COVER to CLIQUE.
We define the problem INDEPENDENT SET as follows.INDEPENDENT SETInput: A graph \(\mathbf{G}\) and an integer \(k\).Output: YES if there is a subset \(\mathbf{S}\) of the vertices in \(\mathbf{G}\) of
Define the problem PARTITION as follows:PARTITIONInput: A collection of integers.Output: YES if the collection can be split into two such that the sum of the integers in each partition sums to the
Imagine that you have a problem \(\mathbf{P}\) that you know is \(\mathcal{N P}\)-complete. For this problem you have two algorithms to solve it. For each algorithm, some problem instances of
The last paragraph of Section 17.2.3 discusses a strategy for developing a solution to a new problem by alternating between finding a polynomial time solution and proving the problem \(\mathcal{N
Prove that the set of real numbers is uncountable. Use a proof similar to the proof in Section 17.3.1 that the set of integer functions is uncountable. 17.3.1 Uncountability Before proving that the
Prove, using a reduction argument such as given in Section 17.3.2, that the problem of determining if an arbitrary program will print any output is unsolvable. 17.3.2 The Halting Problem Is
Prove, using a reduction argument such as given in Section 17.3.2, that the problem of determining if an arbitrary program executes a particular statement within that program is unsolvable.
Prove, using a reduction argument such as given in Section 17.3.2, that the problem of determining if two arbitrary programs halt on exactly the same inputs is unsolvable. 17.3.2 The Halting Problem
Prove, using a reduction argument such as given in Section 17.3.2, that the problem of determining whether there is some input on which two arbitrary programs will both halt is unsolvable. 17.3.2 The
Prove, using a reduction argument such as given in Section 17.3.2, that the problem of determining whether an arbitrary program computes a specified function is unsolvable. 17.3.2 The Halting Problem
Consider a program named COMP that takes two strings as input. It returns TRUE if the strings are the same. It returns FALSE if the strings are different. Why doesn't the argument that we used to
Implement VERTEX COVER; that is, given graph \(\mathbf{G}\) and integer \(k\), answer the question of whether or not there is a vertex cover of size \(k\) or less. Begin by using a brute-force
Implement KNAPSACK (see Section 16.2). Measure its running time on a number of inputs. What is the largest practical input size for this problem?
Implement an approximation of TRAVELING SALESMAN; that is, given a graph \(\mathbf{G}\) with costs for all edges, find the cheapest cycle that visits all vertices in G. Try various heuristics to find
Write a program that, given a positive integer \(n\) as input, prints out the Collatz sequence for that number. What can you say about the types of integers that have long Collatz sequences? What can
Use the technique of guessing a polynomial and deriving the coefficients to solve the summation i=1 -2
Use the technique of guessing a polynomial and deriving the coefficients to solve the summation n i=1 ;3
Find, and prove correct, a closed-form solution for b i= -2
Use the shifting method to solve the summation n i=1
Use the shifting method to solve the summation m 2. i=1
Use the shifting method to solve the summation n i=1 i2n-i
Provide a summation for the value of sum in the following code fragment.Find and prove correct a closed form solution to the summation. sum = 0; inc = 0; for (i=1;i
A chocolate company decides to promote its chocolate bars by including a coupon with each bar. A bar costs a dollar, and with c coupons you get a free bar. So depending on the value of c, you get
Write and solve a recurrence relation to compute the number of times Fibr is called in the Fibr function of Exercise 2.11.Data From in Exercise 2.11. 2.11 Here is a simple recursive function to
Give and prove the closed-form solution for the recurrence relation T(n) =T(n - 1) + 1, T(1) = 1.
Give and prove the closed-form solution for the recurrence relation T(n) =T(n - 1) + c, T(1) = c.
Prove by induction that the closed-form solution for the recurrence relationis in Ω(n log n). T(n) = 2T (n/2) +n; T(2) = 1
Find the solution (in asymptotic terms, not precise constants) for the recurrence relationYou may assume that n is a power of 2. T(n) = T(n/2) + n; T(1) = 1.
Using the technique of expanding the recurrence, find the exact closed-form solution for the recurrence relationYou may assume that n is a power of 2. T(n) = 2T(n/2) +n; T(2) = 2.
For the following recurrence, give a closed-form solution. You should not give an exact solution, but only an asymptotic solution (i.e., using Θ notation).You may assume that n is a power of 2.
Section 5.5 provides an asymptotic analysis for the worst-case cost of function buildHeap. Give an exact worst-case analysis for buildHeap. 5.5 Heaps and Priority Queues There are many situations,
For each of the following recurrences, find and then prove (using induction) an exact closed-form solution. When convenient, you may assume that n is a power of 2. (a) T(n) = T(n-1) + n/2 for n > 1;
Use Theorem 14.1 to prove that binary search requires Θ(log n) time. Theorem 14.1 (The Master Theorem) For any recurrance relation of the form T(n) = aT(n/b) + cnk, T(1) = c, the following
Recall that when a hash table gets to be more than about one half full, its performance quickly degrades. One solution to this problem is to reinsert all elements of the hash table into a new hash
Given a 2-3 tree with N nodes, prove that inserting M additional nodes requires O(M + N) node splits.
One approach to implementing an array-based list where the list size is unknown is to let the array grow and shrink. This is known as a dynamic array.When necessary, we can grow or shrink the array
Recall that two vertices in an undirected graph are in the same connected component if there is a path connecting them. A good algorithm to find the connected components of an undirected graph begins
Give a proof similar to that used for Theorem 14.2 to show that the total number of comparisons required by any series of n or more searches S on a self-organizing list of length n using the count
Use mathematical induction to prove that n i=1 Fib(i) = Fib(n 2) - 1, for n 1. -
Use mathematical induction to prove that Fib(i) is even if and only if n is divisible by 3.
Use mathematical induction to prove that for n> 6, fib(n) > (3/2)n-1.
Find closed forms for each of the following recurrences. (a) F(n) = F(n-1) +3; F(1) = 2. (b) F(n) = 2F (n - 1); F(0) = 1. (c) F(n) = 2F (n-1)+1; F(1) = 1. (d) F(n) = 2nF(n-1); F(0) = 1. (e) F(n) = 2F
Find Θ for each of the following recurrence relations. (a) T(n) = 2T (n/2) + n. (b) T(n) = 2T (n/2) + 5. (c) T(n) = 4T (n/2) + n. (d) T(n) = 2T (n/2) + n. (e) T(n) = 4T (n/2) + n. (f) T(n) = 4T
Implement the UNION/FIND algorithm of Section 6.2 using both path compressionand the weighted union rule. Count the total number of node accessesrequired for various series of equivalences to
Create a graph showing expected cost versus the probability of an unsuccessful search when performing sequential search (see Section 9.1). What can you say qualitatively about the rate of increase in
Modify the binary search routine of Section 3.5 to implement interpolation search. Assume that keys are in the range 1 to 10,000, and that all key values within the range are equally likely to occur.
Write an algorithm to find the Kth smallest value in an unsorted array of n numbers (K
Example 9.9.3 discusses a distribution where the relative frequencies of the records match the harmonic series. That is, for every occurance of the first record, the second record will appear half as
Graph the equations T(n)= log2 n and T(n) = n/loge n. Which gives the better performance, binary search on a sorted list, or sequential search on a list ordered by frequency where the frequence
Assume that the values A through H are stored in a self-organizing list, initially in ascending order. Consider the three self-organizing list heuristics: count, move-to-front, and transpose. For
For each of the three self-organizing list heuristics (count, move-to-front, and transpose), describe a series of record accesses for which it would require the greatest number of comparisons of the
Write an algorithm to implement the frequency count self-organizing list heuristic, assuming that the list is implemented using an array. In particular, write a function FreqCount that takes as input
Write an algorithm to implement the move-to-front self-organizing list heuristic, assuming that the list is implemented using an array. In particular, write a function MoveToFront that takes as input
Write an algorithm to implement the transpose self-organizing list heuristic, assuming that the list is implemented using an array. In particular, write a function transpose that takes as input a
Write functions for computing union, intersection, and set difference on arbitrarily long bit vectors used to represent set membership as described in Section 9.3. Assume that for each operation both
Compute the probabilities for the following situations. These probabilities can be computed analytically, or you may write a computer program to generate the probabilities by simulation.(a) Out of a
Assume that you are hashing key K to a hash table of n slots (indexed from 0 to n - 1). For each of the following functions h(K), is the function acceptable as a hash function (i.e., would the hash
Assume that you have a ten-slot closed hash table (the slots are numbered 0 through 9). Show the final hash table that would result if you used the hash function h(k) = k mod 10 and quadratic probing
Assume that you have a ten-slot closed hash table (the slots are numbered 0 through 9). Show the final hash table that would result if you used the hash function h(k) = k mod 10 and quadratic probing
Assume that you have a ten-slot closed hash table (the slots are numbered 0 through 9). Show the final hash table that would result if you used the hash function h(k) = k mod 10 and pseudo-random

Showing 1 - 100 of 447