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

Assume that you have a ten-slot closed hash table (the slots are numbered 0 through 9). Show the final hash table that would result if you used the hash function h(k) = k mod 10 and quadratic probing on this list of numbers:3, 12, 9, 2, 79, 46. After inserting the record with key value 46, list for
Assume that you have a ten-slot closed hash table (the slots are numbered 0 through 9). Show the final hash table that would result if you used the hash function h(k) = k mod 10 and pseudo-random probing on this list of numbers: 3, 12, 9, 2, 79, 44. The permutation of offsets to be used by the
What is the result of running sfold from Section 9.4.1 on the following strings? Assume a hash table size of 101 slots.(a) HELLO WORLD(b) NOW HEAR THIS(c) HEAR THIS NOW
Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of thirteen slots (the slots are numbered 0 through 12). The hash functions to be used are H1 and H2, defined below.You should show the hash table after all eight keys have been inserted.Be
Write an algorithm for a deletion function for hash tables that replaces the record with a special value indicating a tombstone. Modify the functions hashInsert and hashSearch to work correctly with tombstones.
Consider the following permutation for the numbers 1 to 6:2, 4, 6, 1, 3, 5.Analyze what will happen if this permutation is used by an implementation of pseudo-random probing on a hash table of size seven. Will this permutation solve the problem of primary clustering? What does this say about
Implement a binary search and the quadratic binary search of Section 9.1.Run your implementations over a large range of problem sizes, timing the results for each algorithm. Graph and compare these timing results. The location of a particular key within the key range is translated into the expected
Implement the three self-organizing list heuristics count, move-to-front, and transpose. Compare the cost for running the three heuristics on various input data. The cost metric should be the total number of comparisons required when searching the list. It is important to compare the heuristics
Implement a system for managing document retrieval. Your system should have the ability to insert (abstract references to) documents into the system, associate keywords with a given document, and to search for documents with specified keywords.
Implement a database stored on disk using bucket hashing. Define records to be 128 bytes long with a 4-byte key and 120 bytes of data. The remaining 4 bytes are available for you to store necessary information to support the hash table. A bucket in the hash table will be 1024 bytes long, so each
Implement the dictionary ADT of Section 4.4 by means of a hash table with linear probing as the collision resolution policy. You might wish to begin with the code of Figure 9.7.Using empirical simulation, determine the cost of insert and delete as α grows (i.e., reconstruct the dashed lines of
Assume that a computer system has disk blocks of 1024 bytes, and that you are storing records that have 4-byte keys and 4-byte data fields. The records are sorted and packed sequentially into the disk file.(a) Assume that a linear index uses 4 bytes to store the key and 4 bytes to store the block
Assume that a computer system has disk blocks of 4096 bytes, and that you are storing records that have 4-byte keys and 64-byte data fields. The records are sorted and packed sequentially into the disk file.(a) Assume that a linear index uses 4 bytes to store the key and 4 bytes to store the block
Modify the function binary of Section 3.5 so as to support variable-length records with fixed-length keys indexed by a simple linear index as illustrated by Figure 10.1. Linear Index 37 42 52 73 73 Database Records 52 98 98 37 42
Assume that a database stores records consisting of a 2-byte integer key and a variable-length data field consisting of a string. Show the linear index (as illustrated by Figure 10.1) for the following collection of records: Linear Index 37 42 52 73 73 Database Records 52 98 98 37 42
Each of the following series of records consists of a four-digit primary key (with no duplicates) and a four-character secondary key (with many duplicates).(a) Show the inverted list (as illustrated by Figure 10.4) for this collection of records.(b) Show the improved inverted list (as illustrated
Under what conditions will ISAM be more efficient than a B+-tree implementation?
Prove that the number of leaf nodes in a 2-3 tree with k levels is between 2k-1 and 3k-1.
Show the result of inserting the values 55 and 46 into the 2-3 tree of Figure 10.9. 10 12 15 18 33 20 21 23 30 24 Figure 10.9 A 2-3 tree. 31 48 45 47 50 52
You are given a series of records whose keys are letters. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J. Show the 2-3 tree that results from inserting these records.
You are given a series of records whose keys are letters. The records are inserted in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J. Show the tree that results from inserting these records when the 2-3 tree is modified to be a 2-3+ tree, that is, the internal nodes
Show the result of inserting the value 55 into the B-tree of Figure 10.16. 10 12 15 20 18 24 21 23 Figure 10.16 A B-tree of order four. 30 31 38 33 45 48 47 50 52 60
Show the result of inserting the values 1, 2, 3, 4, 5, and 6 (in that order) into the B+-tree of Figure 10.17. 101215 18 23 18 19 20 21 22 33 233031 33 45 47 48 48 50 52
Show the result of deleting the values 18, 19, and 20 (in that order) from the B+-tree of Figure 10.22b. 101215 18 18 19 20 21 22 23 (b) 23 30 31 33 45 47 48 50 52
You are given a series of records whose keys are letters. The records are inserted in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R,K, E, H, O, L, J. Show the B+-tree of order four that results from inserting these records. Assume that the leaf nodes are capable of storing up to
Assume that you have a B+-tree whose internal nodes can store up to 100 children and whose leaf nodes can store up to 15 records. What are the minimum and maximum number of records that can be stored by the B+-tree for 1, 2, 3, 4, and 5 levels?
Assume that you have a B+-tree whose internal nodes can store up to 50 children and whose leaf nodes can store up to 50 records. What are the minimum and maximum number of records that can be stored by the B+-tree for 1, 2, 3, 4, and 5 levels?
Implement a two-level linear index for variable-length records as illustrated by Figures 10.1 and 10.2. Assume that disk blocks are 1024 bytes in length.Records in the database file should typically range between 20 and 200 bytes, including a 4-byte key value. Each record of the index file should
Implement the 2-3+ tree, that is, a 2-3 tree where the internal nodes act only as placeholders. Your 2-3+ tree should implement the dictionary interface of Section 4.4. Dictionaries and Comparators The most common objective of computer programs is to store and retrieve data. Much of this book is
Implement the dictionary ADT of Section 4.4 for a large file stored on disk by means of the B+-tree of Section 10.5. Assume that disk blocks are 1024 bytes, and thus both leaf nodes and internal nodes are also 1024 bytes.Records should store a 4-byte (int) key value and a 60-byte data field.
Prove by induction that a graph with n vertices has at most n(n−1)/2 edges.
Prove the following implications regarding free trees.(a) If an undirected graph is connected and has no simple cycles, THEN the graph has |V| − 1 edges.(b) If an undirected graph has |V| − 1 edges and no cycles, THEN the graph is connected.
(a) Draw the adjacency matrix representation for the graph of Figure 11.25.(b) Draw the adjacency list representation for the same graph.(c) If a pointer requires four bytes, a vertex label requires two bytes, and an edge weight requires two bytes, which representation requires more space for this
Show the DFS tree for the graph of Figure 11.25 , starting at Vertex 1. 10 3 2 3 2 20 5 15 6 10 3 5 11
Wright a pseudocode algorithm to create a DFS tree for an undirected, connected graph starting at a specified vertex V.
Show the BFS tree for the graph of Figure 11.25, starting at Vertex 1. 10 3 2 3 2 20 5 15 6 10 3 5 11
Wright a pseudocode algorithm to create a BFS tree for an undirected, connected graph starting at a specified vertex V.
The BFS topological sort algorithm can report the existence of a cycle if one is encountered. Modify this algorithm to print the vertices possibly appearing in cycles (if there are any cycles).
Explain why, in the worst case, Dijkstra’s algorithm is (asymptotically) as efficient as any algorithm for finding the shortest path from some vertex I to another vertex J.
Show the shortest paths generated by running Dijkstra’s shortest-paths algorithm on the graph of Figure 11.25, beginning at Vertex 4. Show the D values as each vertex is processed, as in Figure 11.18. 10 3 2 3 2 20 5 15 6 10 3 5 11
Modify the algorithm for single-source shortest paths to actually store and return the shortest paths rather than just compute the distances.
The root of a DAG is a vertex R such that every vertex of the DAG can be reached by a directed path from R. Write an algorithm that takes a directed graph as input and determines the root (if there is one) for the graph. The running time of your algorithm should be Θ(|V| + |E|).
Write an algorithm to find the longest path in a DAG, where the length of the path is measured by the number of edges that it contains. What is the asymptotic complexity of your algorithm?
Write an algorithm to determine whether a directed graph of |V| vertices contains a cycle. Your algorithm should run in Θ(|V| + |E|) time.
Write an algorithm to determine whether an undirected graph of |V| vertices contains a cycle. Your algorithm should run in Θ(|V|) time.
The single-destination shortest-paths problem for a directed graph is to find the shortest path from every vertex to a specified vertex V. Write an algorithm to solve the single-destination shortest-paths problem.
List the order in which the edges of the graph in Figure 11.25 are visited when running Prim’s MST algorithm starting at Vertex 3. Show the final MST. 10 3 2 3 2 20 5 15 6 10 3 5 11
List the order in which the edges of the graph in Figure 11.25 are visited when running Kruskal’s MST algorithm. Each time an edge is added to the MST, show the result on the equivalence array, (e.g., show the array as in Figure 6.7). 10 3 2 3 2 20 5 15 6 10 3 5 11
Write an algorithm to find a maximum cost spanning tree, that is, the spanning tree with highest possible cost.
When can Prim’s and Kruskal’s algorithms yield different MSTs?
Prove that, if the costs for the edges of Graph G are distinct, then only one MST exists for G.
Consider the collection of edges selected by Dijkstra’s algorithm as the shortest paths to the graph’s vertices from the start vertex. Do these edges form a spanning tree (not necessarily of minimum cost)? Do these edges form an MST? Explain why or why not.
Prove that a tree is a bipartite graph.
Prove that any tree can be two-colored.
Write an algorithm that determines if an arbitrary undirected graph is a bipartite graph. If the graph is bipartite, then your algorithm should also identify the vertices as to which of the two partitions each belongs to.
Design a format for storing graphs in files. Then implement two functions:one to read a graph from a file and the other to write a graph to a file. Test your functions by implementing a complete MST program that reads an undirected graph in from a file, constructs the MST, and then writes to a
An undirected graph need not explicitly store two separate directed edges to represent a single undirected edge. An alternative would be to store only a single undirected edge (I, J) to connect Vertices I and J. However, what if the user asks for edge (J, I)? We can solve this problem by
While the underlying implementation (whether adjacency matrix or adjacency list) is hidden behind the graph ADT, these two implementations can have an impact on the efficiency of the resulting program. For Dijkstra’s shortest paths algorithm, two different implementations were given in Section
The example implementations for DFS and BFS show calls to functions PreVisit and PostVisit. Better is to implement BFS and DFS using the visitor design pattern, with the visitor functions being passed in as either function or template parameters. Reimplement the BFS and DFS functions to make use of
Write a program to label the connected components for an undirected graph.In other words, all vertices of the first component are given the first component’s label, all vertices of the second component are given the second component’s label, and so on. Your algorithm should work by defining any
For each of the following bracket notation descriptions, draw the equivalent multilist in graphical form such as shown in Figure 12.2. L10 a L2 b c de L3
(a) Show the bracket notation for the list of Figure 12.19(a).(b) Show the bracket notation for the list of Figure 12.19(b).(c) Show the bracket notation for the list of Figure 12.19(c). a (a) 20 D L10 a (b) L1Q L2 a b L3 (c) L4
Given the linked representation of a pure list such aswrite an in-place reversal algorithm to reverse the sublists at all levels including the topmost level. For this example, the result would be a linked representation corresponding to (x1, (y1, y2, (21, 22), y4), (w, w2), 14),
What fraction of the values in a matrix must be zero for the sparse matrix representation of Section 12.2 to be more space efficient than the standard two-dimensional matrix representation when data values require eight bytes, array indices require two bytes, and pointers require four bytes?
Write a function to add an element at a given position to the sparse matrix representation of Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements have a value of zero. One example is the lower triangular matrix that
Write a function to delete an element from a given position in the sparse matrix representation of Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements have a value of zero. One example is the lower triangular matrix
Write a function to transpose a sparse matrix as represented in Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements have a value of zero. One example is the lower triangular matrix that results from solving systems of
Write a function to add two sparse matrices as represented in Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements have a value of zero. One example is the lower triangular matrix that results from solving systems of
Write memory manager allocation and deallocation routines for the situation where all requests and releases follow a last-requested, first-released (stack) order.
Write memory manager allocation and deallocation routines for the situation where all requests and releases follow a last-requested, last-released (queue) order.
Show the result of allocating the following blocks from a memory pool of size 1000 using first fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call this block A), take 500, release A, take 200, take 300.(b) Take 200 (call this block A), take 500,
Show the result of allocating the following blocks from a memory pool of size 1000 using best fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call this block A), take 500, release A, take 200, take 300.(b) Take 200 (call this block A), take 500,
Show the result of allocating the following blocks from a memory pool of size 1000 using worst fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call this block A), take 500, release A, take 200, take 300.(b) Take 200 (call this block A), take 500,
Assume that the memory pool contains three blocks of free storage. Their sizes are 1300, 2000, and 1000. Give examples of storage requests for which(a) First-fit allocation will work, but not best fit or worst fit.(b) Best-fit allocation will work, but not first fit or worst fit.(c) Worst-fit
Implement the sparse matrix representation of Section 12.2. Your implementation should support the following operations on the matrix:• Insert an element at a given position,• Delete an element from a given position,• Return the value of the element at a given position,• Take the
Implement the MemManager ADT shown at the beginning of Section 12.3.Use a separate linked list to implement the freelist. Your implementation should work for any of the three sequential-fit methods: first fit, best fit, and worst fit. Test your system empirically to determine under what conditions
Implement the MemManager ADT shown at the beginning of Section 12.3.Do not use separate memory for the free list, but instead embed the free list into the memory pool as shown in Figure 12.12. Your implementation should work for any of the three sequential-fit methods: first fit, best fit, and
Implement the MemManager ADT shown at the beginning of Section 12.3 using the buddy method of Section 12.3.1. Your system should support requests for blocks of a specified size and release of previously requested blocks.
Implement the Deutsch-Schorr-Waite garbage collection algorithm that is illustrated by Figure 12.18. a a 2 2 C e 5 6 (a) 3 b 3 b 5 (b) C curr 4 4 prev 6
Show the binary trie (as illustrated by Figure 13.1) for the following collection of values: 42, 12, 100, 10, 50, 31, 7, 11, 99. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 0 40 1 0 1 42 1 120
Show the PAT trie (as illustrated by Figure 13.3) for the following collection of values: 42, 12, 100, 10, 50, 31, 7, 11, 99. 000XXXX 2 00XXXXX 2 4 OXXXXXX 1 7 24 4 0 01XXXXX 3 32 37 40 1XXXXXX 120 0101XXX 5 010101x 42
Write the insertion routine for a binary trie as shown in Figure 13.1. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 1 0 0 1 40 42 1 120
Write the deletion routine for a binary trie as shown in Figure 13.1. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 1 0 0 1 40 42 1 120
(a) Show the result (including appropriate rotations) of inserting the value 39 into the AVL tree on the left in Figure 13.4.(b) Show the result (including appropriate rotations) of inserting the value 300 into the AVL tree on the left in Figure 13.4.(c) Show the result (including appropriate
Show the splay tree that results from searching for value 75 in the splay tree of Figure 13.10(d). 17 18 89 (25) (42) 72 (d) (92) (75) 99
Show the splay tree that results from searching for value 18 in the splay tree of Figure 13.10(d). 17 18 89 (25) (42) 72 (d) (92) (75) 99
Some applications do not permit storing two records with duplicate key values.In such a case, an attempt to insert a duplicate-keyed record into a tree structure such as a splay tree should result in a failure on insert. What is the appropriate action to take in a splay tree implementation when the
Show the result of deleting point A from the k-d tree of Figure 13.11. B A E C (a) D LL X y X y B (15, 70) A (40, 45) C (70, 10) (b) D (69, 50) E (66, 85) F (85, 90)
(a) Show the result of building a k-d tree from the following points (inserted in the order given). A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (30, 35), G (55, 40), H (45, 35), I (50, 30).(b) Show the result of deleting point A from the tree you built in part (a).
(a) Show the result of deleting F from the PR quadtree of Figure 13.16.(b) Show the result of deleting records E and F from the PR quadtree of Figure 13.16. 0 127 B A C D E (a) LL 127 A (40,45) C (70, 10) nw ne sw D (69,50) se B (15,70) E F (55,80) (80, 90) (b)
(a) Show the result of building a PR quadtree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (30, 35), G (45, 25), H (45, 30), I (50, 30).(b) Show the result of
On average, how many leaf nodes of a PR quadtree will typically be empty? Explain why.
When performing a region search on a PR quadtree, we need only search those subtrees of an internal node whose corresponding square falls within the query circle. This is most easily computed by comparing the x and y ranges of the query circle against the x and y ranges of the square corresponding
(a) Show the result of building a bintree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (30, 35), G (45, 25), H (45, 30), I (50, 30).(b) Show the result of deleting
Compare the trees constructed for Exercises 12 and 15 in terms of the number of internal nodes, full leaf nodes, empty leaf nodes, and total depths of the two trees.Data from in Exercise 12(a) Show the result of building a PR quadtree from the following points (inserted in the order given). Assume
Show the result of building a point quadtree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (31, 35), G (45, 26), H (44, 30), I (50, 30).
Revise the BST class of Section 5.4 to use the AVL tree rotations. Your new implementation should not modify the original BST class ADT. Compare your AVL tree against an implementation of the standard BST over a wide variety of input data. Under what conditions does the splay tree actually save
Revise the BST class of Section 5.4 to use the splay tree rotations. Your new implementation should not modify the original BST class ADT. Compare your splay tree against an implementation of the standard BST over a wide variety of input data. Under what conditions does the splay tree actually save
Implement a city database using the k-d tree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and y-coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and searched
Implement a city database using the PR quadtree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and y-coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and

Showing 100 - 200 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