New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
computer science
practical introduction to data structures

Practical Introduction To Data Structures And Algorithm Analysis Java Edition 1st Edition Clifford A. Shaffer - Solutions

Complete the implementation of the Huffman coding tree, building on the code presented in Section 5.6. Include a function to compute and store in a table the codes for each letter, and functions to encode and decode messages.This project can be further extended to support file compression. To do so
Write an algorithm to determine if two general trees are identical. Make the algorithm as efficient as you can. Analyze your algorithm’s running time.
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 and right child with value B, this would be considered identical to another tree with root node value
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 in order RACDEBF.A postorder traversal of this tree visits the nodes in order CDEAFBR. A C) (D) (E R
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 */ interface GenTree { public void clear(); public GTNode root (); // Clear the tree // Return the root //
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. Modify the implementation of Figure 6.4 to support the weighted union rule. /** General Tree class
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 the union. Explain why the height union rule can lead to worse average time behavior than 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 values 0 through 15. Initially, each element in the set should be in a separate equivalence class. When
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 values 0 through 15. Initially,each element in the set should be in a separate equivalence class. When
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 parent pointers followed to perform this series?
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 every other node i on the path the new parent of i. Write a version of FIND that implements path
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 these implementations compare in space efficiency? A R C D E R' B) FL X) Left Val Par Right 1 R 78-
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. /** General tree ADT */ interface GenTree { public void clear(); public GTNode root (); // Make the
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) = 2r + 1 if 2r +1
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 and each pointer requires four bytes.(b) All nodes store data and K child pointers. The data field
(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 the coding illustrated by Example 6.6. 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.5:ABD//E//C/F//In Figure 6.17 Example 6.5 For the binary tree of Figure 6.17, the corresponding se- quential representation would be as follows (assuming that stands for null):
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 (as illustrated by Example 6.7 )for this tree. Example 6.6 We can represent the tree of Figure 6.17
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 sequential representation RAC)D)E))BF))) (6.4) Note that F is followed by three ")" marks, because it
(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 root of the resulting binary tree.In Figure 6.17(b) Write a function to decode the sequential
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 weight is from Knuth [Knu97].
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 */ interface GenTree { public void clear(); // Clear the tree. public GTNode root (); // Return the root
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 only fixed-size nodes that do not change their number of children once they are created.Then,
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 to support changes in the number of children for a node. When created, a node should be allocated
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 Section 6.5. It should also be able to read in disk files using your sequential representation and
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 be in the same cluster if they are within a specified distance d of each other. For the purpose of
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 four implementations:(a) Standard UNION/FIND with path compression and weighted union.(b) Path
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 integers and a fixed number of stacks. The algorithm should return a stack containing the records in
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 implementation work correctly? Would the change affect the asymptotic complexity of the algorithm? How
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 number of comparisons required?How would using such a binary search affect the asymptotic running
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 perform unnecessary swaps.(a) Modify the algorithm so that it does not make unnecessary swaps.(b) What
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, Quicksort, Mergesort, Heapsort, Binsort, and Radix Sort, which of these are stable, and which are not? For
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) duplicate key values are made unique in a way that the first occurance of the original duplicate value is
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 makes two recursive calls. The algorithm could be changed to make these two calls in a specific order.
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 73 72 85 Pivot = 6 Pivot = 73 6 42 57 48 Pivot = 57 Pivot = 42 42 48 57 42 48 6 72 73 85 88 83 Pivot
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 is the averagecase time complexity for each of the following code fragments?(a) for (i=0; i
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 algorithm should do the minimum amount of work necessary.
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 function should modify the index array so that the first pointer points to the beginning of the lowest
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 expression for an implementation of Insertion Sort will be less than the constant factors for
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 elements whose values are less than all elements in j for i Furthermore, assume that the k lists can be
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, but initially we do not know which nut goes with which bolt. The differences in size between two nuts
(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 to sort five numbers. It should make as few comparisons as possible. How many comparisons and swaps
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 complexity.(a) Find the minimum value.(b) Find the maximum value.(c) Compute the arithmetic mean.(d)
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 place the records in order in a second pass. Write an implementation of counting sort (see the
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 Bounds for Sorting This book contains many analyses for algorithms. These analyses generally define
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 sorted and so the algorithm can stop early. This makes the best case performance become O(n) (because if
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 optimizations in various combinations to try and develop the fastest possible Quicksort implementation that
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 program as fast as possible.Do you get the same relative timings as shown in Figure 7.13? If not, why do
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 “division by 3” where the increments on a list of length n will be n=3, n=9, etc. Do other increment
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 list using Mergesort. Implement both a linked list-based version of Mergesort and the array-based
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 the radix is 16, then a 32-bit key will be processed in 8 steps of 4 bits each. This can lead to a
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 are compared, then the winner is compared to X. If X is too small, it is swapped with its larger child
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 processing? Medium 1996 1997 2000 2004 2006 RAM Disk Flash drive 2008 0.0339 $45.00 7.00 1.500 0.3500
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 bytes/sector, and 8 sectors/cluster. The disk turns at 3600 rpm. The track-to-track seek time is 20 ms,
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 8.2Assume a disk drive from the late 1990s is configured as follows. The total storage is approximately
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 follows. The total storage is approximately 675MB divided among 15 surfaces. Each surface has 612
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 8 sectors/cluster. The disk turns at 7200 rpm. The track-to-track seek time is 3 ms, and the
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 8.5Assume that a disk drive is configured as follows. The total storage is approximately 1033MB divided
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 possible.(b) The file is spread randomly across the disk in 4KB clusters.Show your calculations.Data from in
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 sector holds 512 bytes) and 16 sectors/cluster. The disk turns at 7200 rpm. The track-to-track seek
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 typical disk drive from 2004 has the following specifications. The total storage is approximately
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 specifications. The total storage is approximately 120GB on 6 platter surfaces or 20GB/platter. Each platter
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 there are 16,384 tracks with an average of 1170 sectors/track and 512 bytes/sector.3 The disk turns
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 8.11At the end of 2004, the fastest disk drive I could find specifications for was the Maxtor Atlas. This
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 specifications for was the Maxtor Atlas. This drive had a nominal capacity of 73.4GB using 4 platters
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 containing 100 records. Assume that the average time to read a sector selected at random is 10.0 ms. In
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 series of memory accesses takes place:5 2 5 12 3 6 5 9 3 2 4 1 5 9 8 15 3 7 2 5 9 10 4 6 8 5 For each of
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 variables, etc.). What is the expected size for the largest file that can be merged using replacement
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 largest file that can be merged using replacement selection followed by two passes of multiway merge?
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 greater value.
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 employee records, and that an external sorting algorithm is used. The company’s payroll program is so
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. Requests come in for records, with the request specifying which block contains the record. If a block
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 processing is required to unpack the pixels (because a pixel corresponds to a byte, the lowest level
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. Assume that blocks are 4096 bytes in size, with the first 4 bytes used to store the block ID
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 what size record do you find that key sorting would be worthwhile?
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 record in the array would be read or written by quicksort, use a call to a buffer pool function
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 standard 2-way merge is used in a series of passes to merge the runs together. However, this makes
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 representation for integers that has no size restriction (other than the limits of the computer’s
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 different physical representations for strings.
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 declaration, showing the functions, their parameters, and their return types. Example 1.4 An ADT
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 not familiar with these.)Why does this representation for integers qualify as a data structure as
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 and 1000 columns, where less than 10,000 of the array values are non-zero. Describe two different
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 to generalize a simple sorting algorithm (such as insertion sort, or any other sort you are
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 and key types. Describe ways to generalize the search function to support this goal. Consider the
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 spelling checker comes with a dictionary of about 20,000 words. What primitive operations must be
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 the database. Example 1.2 A company is developing a database system containing information about
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 specified key value. Which one do you consider “better” and why?
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 algorithms?(b) What tests or analysis would you conduct to determine how the two algorithms perform
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 properly nested pairs of parentheses, but the string “)()(” does not; and the string “())”

Showing 300 - 400 of 449

1
2
3
4
5

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved