Class 34: Discussion of Exam 2

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.
• If you haven't done so already, please read the chapter(s) in Bailey on lists.
• 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

• General grading issues
• 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
  • Start with 0 not 1 (fixed already)
  • 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) = c₁
  • f(n) = c₂ + n + f(n/2)
  • Hence, f(n) is in O(n²)
• Running times of smallest/largest differece
  • You all got it
• Smallest difference.
  • Must be between nearby values.
  • So sort first, which is O(n log₂ 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.