Description

Chapter: 12 -Problem: 1 >> Suppose that the coins of the fictional country of Combinatoria come in the denominations, d1, d2,...,dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins whose values sum to n. (a) Give an instance of the making-change problem for which it is suboptimal to
Answer Preview: a An instance of the making change problem for which it is suboptimal to use the standard gr…

, Chapter: 5 -Problem: 2 >> 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 the simulation forward, the event, e, that has smallest time, te, in the future needs to be processed
Answer Preview: Given Scenario Here we have a set of events for their future times te In each step we need to extrac…

, Chapter: 11 -Problem: 4 >> Selecting out a maxima set of points from among a set of points in the plane seems is intended to filter away a lot of points from consideration in a multiobjective optimization problem. For example, if we grade hotels by the sizes of their pools and the quality of their restaurants, then we would hope to have a small set of hotels to choose from that are not dominated by any other hotel along the
Answer Preview: Since all the points in the set R have distinct x and y coordinates and the x coordinat…

, Chapter: 4 -Problem: 9 >> Show that at most one trinode restructure operation (which corresponds to one single or double rotation) is needed to restore balance after any insertion in an AVL tree.
Answer Preview: The AVL tree is a selfbalancing Binary Search Tree BST where the diff…

, Chapter: 11 -Problem: 1 >> Consider the recurrence equation,  Transcribed Image Text: T(n) = 2T(n – 1) + 1, for n > 1, where T(n) = 1 forn= 1. Prove that T(n) is O(2").
Answer Preview: Given T n 2T n 1 1 for n 1 T n 1 We will solve this using substitution method T …

, Chapter: 4 -Problem: 7 >> Draw an example of an AVL tree such that a single remove operation could require ?(log n) trinode restructurings (or rotations) from a leaf to the root in order to restore the height-balance property. (Use triangles to represent subtrees that are not affected by this operation.)
Answer Preview: 1Consider an AVL tree with the following nodes and heights 2Suppose we …

, Chapter: 9 -Problem: 12 >> 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.
Answer Preview: Algorithm 1 step 1 Make an array of frequency of size having equal to n bacause as per the question the range of elements in array will be between 1 t…

, Chapter: 6 -Problem: 6 >> 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 test whether two of the people on this list have the same birthday
Answer Preview: The most efficient way to test if two people have the same birthday in an On expected time is to use …

, Chapter: 4 -Problem: 20 >> 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 is O(log A/ai). Find the item xj with largest j such that  Consider putting this item at the root and re
Answer Preview: To build the search tree T we will use the following divide and conquer algorithm Find the item xj w…

, Chapter: 5 -Problem: 6 >> 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.
Answer Preview: The path to the last node …

, Chapter: 8 -Problem: 9 >> 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)).
Answer Preview: Suppose we know the number of inversions in the left half and right half of the array let be inv1 an…

, Chapter: 4 -Problem: 6 >> What is the minimum number of nodes in an AVL tree of height 7?
Answer Preview: Since we know that N01 N1 2 N2 1 N2 1 N2 2 1 2 1 …

, Chapter: 4 -Problem: 13 >> Let T be a wavl tree storing n items, and let k be the key of an item in T. Show how to construct from T, in O(log n) time, two wavl trees T  and T , such that T  contains all the keys of T less than k, and T  contains all the keys of T greater than k. This operation destroys T.
Answer Preview: We can construct T and T from T in Olog n time using …

, Chapter: 8 -Problem: 5 >> 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 queries, however. Describe an efficient method for computing a list of the documents that contain two w
Answer Preview: The algorithm is similar to the merge algorithm for the …

, Chapter: 8 -Problem: 1 >> 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.
Answer Preview: Step 1 If it is only one element in the array S it is already s…

, Chapter: 6 -Problem: 10 >> 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 spelling mistakes: transpositions, where two consecutive letters are swapped, and substitutions, whe
Answer Preview: A scheme to process the dictionary D in expected On time and then process any mletter word w to see …

, Chapter: 7 -Problem: 5 >> 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 gets k' bonus points. Describe an efficient way to detect when a player wins and also, at that same moment,
Answer Preview: To determine if a player has won the game of Hex and to calculate their bonus points we can use a mo…

, Chapter: 5 -Problem: 5 >> 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 that converges to a constant instead of growing to infinity as a function close to ln n. This phenomenon is
Answer Preview: This algorithm can be implemented in O n log n time by using a div…

, Chapter: 5 -Problem: 8 >> Develop an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time.
Answer Preview: Construct a heap wh…

, Chapter: 4 -Problem: 15 >> Draw an example red-black tree that is not an AVL tree. Your tree should have at least 6 nodes, but no more than 16.
Answer Preview: A redblack tree is a tree in which all nodes are one of two colors There are 4 properties 1 All node…

, Chapter: 5 -Problem: 4 >> 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 node) using just the methods of the binary tree interface. Be sure and handle all possible cases. What
Answer Preview: We can use a levelorder traversal to find the insertion point Starting from the curr…

, Chapter: 24 -Problem: 6 >> 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 before it gets to Bob Explain how Eve can use Bob’s public key to alter the ciphertext C to change it int
Answer Preview: Eve can use Bob's public key to calculate the encryption exponent, e, and the R…

, Chapter: 7 -Problem: 1 >> 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) time.
Answer Preview: A modern metric in data centers is the higher a particular …

, Chapter: 6 -Problem: 4 >> 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 the Bears and the Anteaters. To fill the empty time during half-time, you would like to say that thi
Answer Preview: Create a cuckoo hash table T that uses i j pairs as keys and counts c as values where …

, Chapter: 6 -Problem: 2 >> 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?
Answer Preview: When a functions slope is zero at x and the second derivative at x is less than 0 it i…

, Chapter: 6 -Problem: 9 >> 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 efficient method for counting the number of times each word is used in that speech. You may assume that yo
Answer Preview: Running time f fllwing methd n beuse we trversing eh wrd frm seeh n…

, Chapter: 5 -Problem: 8 >> Where may an item with largest key be stored in a heap?
Answer Preview: The largest …

, Chapter: 7 -Problem: 2 >> 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 either an insert(i) or removeMin(), such that i is a distinct integer in the range from 1 to n. This pro
Answer Preview: Impossible to implement in interactive systems where req…

, Chapter: 8 -Problem: 2 >> Give a pseudocode description of the merge-sort algorithm assuming the input is given as a linked list.
Answer Preview: For sorting a linked list merge sort is often preferred Some other algorithms like quickso…

, Chapter: 7 -Problem: 8 >> Answer the previous exercise assuming that we implement both the union-bysize and path compression heuristics.
Answer Preview: Naive implementation of find int findint paren…

, Chapter: 7 -Problem: 6 >> 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.
Answer Preview: The running time for a treebased unionfind data structure using th…

,

, Chapter: 4 -Problem: 17 >> For each of the following statements about wavl trees, determine whether it is true or false. If you think it is true, provide a justification. If you think it is false, give a counterexample. a. A subtree of a wavl tree is itself a wavl tree. b. The sibling of an external node is either external or it has rank 1.
Answer Preview: Firstly wavl trees are the binary search tress which are self balancedThese trees are also referred to as weak AVL treesThese trees are closely relate…

, Chapter: 9 -Problem: 5 >> 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.
Answer Preview: Input m 10 n 4 Output 4 There should be n el…

, Chapter: 1 -Problem: 21 >> Show that 2n+1 is O(2n).
Answer Preview: By the definition of bigOh we need to …

, Chapter: 7 -Problem: 4 >> 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?
Answer Preview: Energy density relates to the amount of energy that can be stored pe…

, Chapter: 7 -Problem: 5 >> 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 u along this path to point to its grandparent. Show that the total running time for performing m uni
Answer Preview: The running time for a unionfind data structure using the unionbysize heuristic and p…

, Chapter: 8 -Problem: 12 >> 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?
Answer Preview: Sort the numbers by nondecreasing values Next we can scan the sequence to keep track for each ru…

, Chapter: 8 -Problem: 13 >> 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 of the correct result, 1, for “true” or ?1, for “false,” to the question, “x ? y?” That is, for each compa
Answer Preview: One possible way to get Rustbucket to sort n elements is to use randomized quicksort but modify the …

, Chapter: 6 -Problem: 3 >> 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 credit of $10,000 to its Notes Payable account. In order to be in balance, every debit in such a sys
Answer Preview: A possible algorithm to test if a doubleentry accounting system is i…

,

, Chapter: 5 -Problem: 7 >> Show that the problem of finding the kth smallest element in a heap takes at least ?(k) time in the worst case.
Answer Preview: Minimum number of nodes in a tree with height h can be …

, Chapter: 6 -Problem: 8 >> 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 whose banking records were stolen, and, of course, you know the Social Security numbers for your own c
Answer Preview: An insurance company working that is insuring people against identity theft It observes that major s…

, Chapter: 5 -Problem: 6 >> 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 computer to another over the Internet. Suppose you are writing an Internet file transfer application, s
Answer Preview: Let us sort the input sequence of packets using insertion…

, Chapter: 9 -Problem: 1 >> Show that any comparison-based sorting algorithm can be made to be stable, without affecting the asymptotic running time of this algorithm.
Answer Preview: Change the way elements are compared with each other b…

, Chapter: 4 -Problem: 21 >> 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 n)-time algorithm that builds a search tree T for S such that the depth of each item ai is O(log A/ai). Find
Answer Preview: ANSWER To design a lineartime algorithm for the given problem …

, Chapter: 4 -Problem: 18 >> What does a splay tree look like if its items are accessed in increasing order by their keys?
Answer Preview: The tree will look like a left skewed binary …

, Chapter: 7 -Problem: 4 >> 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 grid. Once a stone is placed, it cannot be moved. The black player’s goal is to connect the top and botto
Answer Preview: An efficient scheme to determine after each move whether black or white has just won a game of H…

, Chapter: 4 -Problem: 19 >> 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.
Answer Preview: The number of trinode restructuring operations needed to perform the zigzig zigzag and zi…

, Chapter: 6 -Problem: 7 >> 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, containing n total words (including duplicates). Describe an efficient scheme to count the number of uniqu
Answer Preview: An efficient scheme to count the number of unique words in B is to use a Hash Ta…

,

, Chapter: 6 -Problem: 2 >> 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 linked-list nodes for the cells in A that hold only one item.
Answer Preview: We can modify our implementation by having each cell in the array A hold a va…

, Chapter: 5 -Problem: 11 >> 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 implementation for a min-max queue that can perform each of these operations in amortized O(1) time.
Answer Preview: A minmax queue can be implemented using a modified doubly linked list where each node contains an …

, Chapter: 5 -Problem: 10 >> 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 implementation for a min-max stack that can perform each of these operations in O(1) time.
Answer Preview: An implementation for a minmax stack can be done using a doubly linked list and a minmax heap T…

, Chapter: 7 -Problem: 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 and bottom are connected, we would then take the ratio of r/s as an approximation to this threshold
Answer Preview: The algorithm for efficiently computing this threshold value could …

, Chapter: 8 -Problem: 7 >> 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 removing the bottom card from that deck and placing that card on the top of an output deck. This card
Answer Preview: We can prove that every card has an equal probability of being the top car…

, Chapter: 7 -Problem: 2 >> 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).
Answer Preview: Change the representation of …

, Chapter: 7 -Problem: 8 >> 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 is, provide a proof that it is O(n2) and an example that requires ?(n2) time.
Answer Preview: On2 We can prove that the running time for a sequence of n union and find operations …

, Chapter: 5 -Problem: 6 >> 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.
Answer Preview: A worstcase list for insertion sort would be one that is in descending orde…

, Chapter: 8 -Problem: 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?
Answer Preview: First we sort the objects of A Then we can …

, Chapter: 7 -Problem: 3 >> 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.
Answer Preview: We can define power as the rate of doing work it i…

, Chapter: 7 -Problem: 1 >> 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?
Answer Preview: Measured in Wm 2 it describes the amount of power obtained per unit of Earth surface area used …

, Chapter: 4 -Problem: 16 >> Draw an example of a red-black tree that is not structurally equivalent to a wavl tree.
Answer Preview: Sure Heres an example of a redblack tree that is not structurally e…

, Chapter: 7 -Problem: 6 >> 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.
Answer Preview: ANSWER The listbased representation of the sets that result from the operatio…

, Chapter: 8 -Problem: 3 >> 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.
Answer Preview: In divide and conquer approach we divide the problem into sub p…

, Chapter: 6 -Problem: 3 >> Describe the limitations of using a linked list to store a collection of key-value pairs subject to put(k, v) and get(k).
Answer Preview: At zero kelvin minus 273 degrees Celsius the particles …

, Chapter: 8 -Problem: 1 >> 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 that you can use this device to sort n elements in O(n log n / log k) time. That is, if k is ?(?n), then
Answer Preview: Algorithm Input ksorted lists A1 A2 Ak where Ai has size ni Let L be a matrix of size k x m Here Li …

, Chapter: 8 -Problem: 7 >> 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?
Answer Preview: Sort the elements of S which takes On log …

, Chapter: 9 -Problem: 2 >> 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).
Answer Preview: We n use unt rry t hek whether they hve sme set f numbers in li…

, Chapter: 4 -Problem: 6 >> Describe how to perform the operation removeAllElements(k), which removes all elements with keys equal to k, in a balanced search tree T, and show that this method runs in time O(s log n), where n is the number of elements stored in the tree and s is the number of elements with key k.
Answer Preview: The operation removeAllElementsk can be performed in a balanced search tree T in the following steps …

, Chapter: 7 -Problem: 5 >> 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.
Answer Preview: Simply traverse the …

, Chapter: 3 -Problem: 7 >> Let S be an ordered set of n items stored in a binary search tree, T, of height h. Show how to perform the following method for S in O(h) time: countAllInRange(k1, k2): Compute and return the number of items in S with key k such that k1 ? k ? k2.
Answer Preview: For each node of the tree maintain the size of the corresponding subtree defined as the number of in…

, Chapter: 24 -Problem: 2 >> 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, with n leaves, of height [log n], with each leaf, i, associated with a document, Di. He stores at i the
Answer Preview: Bob can give each document owner a set of O log n numbers by providing them with the h…

, Chapter: 1 -Problem: 14 >> Suppose you are given an array, A, of n positive integers. Describe an O(n) algorithm for removing all the even numbers from A. That is, if A has m odd numbers, then, after you are done, these odd numbers should occupy the first m cells of A in the same relative order they were in originally.
Answer Preview: For this problem we are going to use two variables count …

, Chapter: 24 -Problem: 5 >> 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.
Answer Preview: Replace the st…

, Chapter: 2 -Problem: 22 >> Define the internal path length, I(T), of a tree T to be the sum of the depths of all the internal nodes in T. Likewise, define the external path length, E(T), of a tree T to be the sum of the depths of all the external nodes in T. Show that if T is a binary tree with n internal nodes, then E(T) = I(T)+2n.
Answer Preview: Proof by induction on the number of internal nodes n Base ca…

, Chapter: 19 -Problem: 1 >> Suppose that Bob wants a constant-time method for implementing the random(k) method, which returns a random integer in the range [0, k ? 1]. Bob has a source of unbiased bits, so to implement random(k), he samples [log k] of these bits, interprets them as an unsigned integer, K, and returns the value K mod k. Show that Bob’s algorithm does not return every integer in the range [0, k ? 1] with equa
Answer Preview: Suppose we take k 10 Then before he performs his modular reductio…

, Chapter: 2 -Problem: 6 >> Describe a recursive algorithm for enumerating all permutations of the numbers {1, 2,...,n}. What is the running time of your method?
Answer Preview: All right So for part a have funding a beaker insulation for a number of permutations set with N elements Yes This is part A here and so imagine that …

,

, Chapter: 2 -Problem: 3 >> Suppose you work for a company, iPilgrim.com, whose n employees are organized in a tree T, so that each node is associated with an employee and each employee is considered a supervisor for all the employees (including themselves) in his or her subtree in T, as in the previous exercise. Furthermore, suppose that communication in iPilgrim is done the “old fashioned” way, where, for an employee, x, t
Answer Preview: Let duv be the diameter of T First observe that both u and v are tree leaves if not we can find a path of higher length only by considering one of us …

, Chapter: 19 -Problem: 4 >> Consider a modification of the Fisher-Yates random shuffling algorithm where we replace the call to random(k + 1) with random(n), and take the for-loop down to 0, so that the algorithm now swaps each element with another element in the array, with each cell in the array having an equal likelihood of being the swap location. Show that this algorithm does not generate every permutation with equal pr
Answer Preview: Suppose n 3 We start with 123 After 1 step we get 123 1…

, Chapter: 3 -Problem: 12 >> If one has a set, S, of n items, where n is even, then the median item in S is the average of the ith and (i + 1)st smallest elements in S, where i = n/2. Describe an efficient algorithm for computing the median of such a set S that is stored in a binary search tree, T, where each node, v, in T is augmented with a count, nv, which stores the number of items stored in the subtree of T rooted at v.
Answer Preview: Approach 1 Using On extra memory 1 Create an empty arrayvector 2 Do an inorder traversal of the B…

, Chapter: 19 -Problem: 7 >> 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 then he chooses a coupon uniformly at random from among the coupons that are that color. What is the
Answer Preview: If the colored tickets were dispensed from two different windows then y…

, Chapter: 23 -Problem: 13 >> 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.
Answer Preview: RabinKarp algorithm is an algorithm used for searchingma…

, Chapter: 21 -Problem: 10 >> Describe an efficient method for inserting an object into a (balanced) priority search tree. What is the running time of this method?
Answer Preview: In computer science a binary search tree BST also called an ordered or sorted binary t…

, Chapter: 20 -Problem: 2 >> 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 union-find data structure (from Section 7.1) so that union and find operations each use at most O(log n/ log
Answer Preview: A Btree can be used to implement a unionfind data structure in order to reduce the time complexity o…

, Chapter: 22 -Problem: 6 >> 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 mountains. These pathways and obstacles are described on your map by a collection, S, of n twodimens
Answer Preview: One approach to constructing a trapezoidal decomposition of S is to first sort the s…

, Chapter: 21 -Problem: 7 >> 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)}.
Answer Preview: Quadtrees are trees used to efficiently store data of points on a twodimensional space In this tree …

, Chapter: 20 -Problem: 9 >> 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)?
Answer Preview: Its good practice to try to write the parameters a…

, Chapter: 22 -Problem: 7 >> 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.
Answer Preview: Put P0 at first position in output hull 2 Consider the r…

, Chapter: 22 -Problem: 2 >> 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 rise to very complicated shapes for voting districts, and it can sometimes be challenging to determine
Answer Preview: Let r be a ray emanating vertically up …

, Chapter: 21 -Problem: 6 >> 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 perpendicular great circles going through the poles and then into eight pieces by one more cut using
Answer Preview: The Sload Digital Sky Survey could use a recursive quadtree structure to store the twodimensional po…

, Chapter: 17 -Problem: 5 >> Suppose you are computer security expert working for a major company, CableClock, any you have just discovered that many of the computers at CableClock are infected with malware that must have come from users visiting unsafe websites. For each infected computer, you are given a log file that lists all websites it has visited since the last time it was scanned for malware. Unfortunately, as you loo
Answer Preview: This is an instance of the SET COVER problem In this case the universe of objects is the …

, Chapter: 20 -Problem: 3 >> 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.
Answer Preview: First sort the course num…

, Chapter: 18 -Problem: 9 >> Consider a greedy algorithm for the VERTEX-COVER problem, where we repeatedly choose a vertex with maximum degree, add it to our cover, and then remove it and all its incident edges. Show that this algorithm does not, in general, produce a 2-approximation. Hint: Use a bipartite gra
Answer Preview: 4 Properties If a graph is a bipartite graph then it ll n…

, Chapter: 15 -Problem: 11 >> Suppose Vojtech Jarnìk had an evil twin, named Stanislaw, who designed a divideand-conquer algorithm for finding minimum spanning trees. Suppose G is an undirected, connected, weighted graph, and, for the sake of simplicity, let us further suppose that the weights of the edges in G are distinct. Stanislaw’s algorithm, MinTree(G), is as follows: If G is a single vertex, then it just returns, output
Answer Preview: Stanislaws algorithm is not correct Consider an example graph that is a square abcd with we…

, Chapter: 17 -Problem: 5 >> Consider the problem DNF-DISSAT, which takes a Boolean formula S in disjunctive normal form (DNF) as input and asks whether S is dissatisfiable, that is, there is an assignment of Boolean values to the variables of S so that it evaluates to 0. Show that DNF-DISSAT is NP-complete.
Answer Preview: 1 Produce the complete truth table for the given DNF For i…

, Chapter: 17 -Problem: 7 >> Show that the CLIQUE problem is in NP.
Answer Preview: To show that CLIQUE is in N…

, Chapter: 1 -Problem: 29 >> Describe a recursive algorithm for finding both the minimum and the maximum elements in an array A of n elements. Your method should return a pair (a, b), where a is the minimum element and b is the maximum. What is the running time of your method?
Answer Preview: The stocks par value is legally significant because it reflec…

, Chapter: 17 -Problem: 17 >> The Manhattan distance between two points (a, b) and (c, d) in the plane is |a ? c| + |b ? d|. Using Manhattan distance to define the cost between every pair of points, find an optimal traveling salesperson tour of the following set of points: {(1, 1),(2, 8),(1, 5),(3, ?4),(5, 6),(?2, ?6)}.
Answer Preview: The optimal traveling salesperson tour of the given set of poi…

, Chapter: 24 -Problem: 2 >> Write a nonrecursive version of Algorithm EuclidGCD.
Answer Preview: Here is the c code for a non recur…

, Chapter: 1 -Problem: 28 >> Give complete pseudocode for a new class, ShrinkingTable, that performs the add method of the extendable table, as well as methods, remove(), which removes the last (actual) element of the table, and shrinkToFit(), which replaces the underlying array with an array whose capacity is exactly equal to the number of elements currently in the table.
Answer Preview: Class shaking table private object array Private int …

, Chapter: 17 -Problem: 11 >> Define HYPER-COMMUNITY to be the problem that takes a collection of n web pages and an integer k, and determines if there are k web pages that all contain hyperlinks to each other. Show that HYPER-COMMUNITY is NP-complete.
Answer Preview: HYPER COMMUNITY can be shown to be NP complete by reducing a known NP complete problem to it To do s…

, Chapter: 21 -Problem: 1 >> 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 x-coordinate of its element). What is the running time of your method?
Answer Preview: The algorithm for performing a twodimensional range search in a twodimensiona…

, Chapter: 2 -Problem: 1 >> In the children’s game “hot potato,” a group of n children sit in a circle passing an object, called the “potato,” around the circle (say in a clockwise direction). The children continue passing the potato until a leader rings a bell, at which point the child holding the potato must leave the game, and the other children close up the circle. This process is then continued until there is only one c
Answer Preview: This metho…

, Chapter: 17 -Problem: 2 >> Suppose the football coach for the Anteaters has heard about your abilities to solve challenging problems and has hired you to write a computer program that can decide which of their many trophies to feature on their prized trophy shelf. He is asking that you do this as a computer program, rather than just coming up with a single decision, because the Anteaters are getting new trophies every year.
Answer Preview: The decision version of this problem is to decide whether a given set …

, Chapter: 21 -Problem: 6 >> 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?
Answer Preview: The worstcase dep…

, Chapter: 2 -Problem: 16 >> Show how to represent an improper binary tree by means of a proper one.
Answer Preview: were asked to use structural induction show that LMT which is the number of leaves on a full binary tree T is one more an eye of tea which is you Numb…

, Chapter: 16 -Problem: 7 >> Give an algorithm that determines, in O(n + m) time, whether a graph with n vertices and m edges is bipartite.
Answer Preview: Start from some vertex v and perform a breadth first search …

, Chapter: 23 -Problem: 9 >> Show how to perform prefix matching queries using a suffix trie.
Answer Preview: Trie In a trie each alphabet of all the strings in the prescrib…

, Chapter: 2 -Problem: 7 >> Let T be a binary tree such that all the external nodes have the same depth. Let De be the sum of the depths of all the external nodes of T, and let Di be the sum of the depths of all the internal nodes of T. Find constants a and b such that  where n is the number of nodes of T. Transcribed Image Text:
Answer Preview: Given a binary tree T with n external nodes the sum of the depths …

, Chapter: 15 -Problem: 8 >> Suppose you are given a weighted graph, G, with n vertices and m edges, such that the weight of each edge in G is a real number chosen independently at random from the interval [0, 1]. Show that the expected running time of the PrimJarnìk algorithm on G is O(n log2 n + m), assuming the priority queue, Q, is implemented with a heap, as described in the chapter.
Answer Preview: For any vertex v in G the expected number of times …

, Chapter: 24 -Problem: 6 >> 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.
Answer Preview: In publickey cryptography there are two parts to the key a secret part and a public part In order fo…

, Chapter: 1 -Problem: 12 >> Given an array, A, of n ? 2 unique integers in the range from 1 to n, describe an O(n)-time method for finding the two integers in the range from 1 to n that are not in A. You may use only O(1) space in addition to the space used by A.
Answer Preview: Compute the sum of all the integers in A and compu…

, Chapter: 15 -Problem: 5 >> Consider a scenario where you have a set of n players in a multiplayer game that we would like to connect to form a team. You are given a connected, weighted, undirected graph, G, with n vertices and m edges, which represents the n players and the m possible connections that can be made to link them together in a communicating team (that is, a connected subgraph of G). In this case, the weight on
Answer Preview: The algorithm that can be used to find the minimum spanning …

, Chapter: 23 -Problem: 4 >> 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, that have the same prefix, p, or suffix, s. Indeed, it is useful even to just know the number of such
Answer Preview: One way to build a data structure for W would be to construct a trie which is a treelike data …

, Chapter: 2 -Problem: 2 >> Solve the previous exercise using a queue instead of stack. That is, suppose you are given an array, A, containing n numbers in order, as in the previous exercise. Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through the cells of A, to insert each element into a queue, and then another for-loop that removes the eleme
Answer Preview: Solution Queue Follows FIFO principle Elements are insert…

, Chapter: 17 -Problem: 15 >> Show that the KNAPSACK problem is solvable in polynomial time if the input is given in a unary encoding. That is, show that KNAPSACK is not strongly NPhard. What is the running time of your algorithm?
Answer Preview: It is little tricky to get this idea Let me explain with an simple conversation between p1 and p2 p1 …

, Chapter: 19 -Problem: 14 >> Give a pseudocode description of the remove dictionary operation, assuming the dictionary is implemented by a skip-list structure.
Answer Preview: A dictionary is defined as a generalpurpose data structure for storing a group …

, Chapter: 4 -Problem: 3 >> Suppose a used car dealer, Jalopy Joe, has asked you to build a website for his car dealership. He wants this website to allow users to be able to search for a set of cars on his lot that are in their price range. That is, viewed abstractly, he would like you to build a system that can maintain an ordered collection, D, of key-value pairs, such that, in addition to the standard insert and removal
Answer Preview: Search for k 1 and then k 2 each while marking the path down to that …

, Chapter: 16 -Problem: 5 >> Draw a flow network with 9 vertices and 12 edges. Illustrate an execution of the Ford-Fulkerson algorithm on it.
Answer Preview: Given a graph which represents a flow network where every edge has a capacity …

, Chapter: 21 -Problem: 4 >> 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 insertions and deletion, and characterize the running times for these and the rankRange method.
Answer Preview: Use a balanced binary tree T which stores the points of S in its external nodes ordered …

, Chapter: 1 -Problem: 30 >> Suppose you have an array of n numbers and you select each one independently with probability 1/n1/2. Use the Chernoff bound to determine an upper bound on the probability that you would have more than 4n1/2 elements in this random sample.
Answer Preview: The Chernoff bound states that for a function fx ex…

, Chapter: 18 -Problem: 2 >> In a synchronous optical network (SONET) ring, a collection of routers are connected with fiber-optic cables to form a single, simple cycle. A message between two routers, x and y, can then be transmitted by routing it clockwise or counter-clockwise around the ring. Given a set, M, of messages to transmit, each specified by a pair of routers (x, y), the ring-loading problem is to route all the mes
Answer Preview: Consider a greedy strategy of always taking the shortest route Let I be some interval between two ad…

, Chapter: 23 -Problem: 3 >> 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 a DNA text string of length n. Describe an O(n)-time method for finding the longest prefix of T that
Answer Preview: We can use a twopointer approach to solve this problem in On tim…

, Chapter: 2 -Problem: 6 >> Answer the following questions so as to justify Theorem 2.7. a. Draw a binary tree with height 7 and maximum number of external nodes. b. What is the minimum number of external nodes for a binary tree with height h? Justify your answer. c. What is the maximum number of external nodes for a binary tree with height h? Justify your answer. d. Let T be a binary tree with height h and n nodes. Show tha
Answer Preview: a A binary tree with height 7 and maximum number of external nodes can be constructed as follows For …

, Chapter: 17 -Problem: 17 >> Given a graph G and two distinct vertices, v and w in G, define HAMILTONIANPATH to be the problem of determining whether there is a path that starts at v and ends at w and visits all the vertices of G exactly once. Show that the HAMILTONIAN-PATH problem is NP-complete.
Answer Preview: A reduction from HAMILTONIAN CIRCUIT could be as follows Suppose we are given …

, Chapter: 19 -Problem: 12 >> 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.
Answer Preview: Ex is also called as mean of the probability distribution because it tell…

, Chapter: 2 -Problem: 2 >> Suppose that a friend has implemented a deque, as defined in the previous exercise, using a singly linked list, but hasn’t given you the details, for example, of whether the links go forward or backward in the list or whether sentinel nodes are used. Nevertheless, show that one of the insertion or removal methods must take ?(n) time, where n is the number of elements in the deque. Data From Previo
Answer Preview: The insertion or removal methods of a deque implemented with a singly linked list must take n time w…

,

, Chapter: 19 -Problem: 8 >> 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.
Answer Preview: Let x be an integer greater than 0 that is modulo p We then have a set of numbers ix mod p …

, Chapter: 1 -Problem: 15 >> Perform a similar analysis for method Loop5 shown in Algorithm 1.21.  Transcribed Image Text: 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+
Answer Preview: The Loo…

, Chapter: 17 -Problem: 14 >> Show that the SET-COVER problem is in NP.
Answer Preview: The set cover problem is a classical question in combinatoric…

, Chapter: 21 -Problem: 8 >> 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)}.
Answer Preview: KD Tree Level 0 …

, Chapter: 1 -Problem: 5 >> Suppose you are given a set of small boxes, numbered 1 to n, identical in every respect except that each of the first i contain a pearl whereas the remaining n ? i are empty. You also have two magic wands that can each test whether a box is empty or not in a single touch, except that a wand disappears if you test it on an empty box. Show that, without knowing the value of i, you can use the two wa
Answer Preview: This problem is very similar to the famous Egg dropping puzzle which can be solved using Dynamic programming Consider the case when we have only one w…

, Chapter: 18 -Problem: 6 >> In the bottleneck traveling salesperson problem (TSP), we are given an undirected graph G with weights on its edges and asked to find a tour that visits the vertices of G exactly once and returns to the start so as to minimize the cost of the maximum-weight edge in the tour. Assuming that the weights in G satisfy the triangle inequality, design a polynomial-time 3-approximation algorithm for bottl
Answer Preview: We can use the Held Karp algorithm to solve this problem The algorithm works by finding a mini…

, Chapter: 21 -Problem: 4 >> 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 single edge. This gives us a data structure known as the compressed quadtree. Describe an efficient met
Answer Preview: The algorithm for constructing a compressed quadtree for a set of n twodimensional p…

, Chapter: 1 -Problem: 22 >> Show that the summation . You may assume that n is a power of 2. Transcribed Image Text: E log2(n/i)] is O(n)
Answer Preview: Log2nP…

, Chapter: 17 -Problem: 13 >> Is there a subset of the numbers in {23, 59, 17, 47, 14, 40, 22, 8} that sums to 100? What about 130? Show your work.
Answer Preview: Answer therefore are two subset that sum to 100 1 23 47 22 8 2 17 …

, Chapter: 19 -Problem: 11 >> Give a randomized algorithm that computes all minimum cuts of a graph with high probability.
Answer Preview: A Simple Solution use MaxFlow based st cut algorithm to find minimum c…

, Chapter: 4 -Problem: 4 >> Suppose you are working for a victim-support group to build a website for maintaining a set, S, containing the names of all the registered sex offenders in a given area. The system should be able to list out the names of the people in S ordered by their Zip codes, and, within each Zip code, ordered alphabetically. It should also be able to list out the names of the people in S just for a given Zip
Answer Preview: Store the elements from S in a balanced binary search tree T ordered by a combination of Z…

, Chapter: 24 -Problem: 3 >> 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 Bob can update the tree, T, in O(log n) time, to reflect these changes? Data From Previous Exercise T
Answer Preview: Bob can update the tree T in Olog n time by first removing the document that is being rem…

, Chapter: 3 -Problem: 3 >> Suppose you have a binary search tree, T, storing numbers in the range from 1 to 500, and you do a search for the integer 250. Which of the following sequences are possible sequences of numbers that were encountered in this search. For the ones that are possible, draw the search path, and, for the ones that are impossible, say why. a. (2, 276, 264, 270, 250) b. (100, 285, 156, 203, 275, 250) c. (4
Answer Preview: a Possible The search path for this sequence is as follows 2 276 264 270 250 b Im…

, Chapter: 17 -Problem: 13 >> Show that the HAMILTONIAN-CYCLE problem on directed graphs is NP-complete.
Answer Preview: To prove this one way is to show that the Hamiltonian cycle p TSP a…

, Chapter: 19 -Problem: 7 >> Suppose that a well-known collector, Kivas Fajo, is trying to collect each of 50 coupons, as in the coupon collector problem. Derive good upper and lower bounds on the expected number of times that Kivas has to visit the ticket window to get all 50 coupons.
Answer Preview: Promotions and incentives play a key factor in driving customers towards a product and in boosti…

, Chapter: 1 -Problem: 5 >> Consider the following recurrence equation, defining a function T(n):  Show, by induction, that T(n) = n(n + 1)/2. Transcribed Image Text: if n = 1 T(n) = 3 T(n – 1) +n otherwise, 1
Answer Preview: we will solve this problem in two induction steps Base Step when n1 …

, Chapter: 16 -Problem: 6 >> Suppose a friend of yours has created a simulation game based on J.R.R. Tolkien’s epic The Lord of the Rings. The game environment is Middle Earth, which is populated by various noble creatures, including hobbits, humans, dwarves, and elves. Unfortunately, these noble creatures are under attack and need to get to safe havens, known as “strongholds.” Some strongholds are larger than others, of cour
Answer Preview: Create a source x and connect it to each populated region …

, Chapter: 21 -Problem: 7 >> 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.
Answer Preview: A range tree is defined as an ordered tree data structure to hold a lis…

, Chapter: 1 -Problem: 8 >> Given an array, A, describe an efficient algorithm for reversing A. For example, if A = [3, 4, 1, 5], then its reversal is A = [5, 1, 4, 3]. You can only use O(1) memory in addition to that used by A itself. What is the running time of your algorithm?
Answer Preview: the …

, Chapter: 15 -Problem: 8 >> Why do all the MST algorithms discussed in this chapter still work correctly even if the graph has negative-weight edges, and even negative-weight cycles?
Answer Preview: In Kruskal s algorithm the safe edge added to A subset of …

, Chapter: 19 -Problem: 12 >> Show that if the compositeness witness function, witness(x, n), of the RabinMiller algorithm returns true, then the number n is composite.
Answer Preview: This is again a somewhat stupid case for MillerRabin similar to your because y…

, Chapter: 1 -Problem: 6 >> Consider the following recurrence equation, defining a function T(n):  Show, by induction, that T(n)=2n+1 ? 1. Transcribed Image Text: if n = 0 T(n) = { 1 T(n – 1) + 2" otherwise,
Answer Preview: Base Case Seduction Hypo…

, Chapter: 17 -Problem: 5 >> Show how to construct a Boolean circuit C such that, if we create variables only for the inputs of C and then try to build

Additional Information

17 Reviews for Algorithm Design And Applications Textbook Questions And Answers