Review Questions
1. When does quicksort work best, and when does it work worst?
2. Write a recursive procedure to implement the insertion sort algorithm.
3. What is the purpose of the pivot value in quicksort? How did we first select it in the text, and what is wrong with that approach for choosing a pivot value?
4. For the following array
30 40 20 15 60 80 7S 4 20
show the new array after each pass of insertion sort, bubble sort, and selection sort. How many comparisons and exchanges are performed by each?
5. For the array in Question 4, trace the execution of Shell sort.
Review Questions
1. Draw the mirror images of the three cases for insertion into a Red-Black tree and explain how each situation is resolved.
2. Show the AVL tree that would be formed by inserting the month names (12 strings) into a tree in their normal calendar sequence.
3. Show the Red-Black tree that would be formed by inserting the month names into a tree in their normal calendar sequence.
4. Show the 2-3 tree that would be formed by inserting the month names into a tree in their normal calendar sequence.
5. Show the 2-34 wee that would be formed by inserting the month names into a tree in their normal calendar sequence.
Review Questions
1. Draw the mirror images of the three cases for insertion into a Red-Black tree and explain how each situation is resolved.
2. Show the AVL tree that would be formed by inserting the month names (12 strings) into a tree in their normal calendar sequence.
3. Show the Red-Black tree that would be formed by inserting the month names into a tree in their normal calendar sequence.
4. Show the 2-3 tree that would be formed by inserting the month names into a tree in their normal calendar sequence.
5. Show the 2-34 wee that would be formed by inserting the month names into a tree in their normal calendar sequence.
Programming Projects
1. Use the random number function to store a list of 1000 pseudorandom integer values in an array. Apply each of the sort classes described in this chapter to the array and deter¬mine the number of comparisons and exchanges. Make sure the same array is passed to each sort method.
2. Investigate the effect of array size and initial element order on the number of compar¬isons and exchanges required by each of the sorting algorithms described in this chapter. Use arrays with 100 and 10,000 integers. Use three initial orderings of each array (randomly ordered, inversely ordered, and ordered). Be certain to son the same six arrays with each sort method.
Programming Projects
1. Complete the AVLTree class by coding the missing methods for insertion only. Use it to insert a collection of randomly generated numbers. Insert the same numbers in a binary search tree that is not balanced. Verify that each tree is correct by performing an inorder traversal. Also, display the format of each tree that was built and compare their heights.
2. Code the RedBlackTrec class by coding the missing methods for insertion. Redo Project 1 using this class instead of the AVLTree class.
Programming Projects
1. Design and implement the Matri xGraph class.
2. Rewrite method di j kstrasAl gori thm to use a priority queue as we did for method prinsAlgori thm. When inserting edges into the priority queue, the weight is replaced by the total distance from the source vertex to the destination vertex. The source vertex, however, remains unchanged as it is the predecessor in the shortest path.