Questions and Answers of Data Structures Algorithms

Suppose you are given an integer c and an array, A, indexed from 1 to n, of n integers in the range from 1 to 5n (possibly with duplicates). Describe an efficient algorithm for determining if there
Repeat the previous problem assuming that you now have k magic wands, with k > 2 and k < log n. Express, as a function of n and k, the asymptotic number of wand touches needed to identify all
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
An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded
Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running times for performing a sequence of n add methods,
Consider an extendable table that supports both add and remove methods, as defined in the previous exercise. Moreover, suppose we grow the underlying array implementing the table by doubling its
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
Show that the summation . You may assume that n is a power of 2. E log2(n/i)] is O(n)
Show that the summation ENog, i] is O(n log n)
Draw a visual justification of Theorem 1.13 analogous to that of Figure 1.11b for the case when n is odd. Theorem 1.13For any integer n ≥ 1, we haveFigure 1.11b п(n + 1) Σ 2 i=1
Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons.
Consider the following recurrence equation, defining a function T(n): Show, by induction, that T(n)=2n. if n = 0 1 T(n) = 2T(n – 1) otherwise,
Consider the following recurrence equation, defining a function T(n):
Consider the following recurrence equation, defining a function T(n): Show, by induction, that T(n) = n(n + 1)/2. if n = 1 T(n) = 3 T(n – 1) +n otherwise, 1
What is the total running time of counting from 1 to n in binary if the time needed to add 1 to the current number i is proportional to the number of bits in the binary expansion of i that must
What is the amortized running time of the operations in a sequence of n operations P = p1p2 ...pn if the running time of pi is Θ(i) if i is a multiple of 3, and is constant otherwise?
Describe how to modify the MaxsubFastest algorithm so that it uses just a single loop and, instead of computing n + 1 different Mt values, it maintains just a single variable M.
Describe how to modify the description of the MaxsubFastest algorithm so that, in addition to the value of the maximum subarray summation, it also outputs the indices j and k that identify the
Consider the following recurrence equation, defining T(n), as Show, by induction, that T(n)=4n. 4 T(n) = { if n = 1 | T(n – 1) + 4 otherwise.
Bill has an algorithm, find2D, to find an element x in an n × n array A. The algorithm find2D iterates over the rows of A and calls the algorithm arrayFind, of Algorithm 1.12, on each one, until x
Order the following list of functions by the big-Oh notation. Group together (for example, by underlining) those functions that are big-Theta of one another.
Show that log3 n is o(n1/3).
Algorithm A uses 10n log n operations, while algorithm B uses n2 operations. Determine the value n0 such that A is better than B for n ≥ n0.
Show that the MaxsubSlow algorithm runs in Ω(n3) time.
Graph the functions 12n, 6n log n, n2, n3, and 2n using a logarithmic scale for the x- and y-axes; that is, if the function value f(n) is y, plot this as a point with x-coordinate at log n and
Suppose you are given a timetable, which consists of:• A set A of n airports, and for each airport a in A, a minimum connecting time c(a).• A set F of m flights, and the following, for each
Draw a simple undirected graph G that has 12 vertices, 18 edges, and 3 connected components.
Draw a standard trie for the following set of strings:{abab, baba, ccccc, bbaaaa, caa, bbaacc, cbcc, cbca}.
Draw a compressed trie for the strings given in the previous problem.Previous problemDraw a standard trie for the following set of strings:{abab, baba, ccccc, bbaaaa, caa, bbaacc, cbcc, cbca}.
Draw a figure illustrating the comparisons done by brute-force pattern matching for the text "aaabaadaabaaa" and pattern "aabaaa".
Repeat the previous problem for the Boyer-Moore algorithm, not counting the comparisons made to compute the last(c) function.
Repeat Exercise R-13.3 for the Knuth-Morris-Pratt algorithm, not counting the comparisons made to compute the failure function.Exercise R-13.3Draw a figure illustrating the comparisons done by
Let T be a red-black tree and let p be the position of the parent of the original node that is deleted by the standard search tree deletion algorithm. Prove that if p has one child, the deletion has
Let T be a red-black tree and let p be the position of the parent of the original node that is deleted by the standard search tree deletion algorithm. Prove that if p has zero children, the removed
Draw a schematic of an AVL tree such that a single remove operation could require Ω(logn) trinode restructurings (or rotations) from a leaf to the root in order to restore the height-balance
Let T be a red-black tree and let p be the position of the parent of the original node that is deleted by the standard search tree deletion algorithm. Prove that if p has two children, the removed
Insert, into an empty binary search tree, entries with keys 30, 40, 24, 58, 48, 26, 11, 13 (in this order). Draw the tree after each insertion.
Give a schematic figure, in the style of Figure 11.13, showing the heights of subtrees during a deletion operation in an AVL tree that triggers a trinode restructuring for the case in which the two
Give a concrete implementation of the pop method, in the context of a MutableSet abstract base class, that relies only on the five core set behaviors described in Section 10.5.2.
On page 406 of Section 10.1.3, we give an implementation of the method setdefault as it might appear in the MutableMapping abstract base class. While that method accomplishes the goal in a general
Show the result of rehashing the hash table shown in Figure 10.6 into a table of size 19 using the new hash function h(k) = 3k mod 17. 4 5 6 7 8 9 10 11 12 54 18 10 25 28 36 38 41 12 90 3.
What is the result of Exercise R-10.9 when collisions are handled by double hashing using the secondary hash function h'(k) = 7−(k mod 7)?Exercise R-10.9Draw the 11-entry hash table that results
Show the result of Exercise R-10.9, assuming collisions are handled by quadratic probing, up to the point where the method fails.Exercise R-10.9Draw the 11-entry hash table that results from using
Draw the 11-entry hash table that results from using the hash function, h(i) = (3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by
Give a concrete implementation of the items( ) method directly within the UnsortedTableMap class, ensuring that the entire iteration runs in O(n) time.
Give a concrete implementation of the items( ) method in the context of the MutableMapping class, relying only on the five primary abstract methods of that class. What would its running time be if
Give a concrete implementation of the pop method in the context of the MutableMapping class, relying only on the five primary abstract methods of that class.
Show that the sum which appears in the analysis of heap-sort, is ?(n log n). п log i, Σ1og , i=1
Consider a situation in which a user has numeric keys and wishes to have a priority queue that is maximum-oriented. How could a standard (minoriented) priority queue be used for such a purpose?
Illustrate the execution of the insertion-sort algorithm on the input sequence of the previous problem.Previous problemIllustrate the execution of the selection-sort algorithm on the following input
Illustrate the execution of the selection-sort algorithm on the following input sequence: (22, 15, 36, 44, 10, 3, 9, 13, 29, 25).
Implement a function that accepts a PositionalList L of n integers sorted in nondecreasing order, and another value V, and determines in O(n) time if there are two elements of L that sum precisely
Give a direct implementation of the num children method within the class BinaryTree.
Justify Table 8.2, summarizing the running time of the methods of a tree represented with a linked structure, by providing, for each method, a description of its implementation, and an analysis of
Answer the previous question for the case when T is a proper binary tree with more than one node.
The constructor for the CaesarCipher class in Code Fragment 5.11 can be implemented with a two-line body by building the forward and backward strings using a combination of the join method and an
Our DynamicArray class, as given in Code Fragment 5.3, does not support use of negative indices with _ _getitem_ _. Update that method to better match the semantics of a Python list. Code Fragment
In Code Fragment 5.1, we perform an experiment to compare the length of a Python list to its underlying memory usage. Determining the sequence of array sizes requires a manual inspection of the
Write a short recursive Python function that rearranges a sequence of integer values so that all the even values appear before all the odd values.
Write a short recursive Python function that takes a character string s and outputs its reverse. For example, the reverse of 'pots&pans' would be 'snap&stop'.
Describe a recursive function for converting a string of digits into the integer it represents. For example, '13531' represents the integer 13,531.
Draw the recursion trace for the execution of function reverse(S, 0, 5) (Code Fragment 4.10) on S = [4, 3, 6, 2, 6].
Draw the recursion trace for the computation of power(2,18), using the repeated squaring algorithm, as implemented in Code Fragment 4.12.
Draw the recursion trace for the computation of power(2,5), using the traditional function implemented in Code Fragment 4.11.
The syntax data.remove(value) for Python list data removes only the first occurrence of element value from the list. Give an implementation of a function, with signature remove all(data, value), that
Implement a function that reverses a list of elements by pushing them onto a stack in one order, and writing them back to the list in reversed order.
Alice has two queues, Q and R, which can store integers. Bob gives Alice 50 odd integers and 50 even integers and insists that she store all 100 integers in Q and R. They then play a game where Bob
Describe a recursive algorithm that counts the number of nodes in a singly linked list.
In certain applications of the queue ADT, it is common to repeatedly dequeue an element, process it in some way, and then immediately enqueue the same element. Modify the ArrayQueue implementation to
Implement a function that counts the number of nodes in a circularly linked list.
Suppose that x and y are references to nodes of circularly linked lists, although not necessarily the same list. Describe a fast algorithm for telling if x and y belong to the same list.
Our CircularQueue class of Section 7.2.2 provides a rotate( ) method that has semantics equivalent to Q.enqueue(Q.dequeue( )), for a nonempty queue. Implement such a method for the LinkedQueue class
Implement a function, with calling syntax max(L), that returns the maximum element from a PositionalList instance L containing comparable elements.
Redo the previously problem with max as a method of the PositionalList class, so that calling syntax L.max( ) is supported.
Update the PositionalList class to support an additional method find(e), which returns the position of the (first occurrence of ) element e in the list (or None if not found).
Provide support for a _ _reversed_ _ method of the PositionalList class that is similar to the given _ _iter_ _, but that iterates the elements in reversed order.
Describe an implementation of the PositionalList methods add last and add before realized by using only methods in the set {is empty, first, last, prev, next, add after, and add first}.
In the FavoritesListMTF class, we rely on public methods of the positional list ADT to move an element of a list at position p to become the first element of the list, while keeping the relative
Show that Σni=1 i2 is O(n3).
Given an n-element sequence S, Algorithm D calls Algorithm E on each element S[i]. Algorithm E runs in O(i) time when it is called on element S[i]. What is the worst-case running time of Algorithm D?
Give a big-Oh characterization, in terms of n, of the running time of the example 5 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =
Give a big-Oh characterization, in terms of n, of the running time of the example4 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =
Give a big-Oh characterization, in terms of n, of the running time of the example3 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =
Give a big-Oh characterization, in terms of n, of the running time of the example 2 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =
Give a big-Oh characterization, in terms of n, of the running time of the example1 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =
Show that n log n is Ω(n).
Show that 2n+1 is O(2n).
Show that (n+1)5 is O(n5).
Write a Python class that extends the Progression class so that each value in the progression is the absolute value of the difference between the previous two values. You should include a constructor
In similar spirit to the previous problem, augment the Sequence class with method _ _lt_ _, to support lexicographic comparison seq1 < seq2.
When using the ArithmeticProgression class of Section 2.4.2 with an increment of 128 and a start of 0, how many calls to next can we make before we reach an integer of 263 or larger?
In Section 2.3.3, we note that our Vector class supports a syntax such as v = u + [5, 3, 10, −2, 1], in which the sum of a vector and list returns a new vector. However, the syntax v = [5, 3, 10,
Implement the _ _neg_ _ method for the Vector class of Section 2.3.3, so that the expression −v returns a new vector instance whose coordinates are all the negated values of the respective
Write a Python program that outputs all possible strings formed by using the characters 'c', 'a', 't', 'd', 'o', and g exactly once.
In Section 1.8, we provided three different implementations of a generator that computes factors of a given integer. The third of those implementations, from page 41, was the most efficient, but we
Write a short Python function that counts the number of vowels in a given character string.
Give an example of a Python code fragment that attempts to write an element to a list based on an index that may be out of bounds. If that index is out of bounds, the program should catch the
Write a short Python program that takes two arrays a and b of length n storing int values, and returns the dot product of a and b. That is, it returns an array c of length n such that c[i] = a[i] ·
Write a Python program that repeatedly reads lines from standard input until an EOFError is raised, and then outputs those lines in reverse order (a user can indicate end of input by typing ctrl-D).
Python’s random module includes a function shuffle(data) that accepts a list of elements and randomly reorders the elements so that each possible order occurs with equal probability. The random

Showing 700 - 800 of 819