# Class 34: Discussion of Exam 2

Back to List Methods. On to Implementing Lists with Arrays.

Held Monday, October 30, 2000

Summary

Today we consider some of the more difficult problems on exam 2.

Notes

• Exam 2 returned.
• Don't forget: Professor Freda Rebelsky visits class tomorrow.
• If we don't get through the exam review today, we may continue into tomorrow.
• Preregistration is soon. I hope many of you will continue on in CS. What are your options?
• CSC341 (if you've taken Combo)
• Combo
• A 2 or 4 credit independent study in database-backed Web sites (details to follow)
• Wait until next fall for 211.

Overview

• Part A
• Part B

• Preparation:
• Algorithm design techniques
• Finding the smallest element of a list
• Binary search without our `Array` class
• Key aspects of recursive functions
• Some general notes:
• Document, document, document ... (e.g., valid field values)
• The role of `this`
• Don't use `new String(...)`
• The `Course` class
• What type should `Course.number` have?
• Building comparators
• What if we want to compare to strings?
• The subarray class, revisited
• Goal: encapsulate the parameters to binary search.
• Solutions
• Fixing binary search
• Tell me what you changed!
• Need to handle empty arrays
• Need to shrink the parameters
• Searching for courses
• No notes
• How much slower is it?
• In each recursive call, we step through O(n) elements.
• f(1) = c1
• f(n) = c2 + n + f(n/2)
• Hence, f(n) is in O(n2)
• Running times of smallest/largest differece
• You all got it
• Smallest difference.
• Must be between nearby values.
• So sort first, which is O(n log2 n)
• Then scan, which is O(n)
• Largest difference.
• Find the smallest value, which is O(n)
• Find the largest value, which is O(n)
• Take their difference.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Monday, 30 October 2000

• Filled in some details, such as they are.

Back to List Methods. On to Implementing Lists with Arrays.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.