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

Describe how to implement the TaskSchedule method to run in O(n log n) time.
Consider again the modification of the deterministic version of the quick-sort algorithm so that, instead of selecting the last element in an n-element sequence as the pivot, we choose the element at index [n/2]. Describe the kind of sequence that would cause this version of quick-sort to run in
In image-processing applications, such as for optical character recognition, it is often useful to group together contiguous sets of similarly colored pixels in an image. (See Figure 7.11.) For instance, in a black-and-white image, we might say that a black pixel, p, is adjacent with another black
Show that n3 log n is Ω(n3).
Show that n2 is ω(n).
Provide an example instance of the fractional knapsack problem where a greedy strategy based on repeatedly choosing as much of the highest-benefit item as possible results in a suboptimal solution.
Let S = {a, b, c, d, e, f, g} be a collection of objects with benefit-weight values, a: (12, 4), b : (10, 6), c : (8, 5), d: (11, 7), e: (14, 3), f : (7, 1), g : (9, 6). What is an optimal solution to the fractional knapsack problem for S assuming we have a sack that can hold objects with total
Suppose instead of choosing a single pivot in the quick-select algorithm, we chose log n pivots. Show that the probability that at least one of them is good is at least 1 − 1/n.
Given an array, A, of n numbers in the range from 1 to n, describe an O(n)-time method for finding the mode, that is, the number that occurs most frequently in A.
Suppose you are given two sorted lists, A and B, of n elements each, all of which are distinct. Describe a method that runs in O(log n) time for finding the median in the set defined by the union of A and B.
Show how a deterministic O(n)-time selection algorithm can be used to design a quick-sort-like sorting algorithm that runs in O(n log n) worst-case time on an n-element sequence.
What does the weighted median algorithm return if the weights of all the elements are equal?
Given an unordered sequence S of n comparable elements, describe a lineartime method for finding the [√n ] items whose rank in an ordered version of S is closest to that of the median.
Explain where the induction proof for showing that deterministic selection runs in O(n) time would fail if we formed groups of size 3 instead of groups of size 5.
Show that the worst-case running time of quick-select on an n-element sequence is Ω(n2).
Suppose we are given a sequence, S, of n integers in the range from 1 to n3. Give an O(n)-time method for determining whether there are two equal numbers in S.
Give a pseudocode description of an in-place quick-select algorithm.
Suppose we are given a sequence S of n elements, each of which is an integer in the range [0, n2 − 1]. Describe a simple method for sorting S in O(n) time.
Suppose we are given two sequences A and B of n integers, possibly containing duplicates, in the range from 1 to 2n. Describe a linear-time algorithm for determining if A and B contain the same set of elements (possibly in different orders).
Show that any comparison-based sorting algorithm can be made to be stable, without affecting the asymptotic running time of this algorithm.
Which, if any, of the algorithms bubble-sort, heap-sort, merge-sort, and quicksort are stable?
Suppose you would like to sort n music files, but you only have an old, unreliable computer, which you have nicknamed “Rustbucket.” Every time Rustbucket compares two music files, x and y, there is an independent 50-50 chance that it has an internal disk fault and returns the value 0, instead
Given a sequence of numbers, (x1, x2,...,xn), the mode is the value that appears the most number of times in this sequence. Give an efficient algorithm to compute the mode for a sequence of n numbers. What is the running time of your method?
Let S be an array of n elements on which a total order relation is defined. An inversion in S is a pair of indices i and j such that i S[j]. Describe an algorithm running in O(n log n) time for determining the number of inversions in S (which can be as large as O(n2)).
Many states require that candidate names appear on a ballot in random order, so as to minimize biases that can arise from the order in which candidate names appear on a ballot for a given election. For instance, in the 2012 general election, the Secretary of State of California performed a random
Suppose we are given a sequence S of n elements, on which a total order relation is defined. Describe an efficient method for determining whether there are two equal elements in S. What is the running time of your method?
In computer games and also in simulations of card-playing scenarios, we sometimes need to use a computer to simulate the way that person would shuffle a deck of cards. Given two decks of n cards each, the riffle shuffle algorithm involves repeatedly choosing one of the two decks at random and then
As mentioned above, for each word, w, in a collection of documents, an inverted file stores a list of documents that contain the word, w. In addition, search engines typically order the list for each word by a ranking score. Modern search engines must be able to answer more than just single-word
how that the running time of the merge-sort algorithm on an n-element sequence is O(n log n), even when n is not a power of 2.
Let A be a collection of objects. Describe an efficient method for converting A into a set. That is, remove all duplicates from A. What is the running time of this method?
Give a pseudocode description of the merge-sort algorithm assuming the input is given as a linked list.
Suppose you are given a new hardware device that can merge k > 2 different sorted lists of total size n into a single sorted list in O(n) time, independent of the value of k. Such a device could, for example, be based on a hardware streaming system or could be based on a network protocol. Show
Describe a variation of the merge-sort algorithm that is given a single array, S, as input, and uses only an additional array, T, as a workspace. No other memory should be used other than a constant number of variables.
Suppose we implement the tree-based union-find data structure, but we don’t use the union-by-size heuristic nor the path-compression heuristic. Show that the total running time for performing a sequence of n union and find operations, starting with n singleton sets, is Θ(n2) in this case. That
Answer the previous exercise assuming that we implement both the union-bysize and path compression heuristics.
Suppose we implement the tree-based union-find data structure using the unionby-size heuristic and path-compression heuristics. Show that the total running time for performing a sequence of m union and find operations, starting with n singleton sets, is O(m), if m ≥ n log n.
Suppose we have 20 singleton sets, numbered 0 through 19, and we call the operation union(find(i),find(i + 5)), for i = 0, 1, 2,..., 14. Draw a picture of a tree-based representation of the sets that result, assuming we don’t implement the union-by-size and path compression heuristics.
Suppose we implement the tree-based union-find data structure using the unionby-size and path-compression heuristics. Show that the total running time for performing a sequence of m union and find operations, starting with n singleton sets, is O(n + m) if all the unions come before all the finds.
Suppose we have 20 singleton sets, numbered 0 through 19, and we call the operation union(find(i),find(i + 5)), for i = 0, 1, 2,..., 14. Draw a picture of a list-based representation of the sets that result.
Consider the game of Hex, as in the previous exercise, but now with a twist. Suppose some number, k, of the cells in the game board are colored gold and if the set of stones that connect the two sides of a winning player’s board are also connected to k ≤ k of the gold cells, then that player
Suppose we implement the tree-based union-find data structure using the unionby-size heuristic and a partial path-compression heuristic. The partial path compression in this case means that, after performing a sequence of pointer hops for a find operation, we update the parent pointer for each node
One additional feature of the list-based implementation of a union-find structure is that it allows for the contents of any set in a partition to be listed in time proportional to the size of the set. Describe how this can be done.
The game of Hex is said to have, as one of its inventors, the mathematician John Nash, who is the subject of the book and movie A Beautiful Mind. In this game, two players, one playing black and the other playing white, take turns placing stones of their respective colors on an n × n hexagonal
Let A be a collection of objects. Describe an efficient method for converting A into a set. That is, remove all duplicates from A. What is the running time of this method?
For the sake of analysis, if we have a sequence of union, find, and makeSet operations, why can we can assume without loss of generality that all the makeSet operations come first?
Suppose that we implement a union-find structure by representing each set using a balanced search tree. Describe and analyze algorithms for each of the methods for a union-find structure so that every operation runs in at most O(log n) time in the worst case.
How many walls were erased to construct the maze in Figure 7.3, not counting the start and finish walls? Figure 7.3
One of the tasks for an operating system is the job of scheduling computations to be performed by the processor(s) that are part of that system. A subtask that comes up in some processor scheduling problems is to solve a sequence σ of O(n) priority queue operations, where each operation in σ is
Consider a method, remove(e), which removes e from whichever list it belongs to, in a list-based implementation of a union-find structure. Describe how to modify the list-based implementation so that this method runs in time O(1).
Another problem of interest in percolation theory is to determine the threshold probability where a liquid will permeate a porous material. One way to model this is to consider the barriers between pairs of adjacent cells in some random order and remove them in this order. At the point when the top
Describe how to implement a union-find structure using extendable arrays, which each contains the elements in a single set, instead of linked lists. Show how this solution can be used to process a sequence of m union-find operations on an initial collection of n singleton sets in O(n log n + m)
Suppose we have a social network with members A, B, C, D, E, F, and G, and the set of friendship ties, {(A, B),(B,C),(C, A),(D, E),(F, G)}. What are the connected components?
Most modern text processing systems have a built-in spelling checker, which checks to make sure words are spelled correctly and offers suggested corrections when words are misspelled. Suppose you have a dictionary, D, of n English words and would like to build such a spelling checker for two common
A popular tool for visualizing the themes in a speech is to draw a word cluster diagram, where the unique words from the speech are drawn in a group, with each word’s size being in proportion to the number of times it is used in the speech. Given a speech containing n total words, describe an
Imagine that you work for an insurance company that is insuring people against identity theft. You have just learned about a major security breach at a prominent bank used by many of your customers. Through back channels, you have obtained the list of Social Security numbers of the bank customers
One way to measure the reading difficulty of a book is to count the number of unique words it contains. For example, Green Eggs and Ham, by Dr. Seuss, contains 50 unique words, whereas the book of Isaiah, from the Bible, contains almost 2,000 unique (Hebrew) words. Suppose you have a book, B,
Suppose you would like to build a hash table for images, where the key for each image is a “thumbnail” image of 75×75 pixels, with each pixel being one of 256 possible colors. Describe a hash function for a set of such images. Your hash function should be fast to compute and it should strive
It is well known that in a room of n people, the probability that at least two of them have the same birthday is over 1/2 if n > 23, which is a phenomenon known as the birthday paradox. Suppose, then, that you have a list of n people and their birthdays. Describe a way, in O(n) expected time, to
A multimap is data structure that allows for multiple values to be associated with the same key. It has a put(k, v) method, which inserts an item with key k and value v even if there is already an item with key k (but not the same key-value pair), and a FindAll(k) method, which returns all the
Imagine that you are building an online plagiarism checker, which allows teachers in the land of Edutopia to submit papers written by their students and check if any of those students have copied whole sections from a set, D, of documents written in the Edutopian language that you have collected
Describe a different way of detecting an eviction cycle in the cuckoo hashing scheme than in counting iterations. You are allowed to use additional memory or to mark the cells of the two tables.
Sports announcers are expected to keep talking during a broadcast of a sporting event even when there is nothing actually happening, such as during half-time. One common way to fill empty time is with sports trivia. Suppose, then, that you are going to be a sports announcer for the big game between
Dr. Wayne has a new way to do open addressing, where, for a key k, if the cell h(k) is occupied, then he suggests trying (h(k) + i · f(k)) mod N, for i = 1, 2, 3,..., until finding an empty cell, where f(k) is a random hash function returning values from 1 to N − 1. Explain what can go wrong
In a double-entry accounting system, every business transaction has to be entered as two separate transactions, in different two accounts, once as a debit and once as a credit. For example, if a business borrows $10,000 from a bank, the business should enter a debit of $10,000 to its Cash account a
Suppose that both the hash function, h, and the hash function, f, used in the double hashing open addressing scheme are random functions. Show that the expected time to perform the get(k) operation is O(1).
Describe the limitations of using a linked list to store a collection of key-value pairs subject to put(k, v) and get(k).
In our description of hashing with the separate chaining rule, we assumed each cell in the array, A, was a pointer to a linked list, which wastes space in the case where the list holds only one item. Show how to modify our implementation so that we don’t waste space on additional pointers to
Bob says that a hash table with collisions handled using open addressing can have a load factor greater than 1. Alice says that this is impossible. Who is right, and why?
Suppose you are working in the information technology department for a large hospital. The people working at the front office are complaining that the software to discharge patients is taking too long to run. Indeed, on most days around noon there are long lines of people waiting to leave the
Give the pseudocode description for performing insertion, searching, and removal from a hash table that uses linear probing to resolve collisions where we use a special marker to represent deleted elements.
Alice says that a hash table with collisions handled using separate chaining can have a load factor greater than 1. Bob says that this is impossible. Who is right, and why?
Show the steps for replacing 5 with 18 in the heap of Figure 5.6. Figure 5.6 5 15 20 (16 (25 (14 (12 (11 8
Show the steps for removing key 16 from the heap of Figure 5.6. Figure 5.6. 5 15 20 (16 (25 (14 (12 (11 8
Define a min-max queue to be a data structure that supports the queue operations of enqueue() and dequeue() for objects that come from a total order, as well as operations min() and max(), which return, but do not delete the minimum or maximum element in the min-max queue, respectively. Describe an
Is there a heap T storing seven distinct elements such that a preorder traversal of T yields the elements of T in sorted order? How about an inorder traversal? How about a postorder traversal?
Define a min-max stack to be a data structure that supports the stack operations of push() and pop() for objects that come from a total order, as well as operations min() and max(), which return, but do not delete the minimum or maximum element in the min-max stack, respectively. Describe an
Let T be a heap storing n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T). For example, given the heap of Figure 5.6 and query key x = 7, the algorithm should report 4, 5, 6, 7. Note that the
Illustrate the performance of the heap-sort algorithm on the following input list: (2, 5, 16, 4, 10, 23, 39, 18, 26, 15).
Develop an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time.
Where may an item with largest key be stored in a heap?
Show that the problem of finding the kth smallest element in a heap takes at least Ω(k) time in the worst case.
One of the oldest applications used on the Internet is FTP, the file transfer protocol. The definition for this protocol traces its roots back to 1971, before the Internet even existed, and its formulation for the Internet was given in 1980. Its primary purpose is for transferring files from one
We can represent a path from the root to a node of a binary tree by means of a binary string, where 0 means “go to the left child” and 1 means “go to the right child.” Design a logarithmic-time algorithm for finding the last node of a heap holding n elements based on the this representation.
Give an example of a worst-case list with n elements for insertion-sort, and show that insertion-sort runs in Ω(n2) time on such a list.
The problem of accurately summing a set S of n floating-point numbers, S = {x1, x2,...,xn}, on a real-world computer is more challenging than might first appear. For example, using the standard accumulating-sum algorithm to compute the harmonic numbers, in floating-point produces a sequence
Show that, for any n, there is a sequence of insertions in a heap that requires Ω(n log n) time to process.
Suppose you are designing a system for buying and selling stocks using a continuous limit order book strategy, as described in the beginning of this chapter. Describe how to use priority queues to process such buy and sell orders, including those that can be processed immediately and those that
Suppose the binary tree T used to implement a heap can be accessed using only the methods of a binary tree. That is, we cannot assume T is implemented as an array. Given a reference to the current last node, v, describe an efficient algorithm for finding the insertion point (that is, the new last
Suppose you work for a major airline and are given the job of writing the algorithm for processing upgrades into first class on various flights. Any frequent flyer can request an upgrade for his or her up-coming flight using this online system. Frequent flyers have different priorities, which are
In a discrete event simulation, a physical system, such as a galaxy or solar system, is modeled as it changes over time based on simulated forces. The objects being modeled define events that are scheduled to occur in the future. Each event, e, is associated with a time, te, in the future. To move
In data smoothing applications, such as in visualizing trends in stock averages over time, it is useful to keep track of the median of a set, S, of numbers as values are inserted or removed from S. Describe a method for maintaining the median of an initially empty set, S, subject to an operation,
Design a linear-time algorithm for the previous problem. Data From Previous ProblemSuppose we are given a sorted sequence S of items (x0, x1,...,xn−1) such that each item xi in S is given a positive integer weight ai. Let A denote the total weight of all elements in S. Construct an O(n log
Suppose we are given a sorted sequence S of items (x0, x1,...,xn−1) such that each item xi in S is given a positive integer weight ai. Let A denote the total weight of all elements in S. Construct an O(n log n)-time algorithm that builds a search tree T for S such that the depth of each item ai
Describe how to implement the methods, insert(k, v) and remove(k), as well methods, and min() and max(), which return the key-value pair with smallest and largest key, respectively, in O(log n) time each using a balanced binary search tree.
How many trinode restructuring operations are needed to perform the zig-zig, zig-zag, and zig updates in splay trees? Use figures to explain your counting.
Show that at most one node in an AVL tree becomes unbalanced after operation removeAboveExternal is performed within the execution of a remove operation.
Give a pseudocode description of an algorithm to find the element with smallest key in a binary search tree. What is the running time of your method?
Show that 2n+1 is O(2n).
Perform a similar analysis for method Loop3 shown in Algorithm 1.21. Algorithm Loop1(n): s-0 for i + 1 to n do s-s+i Algorithm Loop2(n): p-1 for i - 1 to 2n do p-p.i Algorithm Loop3(n): p-1 for i +1 to n? do p- p.i Algorithm Loop4(n): for i - 1 to 2n do for j +1 to i do S-s+i Algorithm
What does a splay tree look like if its items are accessed in increasing order by their keys?

Showing 500 - 600 of 819

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

Step by Step Answers