Category: Class Agendas (Page 2 of 9)

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:

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