CISC220 F2014 Lab5

Lab #2

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.

2. Submission

• 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