Week 4: Algorithm Analysis applied to Python Lists (and Dictionaries)

Outcomes

• Given a standard Python list function, predict it's Big-Oh notation from your general knowledge of the data structure

  • function	name
    O(1)	constant
    O(log n)	logarithmic
    O(n)	linear
    O(n log n)	log linear
    O(n2)	quadratic
    O(n3)	cubic
    O(2n)	exponential
    O(n!)	factorial

 

Activities

This week I am going to intermingle the readings with the videos. Take the time to pay attention to the proposed structure below:

• Suggested Ordering for this week
• Read Section 2.5 [Textbook]


• Read Section 2.6 down to the second code box where the timeit/Timer code is introduced [Textbook]


• Watch How to read the timeit/Timer code (features a small review of Week 2 and OOP) [Video, 19 minutes]
  • textbook_timeit_code.py [Code]


• Watch Applying the timeit/Timer code to methodOne() from YTI#3 [Video, 6 minutes]
  • demo_timeit_module.py [Code]


• Watch Using the timeit/Timer code to validate the remaining methods/results from YTI#3 [Video, 11 minutes]
  • yti3_with_timeit.py [Code]


• [Optional] Watch Demonstrating the Big-Oh holds even over several different scenarios ("Worst Case" and two versions of "Average Case") [Video, minutes]
  • yti3_timing_demo_cases.py [Code]
  • Note - this is getting down into the weeds a little bit. BUT, it demonstrates some code that validates my claim from last week that code like methodFour() that quits early is STILL O(n) in both the average and worst-case scenarios.


• Watch Reviewing Lists in Python [Video, 9 minutes]


• Watch Considering Lists as a Data Strutucture [Video, 7minutes]


• Read the rest of Section 2.6 [Textbook. Focus on the material about Table 2]


• Watch The Big-oh values of various List operations [Video, 15 minutes]


• [Optional] Reread Section 1.8 about dictionaries [Textbook]


• [Optional] Read Section 2.7 [Textbook]

• Prep for CD#1

Additional Resources

• You may have noticed this on the table of contents page for your textbook. Professor Gerry Jenkins is a retired professor from Long Beach City College who made a bunch of videos to correspond with the readings in your textbook. I have NOT viewed all of them. But, I know how helpful it can be to have a wide variety of study resources.
  • Video 5-7 on this playlist corresponds to material we covered this week.