MAT2440 – Ganguli – Spring 2022

Discrete Structures & Algorithms

Page 2 of 11

Class #25 – Mon May 9

Agenda/topics:

  • Finish Sec 3.2 / 3.3:
    • review mathematical definitions (and intuitive understanding) of
      • “big-O” notation (upper bound)
      • “big-Ω” (big-Omega) notation (lower bound)
      • “big-Θ” (big-Theta) notation (both upper and lower bound)
      • “Big-O gives an upper bound on the growth of a function, while Big-Omega gives a lower bound. Big-Omega tells us that a function grows at least as fast as another.”
    • look at relevant video lectures/slides from Coursera Algorithms course
    • HW#4 exercises from Sec 3.2 & Sec 3.3

To Do:

  • hand in Quiz #3: take-home quiz re linear search
  • continue working on HW#4! due next Monday (May 16)

Boardshots:

TBA

Class #24 – Wed May 4

Agenda/topics:

  • Continued with Sec 3.2 & 3.3:
    • reviewed Monday’s material re time complexity of linear search, binary search
    • outlined some of the important computational complexity classes:
      • O(log n): logarithmic time
      • O(n): linear time
      • O(n log n): “linearithmic” time
      • O(n^2): quadratic time
      • O(n^m): polynomial time (for m > 0)
      • O(2^n): exponential time
    • introduced mathematical definition of “big-O” notation

To Do:

  • Quiz #3: take-home quiz re linear search – due Monday (pdf available via Files)
  • HW#4: work on Sec 3.1 & 3.2 exercises! Sec 3.3 exercises TBA

Boardshots:

Class #23 – Mon May 2

Agenda/Topics:

  • Begin Sec 3.3:
    • time complexity (running-time of algorithm as function of input size)
    • analyze time complexity of
      • max & linear search: O(n) [linear time]
      • binary search: O(log n) [logarithmic time]
  • Refer to relevant concepts from Sec 3.2 (“The Growth of Functions”)
    • growth of different functions (see Fig 3, p223)
    • “big-O” and “Theta” notation (next time)

To do:

  • continue working on HW#4 (due date TBA)
    • Sec 3.1 exercises listed on Homework page
    • Sec 3.2 & Sec 3.3 exercises TBA

« Older posts Newer posts »