Java Software Structures Designing And Using Data Structures 4th Edition John Lewis, Joe Chase - Solutions

Create a method called depth that will return an int representing the level or depth of the given node from the root.
Develop a pseudocode algorithm to build an expression tree from an infix expression.
Create boolean methods for our BinaryTreeNode class to determine whether the node is a leaf or an internal node.
Develop a pseudocode algorithm to build an expression tree from a prefix expression.
Complete the implementation of the size and isEmpty operations of a binary tree, assuming that there is not a count variable.
Draw either a matrilineage (following your mother's lineage) or a patrilineage (following your father's lineage) diagram for a couple of generations. Develop a pseudocode algorithm for inserting a person into the proper place in the tree.
Complete the implementation of the getRoot and toString operations of a binary tree.
Develop a pseudocode algorithm for a level-order traversal of a binary tree.
What is the time complexity of a radix sort?
Hand trace a radix sort for the following list of five-digit student ID numbers:1322432131543551212322331212123333354312
Draw the UML description of the SortPhoneList example.
Given the resulting sorted list from Exercise 9.4, show a trace of execution for a binary search, searching for the number 235.Exercise 9.4Consider the following list:90 8 7 56 123 235 9 1 653Show a trace of execution for:a. Selection sortb. Insertion
Modify the quick sort method to choose the partition element using the middle-of-three technique described in the chapter. Run this new version against the old version for several sets of data, and compare the total execution times.
Consider the following list:90 8 7 56 123 235 9 1 653Show a trace of execution for:a. Selection sortb. Insertion sortc. Bubble sortd. Quick sorte. Merge sort
Modify the sorts listed in the chapter (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for
Consider the same list from Exercise 9.1. What happens to the number of comparisons for each of the sort algorithms if the list is already sorted?Exercise 9.13, 8, 12, 34, 54, 84, 91, 110.
There is a variation of the bubble sort algorithm called a gap sort that, rather than comparing neighboring elements each time through the list, compares elements that are i positions apart, where i is an integer less than n. For example, the first element would be compared to the (i+1) element,
Using the list from Exercise 9.1, construct a table showing the number of comparisons required to sort that list for each of the sort algorithms (selection sort, insertion sort, bubble sort, quick sort, and merge sort).Exercise 9.13, 8, 12, 34, 54, 84, 91, 110.
The bubble sort algorithm shown in this chapter is less efficient than it could be. If a pass is made through the list without exchanging any elements, this means that the list is sorted and there is no reason to continue. Modify this algorithm so that it will stop as soon as it recognizes that the
Compare and contrast the linearSearch and binarySearch algorithms by searching for the numbers 45 and 54 in the list3, 8, 12, 34, 54, 84, 91, 110.
Determine the order of the recursive maze solution presented in this chapter.
Determine and explain the order of your solution to Exercise 8.4.Exercise 8.4.Fib(0) = 0Fib(1) = 1Fib(j) = Fib(j-1) + Fib(j-2) for j > 1
Produce a chart showing the number of moves required to solve the Towers of Hanoi puzzle using the following numbers of disks: 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, and 25.
Annotate the lines of output of the SolveTowers program in this chapter to show the recursive steps.
Design and implement a graphical version of the Towers of Hanoi puzzle. Allow the user to set the number of disks used in the puzzle. The user should be able to interact with the puzzle in two main ways. The user can move the disks from one peg to another using the mouse, in which case the program
Design a new maze for the MazeSearch program in this chapter, and rerun the program. Explain the processing in terms of your new maze, giving examples of a path that was tried but failed, a path that was never tried, and the ultimate result.
Design and implement a recursive program to determine and print the Nth line of Pascal’s Triangle, as shown below. Each interior value is the sum of the two values above it. Use an array to store the values on each line. 1 1 2 1 3 1 6 4 1 1 1 3 4 1 5 10 10 5 1 6 1 7 1 1 6 15 20 15 1 21 35 35 21 1
Write a recursive method to reverse a string. Explain why you would not normally use recursion to solve this problem.
Design and implement a recursive program to determine whether a string is a valid Blurb as defined in the previous project description.
Write a recursive method that returns the value of N! (N factorial) using the definition given in this chapter. Explain why you would not normally use recursion to solve this problem.
In the language of an alien race, all words take the form of Blurbs. A Blurb is a Whoozit followed by one or more Whatzits. A Whoozit is the character ‘x’ followed by zero or more ‘y’s. A Whatzit is a ‘q’ followed by either a ‘z’ or a ‘d’ followed by a Whoozit. Design and
Modify the method that calculates the sum of the integers between 1 and N shown in this chapter. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2 + 1) to N. Trace your solution using an N of 8.
Design and implement a recursive program that solves the Nonattacking Queens problem. That is, write a program to determine how eight queens can be positioned on an eight-by-eight chessboard so that none of them is in the same row, column, or diagonal as any other queen. There are no other chess
Modify the Maze class so that it prints out the path of the final solution as it is discovered, without storing it.
Write a recursive definition of the Fibonacci numbers, a sequence of integers, each of which is the sum of the previous two numbers. The first two numbers in the sequence are 0 and 1. Explain why you would not normally use recursion to solve this problem.
Design and implement a program that traverses a 3D maze.
Write a recursive definition of i * j (integer multiplication), where i > 0. Define the multiplication process in terms of integer addition. For example, 4 * 7 is equal to 7 added to itself 4 times.
Write a recursive definition of xy (x raised to the power y), where x and y are integers and y > 0.
Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. In a class called DivisorCalc, define a static method
Write a recursive definition of a valid Java identifier.
Write a while loop that uses an explicit iterator to accomplish the same thing as Exercise 7.3.Exercise 7.3.Write a for-each loop that calls the addInterest method on each BankAccount object in a collection called accounts. What is required for that loop to work?
Write a for-each loop that calls the addInterest method on each BankAccount object in a collection called accounts. What is required for that loop to work?
Write a while loop that uses an explicit iterator to accomplish the same thing as Exercise 7.1.Exercise 7.1.Write a for-each loop that prints all elements in a collection of Student objects called role. What is required for that loop to work?
Write a for-each loop that prints all elements in a collection of Student objects called role. What is required for that loop to work?
Modify the Course class from this chapter so that it implements the Comparable interface. Order the courses first by department and then by course number. Then write a program that uses an ordered list to maintain a list of courses.
Create a graphical application that provides a button for addToFront, addToRear, addAfter, and remove from an unordered list. Your application must provide a text field to accept a string as input for any of the add operations. The user should be able to select the element to be added after, and to
Create a graphical application that provides a button for add and remove from an ordered list, a text field to accept a string as input for add, and a text area to display the contents of the list after each operation.
Create an implementation of a doubly linked DoubleOrderedList class. You will need to create a DoubleNode class, a DoubleList class, and a DoubleIterator class.
Write an implementation of the LinkedUnorderedList class.
Write an implementation of the LinkedOrderedList class.
Write an implementation of the LinkedList class.
Complete the implementation of the ArrayUnorderedList class.
Complete the implementation of the ArrayOrderedList class.
Complete the implementation of the ArrayList class.
Implement an OrderedList using an ArrayList object to store the list elements.
If there were not a rear variable in the array implementation, how could you determine whether the list was full?
Implement an OrderedList using a LinkedList object to store the list elements.
Hand trace an unordered list through the following operations.X.addToFront(new Integer(4));X.addToRear(new Integer(7));Object Y = X.first();X.addAfter(new Integer(3), new Integer(4));X.addToFront(new Integer(2));X.addToRear(new Integer(5));Object Y = X.removeLast();Object Y = X.remove(new
Implement the Josephus problem using a queue, and compare the performance of that algorithm to the ArrayList implementation from this chapter.
In the array implementation, under what circumstances could the rear reference equal 0?
Implement a queue using an ArrayList object to store the queue elements.
In the linked implementation, under what circumstances could the head and tail references be equal?
Implement a queue using a LinkedList object to store the queue elements.
What would be the time complexity of the size operation for the linked implementation if there were not a count variable?
Implement a stack using an ArrayList object to store the stack elements.
Given the resulting list X from Exercise 6.1, what would be the result of each of the following?a. X.last();b. z = X.contains(new Integer(3));X.first();c. Y = X.remove(new Integer(2));X.first();
Implement a stack using a LinkedList object to store the stack elements.
Hand trace an ordered list X through the following operations.X.add(new Integer(4));X.add(new Integer(7));Object Y = X.first();X.add(new Integer(3));X.add(new Integer(2));X.add(new Integer(5));Object Y = X.removeLast();Object Y = X.remove(new Integer(7));X.add(new Integer(9));
Create a system to simulate vehicles at an intersection. Assume that there is one lane going in each of four directions, with stoplights facing each direction. Vary the arrival average of vehicles in each direction and the frequency of the light changes to view the “behavior” of the
Suppose the count variable was not used in the CircularArray Queue class. Explain how you could use the values of front and rear to compute the number of elements in the list.
Create a system using a stack and a queue to test whether a given string is a palindrome (that is, whether the characters read the same both forward and backward).
Explain why the array implementation of a stack does not require elements to be shifted, but the noncircular array implementation of a queue does.
Create a graphical application that provides buttons to enqueue and dequeue elements from a queue, a text field to accept a string as input for enqueue, and a text area to display the contents of the queue after each operation.
Name five everyday examples of a queue other than those discussed in this chapter.
Implement the deque from Programming Project 5.6 using links. Each node will need a next reference and a previous reference.Programming project 5.6A data structure called a deque is closely related to a queue. The name deque stands for “double-ended queue.” The difference between the two is
Describe two different ways in which the isEmpty method of the LinkedQueue class could be implemented.
A data structure called a deque is closely related to a queue. The name deque stands for “double-ended queue.” The difference between the two is that with a deque, you can insert, remove, or view from either end of the queue. Implement a deque using arrays.
Compare and contrast the enqueue method of the LinkedQueue class and the push method of the LinkedStack class from Chapter 4.
All of the implementations in this chapter use a count variable to keep track of the number of elements in the queue. Rewrite the circular array implementation without a count variable.
Hand trace the ticket counter problem for 22 customers and 4 cashiers. Graph the total process time for each person. What can you surmise from these results?
All of the implementations in this chapter use a count variable to keep track of the number of elements in the queue. Rewrite the linked implementation without a count variable.
Under what circumstances could the head and tail references for the linked implementation or the front and rear references of the array implementation be equal?
Write a version of the CircularArrayQueue class that grows the list in the direction opposite to the direction in which the version described in this chapter grows the list.
What would be the time complexity of the size operation for each of the implementations if there were not a count variable?
Complete the implementation of the CircularArrayQueue class described in this chapter, including all methods.
Complete the implementation of the LinkedQueue class presented in this chapter. Specifically, complete the implementations of the first, isEmpty, size, and toString methods.
Hand trace a queue X through the following operations:X.enqueue(new Integer(4));X.enqueue(new Integer(1));Object Y = X.dequeue();X.enqueue(new Integer(8));X.enqueue(new Integer(2));X.enqueue(new Integer(5));X.enqueue(new Integer(3));Object Y = X.dequeue();X.enqueue(new Integer(4));X.enqueue(new
Modify the maze problem in this chapter so that it can start from a user defined starting position (other than 0, 0) and search for a user-defined ending point (other than row-1, column-1).
There is a data structure called a drop-out stack that behaves like a stack in every respect except that if the stack size is n, then when the n+1 element is pushed, the first element is lost. Implement a drop-out stack using links.
Draw the UML class diagram for the iterative maze solver example from this chapter.
The linked implementation in this chapter uses a count variable to keep track of the number of elements in the stack. Rewrite the linked implementation without a count variable.
Discuss the impact (and draw an example) of using a sentinel node or dummy node at the head of a list.
Complete the solution to the iterative maze solver so that your solution marks the successful path.
Discuss the effect on all the operations if there were not a count variable in the implementation.
Design and implement an application that reads a sentence from the user and prints the sentence with the characters of each word backward. Use a stack to reverse the characters of each word.
Modify the algorithm from the previous exercise so that it makes use of a rear reference. How does this affect the time complexity of this and the other operations?
Create a simple graphical application that will enable a user to perform push, pop, and peek operations on a stack, and display the resulting stack (using toString) in a text area.
Write an algorithm for the add method that will add at the end of the list instead of at the beginning. What is the time complexity of this algorithm?
Create a new version of the LinkedStack class that makes use of a dummy record at the head of the list.
Draw a UML diagram showing the relationships among the classes involved in the linked-list implementation of a stack.

Showing 100 - 200 of 232

Java Software Structures Designing And Using Data Structures 4th Edition John Lewis, Joe Chase - Solutions

Step by Step Answers