Introduction To Programming In Java An Interdisciplinary Approach 2nd Edition Robert Sedgewick, Kevin Wayne - Solutions

True or false: Given a BST, let \(x\) be a leaf node, and let \(p\) be its parent. Then either (1) the key of \(p\) is the smallest key in the BST larger than the key of \(x\) or (2) the key of \(p\) is the largest key in the BST smaller than the key of \(x\).
The following code fragment (adapted from a Java programming book) creates a random permutation of the integers from 0 to \(n-1\). Determine the order of growth of its running time as a function of \(n\). Compare its order of growth with the shuffling code in SECtion 1.4. int[] a = new int[n];
A concordance is an alphabetical list of the words in a text that gives all word positions where each word appears. Thus, java Index 0 produces a concordance. In a famous incident, one group of researchers tried to establish credibility while keeping details of the Dead Sea Scrolls secret from
Write a method delete() that takes the first Node in a linked list and an int argument \(k\) and deletes the kth node in the linked list, if it exists.
Write a program to generate random connected graphs and 2-ring graphs with random shortcuts. Using SmallWorld, generate 500 random graphs from both models (with 1,000 vertices each) and compute their average degree, average path length, and clustering coefficient.
Given a bitonic array of \(n\) distinct integers, design a logarithmic-time algorithm to determine whether a given integer is in the array.
Given an array of \(n\) real numbers, design a linearithmic-time algorithm to find a pair of numbers that are closest in value.
Write a SmallWorld and Graph client that generates \(k\)-ring graphs and tests whether they exhibit the small-world phenomenon (first do EXERCISE 4.5.23). 3-ring graph
The following table gives running times for three programs for various values of \(n\). Fill in the blanks with estimates that you think are reasonable on the basis of the information given.Give hypotheses for the order of growth of the running time of each program. program A B C 1,000 0.001 second
Run experiments to validate the claims in the text that the put operations and get requests for Lookup and Index are logarithmic in the size of the table when using ST. Develop test clients that generate random keys and also run tests for various data sets, either from the booksite or of your own
Suppose that \(\mathrm{x}\) is a linked-list Node. What is the effect of the following code fragment?\(t\). next \(=x\). next;\(x \cdot\) next \(=t ;\)
Design a quadratic-time algorithm that, given an array of integers, finds a pair that are closest to each other.
Write a Graph and PathFinder client that takes the name of a movie-cast file and a delimiter as arguments and writes a new movie-cast file, but with all movies not connected to Kevin Bacon removed.
Given an array of \(n\) integers, design an algorithm to determine whether any three of them sum to 0 . The order of growth of the running time of your program should be \(n^{2} \log n\). Extra credit: Develop a program that solves the problem in quadratic time.
Write a method remove() that takes a linked-list Node and a string key as its arguments and removes every node in the list whose item field is equal to key.
A value in an array of length \(n\) is a majority if it appears strictly more than \(n / 2\) times. Given an array of strings, design a linear-time algorithm to identify a majority element (if one exists).
Find the performers in movies.txt with the largest, but finite, Kevin Bacon number.
The "beck" exploit. A popular web server supports a function named no2s7ash() whose purpose is to collapse multiple / characters. For example, the string /d1///d2////d3/test. htm1 collapses to \(/ \mathrm{d} 1 / \mathrm{d} 2 / \mathrm{d} 3 /\) test. htm 1 . The original algorithm was to repeatedly
Modify BST to add a method size() that returns the number of key-value pairs in the symbol table. Use the approach of storing within each Node the number of nodes in the subtree rooted there.
Write a method \(\operatorname{copy}()\) that takes a linked-list Node as its argument and creates a new linked list with the same sequence of items, without destroying the original linked list.
Modify BST to add methods floor() and cei1ing() that take as an argument a key and return the largest (smallest) key in the symbol table that is no larger (no smaller) than the specified key (or nu11 if no such key exists).
Write a method removeAfter() that takes a linked-list Node as its argument and removes the node following the given one (and does nothing if either the argument is nu11 or the next field of the argument is nu17).
Given an array of \(n\) integers, design a linearithmic-time algorithm to determine whether any two of them sum to 0 .
Calculate the probability that no triple among \(n\) random 32-bit integers sums to 0. Extra credit: Give an approximate formula for the expected number of such triples (as a function of \(n\) ), and run experiments to validate your estimate.
Modify BST to add methods \(\min ()\) and \(\max ()\) that return the smallest (or largest) key in the table (or nu17 if no such key exists).
Why does the following code fragment not have the same effect as the code fragment in the previous question? x.next t.next = t; = x.next;
In a grid graph, vertices are arranged in an \(n\)-by- \(n\) grid, with edges connecting each vertex to its neighbors above, below, to the left, and to the right in the grid. Compose a SmallWorld and Graph client that generates grid graphs and tests whether they exhibit the small-world phenomenon
Given an array of \(n\) real numbers, design a linear-time algorithm to find a pair of numbers that are furthest apart in value.
Modify BST to add a method rangeSearch () that takes two keys as arguments and returns an iterable over all keys that are between the two given keys. The running time should be proportional to the height of the tree plus the number of keys in the range.
Write a program SubsetSum that reads 1ong integers from standard input, and counts the number of subsets of those integers that sum to exactly zero. Give the order of growth of the running time of your program.
Watts and Strogatz proposed a hybrid model that contains typical links of vertices near each other (people know their geographic neighbors), plus some random long-range connection links. Plot the effect of adding random edges to an \(n\)-by- \(n\) grid graph on the average path length and on the
The indegrees and outdegrees of pages in the web obey a power law that can be modeled by a preferred attachment process. Suppose that each web page has exactly one outgoing link. Each page is created one at a time, starting with a single page that points to itself. With probability \(p
Young tableaux. Suppose you have an \(n\)-by- \(n\) array of integers a [] [] such that, for all \(i\) and \(j, a[i][j]A two-dimensional array with this property is known as a Young tableaux. Write a function that takes as arguments an n-by-n Young tableaux and an integer, and determines whether
In data compression, a set of strings is prefix-free if no string is a prefix of another. For example, the set of strings \(\{01,10,0010,1111\}\) is prefix-free, but the set of strings \(\{01,10,0010,1010\}\) is not prefix-free because 10 is a prefix of 1010 . Write a program that reads in a set of
Develop a recursive solution to the previous question.Data from in previous question.Write a method \(\max ()\) that takes the first Node in a linked list as its argument and returns the value of the maximum item in the list. Assume that all items are positive integers, and return 0 if the linked
Write an ST client that creates a symbol table mapping letter grades to numerical scores, as in the table below, and then reads from standard input a list of letter grades and computes their average (GPA). A+ A A- B+ B B- C+ C C - 4.33 4.00 3.67 3.33 3.00 2.67 2.33 2.00 1.67 D F 1.00 0.00
Given an array of \(n\) elements, give a linear-time algorithm to rotate the string \(k\) positions. That is, if the array contains \(a_{0}, a_{1}, \ldots, a_{n-1}\), the rotated array is \(a_{k}, a_{k+1}, \ldots, a_{n-1}, a_{0}, \ldots, \mathrm{a}_{k-1}\). Use at most a constant amount of extra
A connected component in a graph is a maximal set of vertices that are mutually connected. Write a Graph client CCFinder that computes the connected components of a graph. Include a constructor that takes a Graph as an argument and computes all of the connected components using breadth-first
Design a linear-time algorithm to sort an array of Comparable objects that is known to have at most two distinct values. Hint: Maintain two pointers, one starting at the left end and moving right, and the other starting at the right end and moving left. Maintain the invariant that all elements to
Implement the following methods, each of which takes as its argument a Node that is the root of a binary tree.Your methods should all run in linear time. int size() int leaves () double total() number of nodes in the tree number of nodes whose links are both null sum of the key values in all nodes
Write a method that takes the first Node in a linked list as its argument and reverses the list, returning the first Node in the result.
Finding a repeated integer.(a) Given an array of \(n\) integers from 1 to \(n\) with one value repeated twice and one missing, give an algorithm that finds the missing integer, in linear time and constant extra memory. Integer overflow is not allowed.(b) Given a read-only array of \(n\) integers,
Design a linear-time algorithm to sort an array of Comparable objects that is known to have at most three distinct values. (Edsger Dijkstra named this the Dutch-national-flag problem because the result is three "stripes" of values like the three stripes in the flag.)
Implement a linear-time method height() that returns the maximum number of links on any path from the root to a leaf node (the height of a one-node tree is 0 ).
Design a fast algorithm to compute \(n\) ! for large values of \(n\), using Java's BigInteger class. Use your program to compute the longest run of consecutive \(9 \mathrm{~s}\) in 1000000 !. Develop and validate a hypothesis for the order of growth of the running time of your algorithm.
Write a program WordLadder that takes two 5 -letter strings as command-line arguments, reads in a list of 5-letter words from standard input, and prints a shortest word ladder using the words on standard input connecting the two strings (if it exists). Two words are adjacent in a word ladder chain
Write a recursive method to randomly shuffle the nodes of a linked list by modifying the links. Easy: Use quadratic time, constant extra space. Not so easy: Develop a divide-and-conquer algorithm that takes linearithmic time and uses logarithmic extra memory.
A binary tree is heap ordered if the key at the root is larger than the keys in all of its descendants. Implement a linear-time method heapOrdered() that returns true if the tree is heap ordered, and false otherwise.
A double-ended queue or deque (pronounced "deck") is a collection that is a combination of a stack and a queue. Write a class Deque that uses a linked list to implement the following API: public class Deque Deque () boolean isEmpty() void enqueue (Item item) void push(Item item) Item pop() Item
A binary tree is balanced if both its subtrees are balanced and the height of its two subtrees differ by at most 1. Implement a linear-time method balanced () that returns true if the tree is balanced, and false otherwise.
Write a program that finds a contiguous subarray of length at most \(m\) in an array of \(n\) long integers that has the highest average value among all such subarrays, by trying all subarrays. Use the scientific method to confirm that the order of growth of the running time of your program is \(m
A random queue is a collection that supports the following API:Write a class RandomQueue that implements this API. Use a resizing array. To remove an item, swap one at a random position (indexed 0 through \(n-1\) ) with the one at the last position (index \(n-1\) ). Then, remove and return the last
Given an array of \(n\) real numbers, design a logarithmic-time algorithm to identify a local minimum (an index \(i\) such that both \(a[i]
Given an \(n\)-by- \(n\) subarray of black (1) and white (0) pixels, design a linear-time algorithm that finds the largest square subarray that contains no white pixels. In the following example, the largest such subarray is the 3-by-3 subarray highlighted in blue.Implement your algorithm and
Two binary trees are isomorphic if only their key values differ (they have the same shape). Implement a linear-time static method isomorphic() that takes two tree references as arguments and returns true if they refer to isomorphic trees, and false otherwise. Then, implement a linear-time static
In the Tokyo subway system, routes are labeled by letters and stops by numbers, such as G-8 or A-3. Stations allowing transfers are sets of stops. Find a Tokyo subway map on the web, develop a simple file format, and write a Graph client that reads a file and can answer shortest-path queries for
Implement a linear-time method isBST() that returns true if the tree is a BST, and false otherwise.
Find a function whose order of growth is larger than any polynomial function, but smaller than any exponential function. Extra credit: Find a program whose running time has that order of growth.
We can measure how good a center Kevin Bacon is by computing each performer's Hollywood number or average path length. The Hollywood number of Kevin Bacon is the average Bacon number of all the performers (in its connected component). The Hollywood number of another performer is computed the same
In the Josephus problem from antiquity, \(n\) people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to \(n-1\) ) and proceed around the circle, eliminating every \(m\) th person until only one
Write a method leve1Order() that prints BST keys in level order: first print the root; then the nodes one level below the root, left to right; then the nodes two levels below the root (left to right); and so forth.
Implement a class that supports the following API, which generalizes both a queue and a stack by supporting removal of the \(i\) th most recently inserted item:First, develop an implementation that uses a resizing array, and then develop one that uses a linked list. public class GeneralizedQueue
The eccentricity of a vertex is the greatest distance between it and any other vertex. The diameter of a graph is the greatest distance between any two vertices (the maximum eccentricity of any vertex). Write a Graph client Diameter that can compute the eccentricity of a vertex and the diameter of
Compute the value returned by mystery () on some sample binary trees and then formulate a hypothesis about its behavior and prove it. public int mystery (Node x) { } if (x==nul1) return 0; return mystery(x.left) + mystery (x.right);
Implement a Digraph data type that represents directed graphs, where the direction of edges is significant: \(\operatorname{addEdge}(v, w)\) means to add an edge from \(v\) to \(w\) but not from \(w\) to \(v\). Replace adjacentTo () with two methods: one to give the set of vertices having edges
A ring buffer (or circular queue) is a FIFO collection that stores a sequence of items, up to a prespecified limit. If you insert an item into a ring buffer that is full, the new item replaces the least recently inserted item. Ring buffers are useful for transferring data between asynchronous
Write a SET client SpellChecker that takes as a commandline argument the name of a file containing a dictionary of words, and then reads strings from standard input and prints any string that is not in the dictionary. You can find a dictionary file on the booksite. Extra credit: Augment your
Modify your Digraph class from the previous exercise to make a MultiDigraph class that allows parallel edges. For a test client, run a random- surfer simulation that matches RandomSurfer (Program 1.6.2).Data from in previous exerciseImplement a Digraph data type that represents directed graphs,
Given two queues with strings in ascending order, move all of the strings to a third queue so that the third queue ends up with the strings in ascending order.
Write an ST client Spe17Corrector that serves as a filter that replaces commonly misspelled words on standard input with a suggested replacement, printing the result to standard output. Take as a command-line argument the name of a file that contains common misspellings and corrections. You can
Write a Digraph client TransitiveClosure whose constructor takes a Digraph as an argument and whose method isReachable (v, w) returns true if there exists some directed path from \(v\) to \(w\), and false otherwise.
Write a SET client WebBTocker that takes as a command-line argument the name of a file containing a list of objectionable websites, and then reads strings from standard input and prints only those websites not on the list.
Use statistical sampling to estimate the average path length and clustering coefficient of a graph. For example, to estimate the clustering coefficient, pick trials random vertices and compute the average of the clustering coefficients of those vertices. The running time of your functions should be
Show how to implement a queue using two stacks. Hint: If you push items onto a stack and then pop them all, they appear in reverse order. Repeating the process puts them back in FIFO order.
Add methods union() and intersection() to SET that take two sets as arguments and return the union and intersection, respectively, of those two sets.
A random walk in an undirected connected graph moves from a vertex to one of its neighbors, where each possibility has equal probability of being chosen. (This process is the random surfer analog for undirected graphs.) Write programs to run experiments that support the development of hypotheses
Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and reinsert it at the beginning.
Develop a data type FrequencyTable that supports the following operations: click() and count (), both of which take string arguments. The data type keeps track of the number of times the click() operation has been called with a given string as an argument. The click() operation increments the count
You have to sequence the order of \(\mathrm{n}\) jobs that are numbered from 0 to \(n-1\) on a server. Some of the jobs must complete before others can begin. Write a program TopologicaT Sorter that takes a command-line argument \(n\) and a sequence on standard input of ordered pairs of jobs \(i
Develop a data type that supports the following operations: insert a date, search for a date, and count the number of dates in the data structure that lie in a particular interval. Use Java's java.util. Date data type.
Develop a data type for a buffer in a text editor that implements the following API: public class Buffer Buffer () void insert(char c) char delete() void left(int k) void right(int k) int size() create an empty buffer insert c at the cursor position delete and return the character at the cursor
Given a list of non-overlapping intervals of integers, write a function that takes an integer argument and determines in which, if any, interval that value lies. For example, if the intervals are 1643-2033, 5532-7643, 8999-10332, and 5666653-5669321, then the query point 9122 lies in the third
Add a function to SmallWorld that computes the global clustering coefficient of a graph. The global clustering coefficient is the conditional probability that two random vertices that are neighbors of a common vertex are neighbors of each other. Find graphs for which the local and global clustering
Create a new constructor for the linked-list implementation of Stack so that Stack \(t=\) new Stack(s); makes \(t\) a reference to a new and independent copy of the stack s. You should be able to push and pop from either \(s\) or \(t\) without influencing the other.
Write a BST client that uses the data file ip-tocountry.csv found on the booksite to determine the source country of a given IP address. The data file has five fields: beginning of IP address range, end of IP address range, two-character country code, three-character country code, and country name.
Create a new constructor so that Queue \(r=\) new Queue \((q)\); makes \(r\) a reference to a new and independent copy of the queue \(q\).
Given a list of web pages, create a symbol table of words contained in those web pages. Associate with each word a list of web pages in which that word appears. Write a program that reads in a list of web pages, creates the symbol table, and supports single-word queries by returning the list of web
Bollobás and Chung proposed a hybrid model that combines a 2-ring on \(V\) vertices ( \(V\) is even), plus a random matching. A matching is a graph in which every vertex has degree 1. To generate a random matching, shuffle the \(V\) vertices and add an edge between vertex \(i\) and vertex \(i+1\)
Develop a data type Quote that implements the following API for quotations:To do so, define a nested class Card that holds one word of the quotation and a link to the next word in the quotation: public class Quote Quote () void add(String word) void add (int i, String word) String get(int i) int
Write a program that takes \(k\) words from the command line, reads in a sequence of words from standard input, and identifies the smallest interval of text that contains all of the \(k\) words (not necessarily in the same order). You do not need to consider partial words.
Write a nonrecursive function that takes the first Node in a linked list as an argument and reverses the list, returning the first Node in the result.
In the game of chess, if a board position is repeated three times with the same side to move, the side to move can declare a draw.Describe how you could test this condition using a computer program.
Write a recursive function that takes the first Node in a linked list as an argument and reverses the list, returning the first Node in the result.
The registrar at a prominent northeastern university recently scheduled an instructor to teach two different classes at the same exact time. Help the registrar prevent future mistakes by describing a method to check for such conflicts. For simplicity, assume all classes run for 50 minutes and start
Study what happens when you modify MM1Queue to use a stack instead of a queue. Does Little's law hold? Answer the same question for a random queue. Plot histograms and compare the standard deviations of the waiting times.
Write a program BaconHistogram that prints a histogram of Kevin Bacon numbers, indicating how many performers from movies. txt have a Bacon number of \(0,1,2,3, \ldots\) Include a category for those who have an infinite number (not connected at all to Kevin Bacon).
Given \(n\) timestamps for when a file is requested from a web server, find the largest interval of time in which no file is requested. Write a program to solve this problem in linearithmic time.
Write a method \(\max ()\) that takes the first Node in a linked list as its argument and returns the value of the maximum item in the list. Assume that all items are positive integers, and return 0 if the linked list is empty.
Modify BST to add a method rangeCount() that takes two keys as arguments and returns the number of keys in a BST between the two specified keys. Your method should take time proportional to the height of the tree.
Implement a class that supports the following API, which generalizes both a queue and a stack by supporting removal of the \(i\) th least recently inserted item (see EXERCISE 4.3.40):Data From in ExerciseImplement a class that supports the following API, which generalizes both a queue and a stack

Showing 300 - 400 of 744

Introduction To Programming In Java An Interdisciplinary Approach 2nd Edition Robert Sedgewick, Kevin Wayne - Solutions

Step by Step Answers