CISC220 F2014 Lab5
The Drozdek references below are to the textbook. It shouldn't matter whether you have the 3rd or 4th edition.
The exercises don't make it clear, but "computational complexity" means "big O complexity". Please write your f function (number of instructions, counting assignments only) as well as your g function.
1. Written problems
- (0.75 points) Drozdek exercise 2.11.7 about changing the longest subarray algorithm. Please explain your reasoning.
- Note: There is a typo in the modified outer loop code. "n==i" should read "n - i"
- (0.75 points) Drozdek exercise 2.11.8 about the kth smallest integer
- (2 points) Drozdek exercise 2.11.10 with four loops. Show the steps of your calculations.
- (1.5 points) Depending on the "shape" of the tree, insert() for a binary search tree might be as good as O(log n) (where n is the number of nodes in the tree) or it might be as bad as O(n). Explain in detail what tree characteristics lead to both of these outcomes.
- Make a PDF file <Your Name>_Lab5_README.pdf with your answers to the written exercises
- No need to compress or archive the PDF, since that's all you're turning in.
- Submit it in Sakai by midnight at the end of Thursday, October 9