Discrete Structures & Algorithms

Author: Suman Ganguli (Page 1 of 11)

Office Hours / Final Exam

Just a reminder that we will have our final exam on Monday, during our regular class time.

A handful of people logged on to Blackboard Collaborate for office hours earlier today. I recorded the session, so you can view the recording on Blackboard (go to our Collaborate Ultra page and click on the menu button in the upper left to switch to “Recordings”)

I went over a mathematical induction proof, reviewed some basic algorithms in pseudocode, and outlined what sort of topics/exercises to review for the final:

  • propositional logic e.g., truth table: see Exam #1
  • direct proofs and indirect proofs (i.e., proofs by contraposition): see Quiz #2 and Exam #2
  • set operations and functions (including domain/range, definitions of one-to-one and onto functions): see Exam #2
  • algorithms (writing simple algorithms in pseudocode; executing the basic search and sorting algorithms; big-O estimates of running-times): Exam #3 & Quiz #3
  • proof by mathematical induction: Exam #3 & Sec 5.1

I will post solutions to Exam #3 and Quiz #3, so that you can review the solutions of those.

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)

Class #26 – Wed May 11

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:

« Older posts