Author: Suman Ganguli (Page 1 of 11)

[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)

Topics:

• Review insertion sort algorithm (Sec 3.1), look at its time complexity (Sec 3.3: O(n^2))
• HW#4 exercises from Sec 3.1 & 3.2:
  • Sec 3.1, #42 (insertion sort)
  • Sec 3.2, #5 & 23 (showing “big-O” relationships using graphs)

Schedule for remainder of semester:

• Thurs May 12 & Fri May 13: Office hours (via Blackboard Collaborate) for questions re HW#4
  • Thurs: 10a-11a
  • Fri: 12p-2p
• Mon May 16: HW#4 due; hand out Exam #3 (take-home)
• Wed May 18: Exam #3 due
• Thurs May 19 & Fri May 20: Office hours (via Blackboard Collaborate) for final exam review (times TBA)
• Mon May 23: Final exam

Boardshots: