Questions and Answers of Practical Introduction To Data Structures

Write an algorithm to determine if two binary trees are identical when the ordering of the subtrees for a node is ignored. For example, if a tree has root node with value R, left child with value A
Write a postorder traversal function for general trees, similar to the preorder traversal function named print given in Section 6.1.2.A preorder traversal of the tree in Figure 6.3 visits the nodes
Write a function that takes as input a general tree and returns the number of nodes in that tree. Write your function to use the GenTree and GTNode ADTs of Figure 6.2. /** General tree ADT */
Describe how to implement the weighted union rule efficiently. In particular, describe what information must be stored with each node and how this information is updated when two trees are merged.
A potential alternatative to the weighted union rule for combining two trees is the height union rule. The height union rule requires that the root of the tree with greater height become the root of
Using the weighted union rule and path compression, show the array for the parent pointer implementation that results from the following series of equivalences on a set of objects indexed by the
Using the weighted union rule and path compression, show the array for the parent pointer implementation that results from the following series of equivalences on a set of objects indexed by the
Devise a series of equivalence statements for a collection of sixteen items that yields a tree of height 5 when both the weighted union rule and path compression are used. What is the total number of
One alternative to path compression that gives similar performance gains is called path halving. In path halving, when the path is traversed from the node to the root, we make the grandparent of
Analyze the fraction of overhead required by the “list of children” implementation, the “left-child/right-sibling” implementation, and the two linked implementations of Section 6.3.3. How do
Using the general tree ADT of Figure 6.2, write a function that takes as input the root of a general tree and returns a binary tree generated by the conversion process illustrated by Figure 6.14. /**
Use mathematical induction to prove that the number of leaves in a nonempty full K-ary tree is (K - 1)n + 1, where n is the number of internal nodes.
Derive the formulae for computing the relatives of a non-empty complete K-ary tree node stored in the complete tree representation of Section 5.3.3. Parent (r) = [(r - 1)/2] if r = 0. Left child(r)
Find the overhead fraction for a full K-ary tree implementation with space requirements as follows:(a) All nodes store data, K child pointers, and a parent pointer. The data field requires four bytes
(a) Write out the sequential representation for Figure 6.18 using the coding illustrated by Example 6.5.In Figure 6.17In Figure 6.18(b) Write out the sequential representation for Figure 6.18 using
Draw the binary tree representing the following sequential representation for binary trees illustrated by Example 6.5:ABD//E//C/F//In Figure 6.17 Example 6.5 For the binary tree of Figure 6.17, the
Draw the binary tree representing the following sequential representation for binary trees illustrated by Example 6.6 :A'/B'/C'/D'/G'/E In Figure 6.17Show the bit vector for leaf and internal nodes
Draw the general tree represented by the following sequential representation for general trees illustrated by Example 6.8 :XPC)Q)RV)M)))) Example 6.8 For the general tree of Figure 6.3, we get the
(a) Write a function to decode the sequential representation for binary trees illustrated by Example 6.5. The input should be the sequential representation and the output should be a pointer to the
Devise a sequential representation for Huffman coding trees suitable for use as part of a file compression utility (see Project 5.7).Project 5.7:The Huffman coding tree has minimum external path
Write classes that implement the general tree class declarations of Figure 6.2 using the dynamic “left-child/right-sibling” representation described in Section 6.3 .4. /** General tree ADT */
Write classes that implement the general tree class declarations of Figure 6.2 using the linked general tree implementation with child pointer arrays of Figure 6.12.Your implementation should support
Write classes that implement the general tree class declarations of Figure 6.2 using the linked general tree implementation with child pointer arrays of Figure 6.12.Your implementation must be able
Implement a BST file archiver. Your program should take a BST created in main memory using the implementation of Figure 5.14 and write it out to disk using one of the sequential representations of
Use the UNION/FIND algorithm to implement a solution to the following problem. Given a set of points represented by their xy-coordinates, assign the points to clusters. Any two points are defined to
In this project, you will run some empirical tests to determine if some variations on path compression in the UNION/FIND algorithm will lead to improved performance. You should compare the following
Using induction, prove that Insertion Sort will always produce a sorted array.
Write an Insertion Sort algorithm for integer key values. However, here’s the catch: The input is a stack (not an array), and the only variables that your algorithm may use are a fixed number of
The Bubble Sort implementation has the following inner for loop:for (int j=n-1; j>i; j--)Consider the effect of replacing this with the following statement:for (int j=n-1; j>0; j--)Would the new
When implementing Insertion Sort, a binary search could be used to locate the position within the first i - 1 elements of the array into which element i should be inserted. How would this affect the
Figure 7.5 shows the best-case number of swaps for Selection Sort as Θ(n).This is because the algorithm does not check to see if the ith record is already in the ith position; that is, it might
Recall that a sorting algorithm is said to be stable if the original ordering for duplicate keys is preserved. Of the sorting algorithms Insertion Sort, Bubble Sort, Selection Sort, Shellsort,
Recall that a sorting algorithm is said to be stable if the original ordering for duplicate keys is preserved. We can make any algorithm stable if we alter the input keys so that (potentially)
The discussion of Quicksort in Section 7.5 described using a stack instead of recursion to reduce the number of function calls made.(a) How deep can the stack get in the worst case?(b) Quicksort
Give a permutation for the values 0 through 7 that will cause Quicksort (as implemented in Section 7.5 ) to have its worst case behavior. 72 6 57 88 60 42 83 73 48 85 Pivot = 60 48 6 57 42 60 88 83
Assume L is an array, length(L) returns the number of records in the array, and qsort(L, i, j) sorts the records of L from i to j (leaving the records sorted in L) using the Quicksort algorithm. What
Modify Quicksort to find the smallest K values in an array of records. Your output should be the array modified so that the K smallest values are sorted in the first K positions of the array. Your
Modify Quicksort to sort a sequence of variable-length strings stored one after the other in a character array, with a second array (storing pointers to strings) used to index the strings. Your
Graph \(f_1(n) = n \log n\), \(f_2(n) = n^{1.5}\), and \(f_3(n) = n^2\) in the range \(1 \leq n \leq 1000\) to visually compare their growth rates. Typically, the constant factor in the running-time
Imagine that there exists an algorithm \(SPLIT_k\) that can split a list \(L\) of \(n\) elements into \(k\) sublists, each containing one or more elements, such that sublist \(i\) contains only
Here is a variation on sorting. The problem is to sort a collection of n nuts and n bolts by size. It is assumed that for each bolt in the collection, there is a corresponding nut of the same size,
(a) Devise an algorithm to sort three numbers. It should make as few comparisons as possible. How many comparisons and swaps are required in the best, worst, and average cases?(b) Devise an algorithm
Devise an efficient algorithm to sort a set of numbers with values in the range 0 to 30,000. There are no duplicates. Keep memory requirements to a minimum.
Which of the following operations are best implemented by first sorting the list of numbers? For each operation, briefly describe an algorithm to implement it, and state the algorithm’s asymptotic
Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? Why?
Implement Mergesort for the case where the input is a linked list.
Counting sort (assuming the input key values are integers in the range 0 to m - 1) works by counting the number of records with each key value in the first pass, and then uses this information to
Use an argument similar to that given in Section 7.9 to prove that log n is a worst-case lower bound for the problem of searching for a given value in a sorted array containing n elements. 7.9 Lower
One possible improvement for Bubble Sort would be to add a flag variable and a test that determines if an exchange was made during the current iteration.If no exchange was made, then the list is
Starting with the Java code for Quicksort given in this chapter, write a series of Quicksort implementations to test the following optimizations on a wide range of input data sizes. Try these
Write your own collection of sorting programs to implement the algorithms described in this chapter, and compare their running times. Be sure to implement optimized versions, trying to make each
Perform a study of Shellsort, using different increments. Compare the version shown in Section 7.3 , where each increment is half the previous one, with others. In particular, try implementing
The implementation for Mergesort given in Section 7.4 takes an array as input and sorts that array. At the beginning of Section 7.4 there is a simple pseudocode implementation for sorting a linked
Radix Sort is typically implemented to support only a radix that is a power of two. This allows for a direct conversion from the radix to some number of bits in an integer key value. For example, if
It has been proposed that heapsort can be optimized by altering the heap’s siftdown function. Call the value being sifted down X. Siftdown does two comparisons per level: First the children of X
Computer memory and storage prices change rapidly. Find out what the current prices are for the media listed in Figure 8.1. Does your information change any of the basic conclusions regarding disk
Assume a disk drive from the late 1990s is configured as follows. The total storage is approximately 675MB divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 512
Using the specifications for the disk drive given in Exercise 8.2, calculate the expected time to read one entire track, one sector, an d one byte. Show your calculations.Data from in exercise
Using the disk drive specifications given in Exercise 8.2, calculate the time required to read a 10MB file assumingData from in exercise 8.2Assume a disk drive from the late 1990s is configured as
Assume that a disk drive is configured as follows. The total storage is approximately 1033MB divided among 15 surfaces. Each surface has 2100 tracks, there are 64 sectors/track, 512 bytes/sector, and
Using the specifications for the disk drive given in Exercise 8.5, calculate the expected time to read one entire track, one sector, and one byte. Show your calculations.Data from in Exercise
Using the disk drive specifications given in Exercise 8.5, calculate the time required to read a 10MB file assuming(a) The file is stored on a series of contiguous tracks, as few tracks as
A typical disk drive from 2004 has the following specifications. The total storage is approximately 120GB on 6 platter surfaces or 20GB/platter. Each platter has 16K tracks with 2560 sectors/track (a
Using the specifications for the disk drive given in Exercise 8.8, calculate the expected time to read one entire track, one sector, and one byte. Show your calculations.Data from in Exercise 8.8A
Using the disk drive specifications given in Exercise 8.8, calculate the time required to read a 10MB file assumingData from in Exercise 8.8A typical disk drive from 2004 has the following
At the end of 2004, the fastest disk drive I could find specifications for was the Maxtor Atlas. This drive had a nominal capacity of 73.4GB using 4 platters (8 surfaces) or 9.175GB/surface. Assume
Using the specifications for the disk drive given in Exercise 8.11 , calculate the expected time to read one entire track, one sector, and one byte. Show your calculations.Data from in Exercise
Using the disk drive specifications given in Exercise 8.11, calculate the time required to read a 10MB file assumingData from in Exercise 8.11At the end of 2004, the fastest disk drive I could find
Prove that two tracks selected at random from a disk are separated on average by one third the number of tracks on the disk.
Assume that a file contains one million records sorted by key value. A query to the file returns a single record containing the requested key value. Files are stored on disk in sectors each
Assume that a virtual memory is managed using a buffer pool. The buffer pool contains five buffers and each buffer stores one block of data. Memory accesses are by block ID. Assume the following
Suppose that a record is 32 bytes, a block is 1024 bytes (thus, there are 32 records per block), and that working memory is 1MB (there is also additional space available for I/O buffers, program
Assume that working memory size is 256KB broken into blocks of 8192 bytes (there is also additional space available for I/O buffers, program variables, etc.). What is the expected size for the
Prove or disprove the following proposition: Given space in memory for a heap of M records, replacement selection will completely sort a file if no record in the file is preceded by M or more keys of
Imagine a database containing ten million records, with each record being 100 bytes long. Provide an estimate of the time it would take (in seconds) to sort the database on a typical workstation.
Assume that a company has a computer configuration satisfactory for processing their monthly payroll. Further assume that the bottleneck in payroll processing is a sorting operation on all of the
How can the external sorting algorithm described in this chapter be extended to handle variable-length records?
For a database application, assume it takes 10 ms to read a block from disk, 1 ms to search for a record in a block stored in memory, and that there is room in memory for a buffer pool of 5 blocks.
Pictures are typically stored as an array, row by row, on disk. Consider the case where the picture has 16 colors. Thus, each pixel can be represented using 4 bits. If you allow 8 bits per pixel, no
Implement a disk-based buffer pool class based on the LRU buffer pool replacement strategy. Disk blocks are numbered consecutively from the beginning of the file with the first block numbered as 0.
Implement an external sort based on replacement selection and multiway merging as described in this chapter. Test your program both on files with small records and on files with large records. For
Implement a quicksort for large files on disk by replacing all array access in the normal quicksort application with access to a virtual array implemented using a buffer pool. That is, whenever a
Section 8.5.1 suggests that an easy modification to the basic 2-way mergesort is to read in a large chunk of data into main memory, sort it with quicksort, and write it out for initial runs. Then, a
Think of a program you have used that is unacceptably slow. Identify the specific operations that make the program slow. Identify other basic operations that the program performs quickly enough.
Most programming languages have a built-in integer data type. Normally this representation has a fixed size, thus placing a limit on how large a value can be stored in an integer variable. Describe a
Define an ADT for character strings. Your ADT should consist of typical functions that can be performed on strings, with each function defined in terms of its input and output. Then define two
Define an ADT for a list of integers. First, decide what functionality your ADT should provide. Example 1.4 should give you some ideas. Then, specify your ADT in Java in the form of an abstract class
Briefly describe how integer variables are typically represented on a computer.(Look up one’s complement and two’s complement arithmetic in an introductory computer science textbook if you are
Define an ADT for a two-dimensional array of integers. Specify precisely the basic operations that can be performed on such arrays. Next, imagine an application that stores an array with 1000 rows
You have been assigned to implement a sorting program. The goal is to make this program general purpose, in that you don’t want to define in advance what record or key types are used. Describe ways
You have been assigned to implement a simple seqential search on an array. The problem is that you want the search to be as general as possible. This means that you need to support arbitrary record
Does every problem have an algorithm?
Does every algorithm have a Java program?
Consider the design for a spelling checker program meant to run on a home computer. The spelling checker should be able to handle quickly a document of less than twenty pages. Assume that the
Imagine that you have been hired to design a database service containing information about cities and towns in the United States, as described in Example 1.2. Suggest two possible implementations for
Imagine that you are given an array of records that is sorted with respect to some key field contained in each record. Give two different algorithms for searching the array to find the record with a
How would you go about comparing two proposed algorithms for sorting an array of integers? In particular,(a) What would be appropriate measures of cost to use as a basis for comparing the two sorting
A common problem for compilers and text editors is to determine if the parentheses (or other brackets) in a string are balanced and properly nested.For example, the string “((())())()” contains
A graph consists of a set of objects (called vertices) and a set of edges, where each edge connects two vertices. Any given pair of vertices can be connected by only one edge. Describe at least two
Imagine that you are a shipping clerk for a large company. You have just been handed about 1000 invoices, each of which is a single sheet of paper with a large number in the upper right corner. The

Showing 300 - 400 of 447