Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

Suppose you have a software method, Conv, that can perform the convolution of two length-n integer vectors, A and B, using the FFT algorithm described in this chapter. Suppose further that you have been asked to build a system that can take an n-bit binary “text” string, T, and an m-bit binary
Describe a version of the FFT that works when n is a power of 3 by dividing the input vector into three subvectors, recursing on each one, and then merging the subproblem solutions. Derive a recurrence equation for the running time of this algorithm and solve this recurrence using the Master
In some numerical computing applications, a desired computation is to find a polynomial that goes through a given set of points on a line, which, without loss of generality, we can assume is the x-axis. So suppose you are given a set of real numbers X = {x0, x1,...,xn−1}. Note that, by
Given degree-n polynomials p(x) and q(x), describe a method for multiplying the derivatives of p(x) and q(x), that is, p'(x)·q'(x), using O(n log n) arithmetic operations.
What is the bit-reversal permutation, reverse, for n = 16?
Prove that ω = 24b/m is a primitive mth root of unity when multiplication is taken modulo (22b + 1), for any integer b > 0 that is a multiple of m.
Write the complex nth roots of unity for n = 4 and n = 8 in the form a + bi.
Prove the following more general form of the reduction property of primitive roots of unity: For any integer c > 0, if ω is a primitive (cn)th root of unity, then ωc is a primitive nth root of unity.
Describe the inverse FFT algorithm, which computes the inverse DFT in O(n log n) time. That is, show how to reverse the roles of a and y and change the assignments so that, for each output index, we have n-1 2jw-り j=1
Construct a table showing an example of the RSA cryptosystem with parameters p = 17, q = 19, and e = 5. The table should have two rows, one for the plaintext M and the other for the ciphertext C. The columns should correspond to integer values in the range [10, 20] for M.
Why can’t you use the pair (1, n) as an RSA public key, even if n = pq, for two large primes, p and q?
Suppose the primes p and q used in the RSA cryptosystem, to define n = pq, are in the range [√n − log n, √n + log n]. Explain how you can efficiently factor n using this information.
Solve the previous exercise, but use the El Gamal cryptosystem instead of RSA.Data From Previous ExerciseSuppose Alice wants to send Bob a message, M, that is the price she is willing to pay for his old bike. Here, M is just an integer in binary. She uses the RSA algorithm to encrypt M, to produce
Suppose Alice wants to send Bob a message, M, that is the price she is willing to pay for his old bike. Here, M is just an integer in binary. She uses the RSA algorithm to encrypt M, to produce the ciphertext, C, using Bob’s public key, and sends it to Bob. Unfortunately, Eve has intercepted C
Write a nonrecursive version of Algorithm ExtendedEuclidGCD.
One of the main uses for public-key cryptography is that it can be used to establish a secret key for a communication session between Alice and Bob even if they have never met to share that secret key in advance. Explain how public key cryptography can be used for this purpose.
Show how to modify Algorithm ExtendedEuclidGCD to compute the multiplicative inverse of an element in Zn using arithmetic operations on operands with at most 2[log2 n] bits.
Show the execution of method FastExponentiation(5, 12, 13) by constructing a table similar to Table 24.6. Table 24.6. 1|0 8 21 12 6 3 1 1 12
Digital certificates are signed documents, where a respected authority verifies the binding between a person’s identity information (like their name, email address, etc.) and their public key. But if that person loses the private key that goes with his or her public key, then this certification
Construct the multiplication table of the elements of Z11, where the element in row i and column j (0 ≤ i, j ≤ 10) is given by i · j mod 11.
Suppose Alice is a U.S. spy on a 7-day trip to a faraway land and wants to prove for each day she is gone that she not been captured. She has chosen a secret random number, x, which she is keeping secret. But she did tell her CIA handler the value y = H(H(H(H(H(H(H(x))))))), where H is a one-way
Let p be a prime. Give an efficient alternative algorithm for computing the multiplicative inverse of an element of Zp that is not based on the extended Euclid’s algorithm. What is the running time of your algorithm?
Consider the time stamping problem from the previous exercise, but now suppose that each day that there is one document added to the set, and one document that is removed from the set, but all of the remaining documents still need to be proven to exist as a part of the set on that day. Explain how
Write a nonrecursive version of Algorithm EuclidGCD.
There are instances when it is useful to prove that a document, D, exists on a certain date. In order to facilitate such proofs, Bob collects a group of documents, D1, D2,...,Dn, every day from people wanting time stamps for their documents on that day. Bob constructs a complete binary tree, T,
There is a perfectly secure cipher, known as the one-time pad, which is said to have been used for encrypting messages on the “hot line” between Moscow and Washington, DC, during the Cold War. In this cryptosystem, Alice and Bob each share a random bit string, K, as large as any message they
Describe a generalized version of the Karp-Rabin lexicon matching algorithm for the case when their are k different possible pattern sizes. Characterize the running time of this algorithm in terms of n, k, and the total size, N, of all the patterns in the lexicon.
Give an example of an input instance for lexicon matching problem, with just a single pattern in the lexicon, L, that forces the Karp-Rabin algorithm given in Algorithm 23.11 to run in Ω(nm) time.
Show how to perform prefix matching queries using a suffix trie.
Suppose the trustee for the estate of famous photographer, Ansel Adams, was interested in finding examples of people posting Ansel Adams photographs on their personal websites without including attributions to him. Suppose further that some of these people have tried to conceal their possible
Suppose Bill is graduate of Slacker University, and he took a little “shortcut” when he was asked to build a software system that could take a pattern, P, of length, m, and text, T, of length, n, with both defined over the same alphabet of size d for some constant d > 1, and determine
Assuming that the characters in alphabet Σ can be enumerated and can index arrays, give an O(m + |Σ|) time method for constructing the last function from an m-length pattern string P.
Linguists are interested in studying the way in which words are constructed, with common prefixes and suffixes giving important clues to the meanings of words they are contained in. Thus, a useful tool for a linguist would be to be able to identify all the words in a given collection, W, of words,
DNA strings are sometimes spliced into other DNA strings as a product of recombinant DNA processes. But DNA strings can be read in what would be either the forward or backward direction for a standard character string. Thus, it is useful to be able to identify prefixes and their reversals. Let T be
Show how to modify the KMP string pattern matching algorithm so as to find every occurrence of a pattern string P that appears as a substring in T, while still running in O(n + m) time. (Be sure to catch even those matches that overlap.)
When a web crawler is exploring the Internet looking for content to index for a search engine, the crawler needs some way of detecting when it is visiting a copy of a website it has encountered before. Describe a way for a web crawler to store its web pages efficiently so that it can detect in O(n)
Describe an O(n log n)-time algorithm for finding the second closest pair of points in a set, S, of n points in the plane. That is, you should return the pair, (p, q), in S, such that the only pair of points that could be closer to each other than the distance between p and q is the closest pair of
Suppose we are given an array, A, of n nonintersecting segments, s1, s2,...,sn, with endpoints on the lines y = 0 and y = 1, and ordered from left to right. Given a point q with 0 < y(q) < 1, design an algorithm that in O(log n) time computes the segment si of A immediately to right of q, or
Suppose you are given a set S of n line segments in the plane, such that each makes a positive angle with the x-axis of either 30◦ or 60◦ (so there are only two possible slopes for the lines in S). Describe an efficient algorithm for finding all the pairs of intersecting segments in S. What is
Let P be a set of n points in the plane. Modify the Graham scan algorithm to compute, for every point p of P that is not a vertex of the convex hull, either a triangle with vertices in P, or a segment with endpoints in P that contains p.
Given a set S of points in the plane, define the Delaunay triangulation of S to be the set of all triangles (p, q, r) such that p, q, and r are in S and the circle defined to have these points on its boundary is empty—it contains no points of S in its interior. Such triangulations have many
Design an O(n2)-time algorithm for testing whether a polygon with n vertices is simple. Assume that the polygon is given by the list of its vertices.
Given a set P of n points, design an efficient algorithm for constructing a simple polygon whose vertices are the points of P.
Imagine a game, Battlestrip, which involves one player laying down a set of horizontal line segments on his computer screen, and another player laying down a set of vertical segments on hers. Then the two computer screens are virtually overlaid on top of one another and the winner is the player
Let C be a collection of n horizontal and vertical line segments. Describe an O(n log n)-time algorithm for determining whether the segments in C form a simple polygon.
In machine learning applications, we often have some kind of condition defined over a set, S, of n points, which we would like to characterize—that is, “learn”— using some simple rule. For instance, these points could correspond to biological attributes of n medical patients and the
Say that a polygon, P, is monotone if any vertical line intersects the boundary of P in at most two points. Given a simple monotone polygon, P, with n vertices, show that you can find the convex hull of P in O(n) time.
Suppose you are given an n-vertex convex polygon, P. Describe an O(n)-time method for computing the area of P.
Suppose you are hiking in the wild country of some exotic part of the world. Naturally, an important part of your survival gear is a GPS tracking device and a digital map of the region you are hiking in, which includes the pathways of trails, rivers, and creeks, as well as obstacles like cliffs and
Computational metrology deals with algorithms for measuring things, such as manufactured parts, and one of the standard algorithms is to determine the flatness of an edge of a manufactured part based on a set of points that are sampled along that edge (say, by a laser range-finder or a scanning
Design an O(n)-time algorithm to test whether a given n-vertex polygon is convex. You should not assume that P is simple.
In the hidden-line elimination problem, we would like to visualize a threedimensional scene, described by a collection of polygons, from a particular viewing point, p, and in a particular direction. This problem is often solved by projecting the edges of the polygons in the scene onto a view plane
Show that the expected number of points on the convex hull of a set of n points chosen uniformly and independently at random in the interior of a rectangle, R, is O(log n).
Line segments and polygons are used to model geometric objects in computer graphics, video games, and computer-aided design, often in data pipelines that use the output of one program as the input to another. One complication that can arise in such scenarios is that a data format needed for the
Gerrymandering is a process where voting districts are drawn to achieve various political goals, such as maximizing the number of voters from a certain party, rather than to achieve geometric goals, such as having districts drawn to have generally round or square shapes. This process often gives
In several computational geometry problems involving distances defined by a set, S, of n points in the plane, it is often useful to first know what is the largest distance between a pair of points in S, which is known as the diameter of S. Another way to define the diameter of such a set, S, is as
Using the orientation test, give a pseudocode description of a method, inTriangle(p, q, r, s), which tests whether a point, p, is inside the interior of a triangle (q, r, s), assuming q, r, and s are listed in counterclockwise order.
Describe an efficient method for inserting an object into a (balanced) priority search tree. What is the running time of this method?
Construct a priority search tree for the point set of Exercise R-21.7. Set of Exercise R-21.7{(1, 2),(4, 10),(14, 3),(6, 6),(3, 15),(2, 2),(3, 12),(9, 4),(12, 14)}.
Suppose we are given a range-searching data structure D that can answer rangesearching queries for a set of n points in d-dimensional space for any fixed dimension d (like 8, 10, or 20) in time that is O(logd n+k), where k is the number of answers. Show how to use D to answer the following queries
Construct a k-d tree for the point set of Exercise R-21.7. Set of Exercise R-21.7{(1, 2),(4, 10),(14, 3),(6, 6),(3, 15),(2, 2),(3, 12),(9, 4),(12, 14)}.
Show how to extend the two-dimensional range tree so as to answer d-dimensional range-searching queries in O(logd n) time for a set of d-dimensional points, where d ≥ 2 is a constant.
Draw a quad-tree for the following set of points, assuming a 16 × 16 bounding box: {(1, 2),(4, 10),(14, 3),(6, 6),(3, 15),(2, 2),(3, 12),(9, 4),(12, 14)}.
When the Sload Digital Sky Survey decided to create a data structure for storing the objects identified by their projects, they needed a method for searching for two-dimensional points that are on a sphere rather than being in a rectangle. So they started with a sphere, cut it into quarters by two
Suppose a set S contains n two-dimensional points whose coordinates are all integers in the range [0, N]. What is the worst-case depth of a quadtree defined on S?
A higher-dimensional version of a quadtree is known as an octree, since, in three dimensions it divides each cube into 8 subcubes and recursively constructs an octree for each nonempty subcube as a child. Suppose we are given such a threedimensional structure, but we are only interested in two of
Design a static data structure (which does not support insertions and deletions) that stores a two-dimensional set S of n points and can answer, in O(log2 n) time, queries of the form countAllInRange(a, b, c, d), which return the number of points in S with x-coordinates in the range [a, b] and
What is the worst-case depth of a k-d tree defined on n points in the plane? What about in higher dimensions?
In applications involving the use of quadtrees in memory-constrained devices, such as smartphones, we often want to optimize the data structure to make it more space efficient. One obvious improvement is to take a standard quadtree, T, and replace each chain of nodes having only one child with a
Describe an efficient data structure for storing a set S of n items with ordered keys, so as to support a rankRange(a, b) method, which enumerates all the items with keys whose rank in S is in the range [a, b], where a and b are integers in the interval [0, n − 1]. Describe methods for object
Argue why the algorithm for answering three-sided range-searching queries with a priority search tree is correct.
Give a pseudocode description of an algorithm for constructing a range tree from a set of n points in the plane in O(n log n) time.
Show that the high y values in a priority search tree satisfy the heap-order property.
In some computer graphics and computer gaming applications, in order to save space, we might like to store a set of two-dimensional points in a single data structure that can be used for both nearest-neighbor queries and range searching. We have already discussed above how a k-d tree can be used to
Let D be an ordered dictionary with n items implemented with a balanced search tree. Show how to implement the following method for D in time O(log n): countAllInRange(k1, k2): Compute and return the number of items in D with key k such that k1 ≤ k ≤ k2.
Given a binary search tree, T, built on the x-coordinates of a set of n objects, describe an O(n)-time method for computing minx(v) and maxx(v) for every node, v, in T.
Show that the Marker algorithm is Hm-competitive when the size of the cache is m and there are m + 1 possible pages that can be accessed, where Hm denotes the mth Harmonic number.
The minx(v) and maxx(v) labels used in the two-dimensional range tree are not strictly needed. Describe an algorithm for performing a two-dimensional rangesearching query in a two-dimensional range tree where each internal node of the primary structure only stores a key(v) label (which is the
What is the expected number of block replacements performed by the Random policy on a cache of size m, for an access sequence of length n, that iteratively accesses m + 1 blocks in a cyclic fashion (assuming n is much larger than m)?
What would be the worst-case space usage of a range tree, if the primary structure were not required to have O(log n) height?
Show that FIFO is m-competitive for any sequence of n page requests, where m is the size of the memory cache.
Show that LRU is m-competitive for any sequence of n page requests, where m is the size of the memory cache.
Consider the generalization of the renter’s dilemma where Alice can buy or rent her skis separate from her boots. Say that renting skis costs a dollars, whereas buying skis costs b dollars. Likewise, say that renting boots costs c dollars, whereas buying boots costs b dollars. Describe a
Suppose Alice is faced with the ski rental problem, where buying skis is 20 times more expensive than renting. In this case, however, Alice notices that she has a fair coin in her pocket and is willing to consider a randomized strategy. Show that she can use her coin to come up with a strategy with
In the MapReduce framework, for performing a parallel computation, a crucial step involves an input that consists of a set of n key-value pairs, (k, v), for which we need to collect each subset of key-value pairs that have the same key, k, into a single file. Describe an efficient external-memory
Suppose you are processing an automated course registration program. The data set in this case is a large file of N course numbers, one for each course request made by a student. Show that you can count the number of requests made for each course, using O((N/B) log(N/B)/ log(M/B)) I/Os.
Imagine that you are trying to construct a minimum spanning tree for a large network, such as is defined by a popular social networking website. Based on using Kruskal’s algorithm, the bottleneck is the maintenance of a union-find data structure. Describe how to use a B-tree to implement a
Show how to implement a dictionary in external memory, using an unordered sequence so that insertions require only O(1)transfers and searches require O(n/B) transfers in the worst case, where n is the number of elements and B is the number of list nodes that can fit into a disk block.
Describe, in detail, the insertion and removal algorithms for an (a, b) tree.
Show that the randomized quick-sort algorithm runs in O(n log n) time with high probability.
Give a pseudocode description of the remove dictionary operation, assuming the dictionary is implemented by a skip-list structure.
Suppose we have a Monte Carlo algorithm, A, and a deterministic algorithm, B, for testing if the output of A is correct. How can we use A and B to construct a Las Vegas algorithm? Also, if A succeeds with probability 1/2, and both A and B run in O(n) time, what is the expected running time of the
Draw an example skip list resulting from performing the following sequence of operations on the skip list in Figure 19.18: remove(38), insert(8,x), insert(24,y), remove(55). Assume the coin flips for the first insertion yield two heads followed by tails, and those for the second insertion yield
Show that if the compositeness witness function, witness(x, n), of the RabinMiller algorithm returns true, then the number n is composite.
Suppose we have a six-sided die, which we roll n times, and let X denote the number of times we role a 1. (a) What is E[X]? (b) Show that X < n/3 with high probability.
Give a randomized algorithm that computes all minimum cuts of a graph with high probability.
Given a parameter, k, suppose we wish to find a number, p, that is prime with probability 2−k. What is the asymptotic number of arithmetic operations needed?
Give an algorithm that computes a minimum cut of a graph with n vertices by O(n) applications of a maximum flow algorithm to a flow network derived from G.
Show that if we do all arithmetic modulo a prime number, p, then, for any integer x > 0, {ix mod p: i = 0, 1,...,p − 1} = {i : i = 0, 1,...,p − 1}. Use the fact that if p is prime, then every nonzero integer less than p has a multiplicative inverse when we do arithmetic modulo p.
Suppose that there is a collection of 3n distinct coupons, n of which are colored red and 2n of which are colored blue. Suppose that each time you go to a ticket window to get a coupon, the clerk first randomly decides, with probability 1/2, whether he will give you a red coupon or blue coupon and

Showing 200 - 300 of 819

Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

Step by Step Answers