Class #28 – Mon May 18

[Sorry for the delay in posting this class update]

Topics:

• reviewed HW#4 exercises from Sec 3.2 & 3.3:
  • Sec 3.2: shortcuts to figuring out big-O estimates for given functions (in particular polynomials, and functions that “look like” polynomials)
  • Sec 3.3: shortcuts to figuring out big-O estimates for given algorithms (in particular based on loops and nested loops)
• introduced Sec 5.1: Mathematical Induction
  • framework for a proof by induction: used to to prove a statement P(n) is true for all positive integers n, consists of two steps:
    • “base case” (usually P(1), i.e, show the statement holds for n = 1)
    • “induction step”: show that “P(k) implies P(k+1)” (for an arbitrary positive integer k)
  • sketched proof of “1 + 2 + 3 + … + n = n(n+1)/2”
    • see slides and/or Example 1 in Sec 5.1
• handed out Exam #3 (take-home due Thursday) – pdf also available via OpenLab Files

Schedule for remainder of semester:

• Wed May 18: finish mathematical induction; address Exam #3 questions; review for final exam
• Thurs May 19: Exam #3 due (either submit hard copy to math dept office (N711) or submit pdf via Blackboard)
• Fri May 20: Office hours (via Blackboard Collaborate) for final exam review and Exam #1/#2 corrections: 12-2p
• Mon May 23: Final exam, 12p-1:40p (& Exam #1/#2 corrections due)