Day 19

Today

• Analysis of algorithms

For Next time

• Reading for next time: Chapter 19 (no reading journal, but be sure to read this chapter. It has some great stuff in it that you’ll want to know about)
• Reflection on the AR is due

Appendix B Debrief

With two folks sitting around you, discuss the following questions:

1. What are some of the challenges in comparing the efficiency of two algorithms?
2. How does order of growth analysis address these challenges?
3. In what situations might order of growth analysis be misleading (or at least tell an incomplete story)?
4. Review your answers to Appendix B Problem 1 (from the reading journal). If there is confusion about one of the answers, take some time to discuss it at your table in more detail (or use the whiteboard). If any questions come up that you’d like to raise with the whole class, there will be some time to do so following your small group discussions.

Practice with Order of Growth

Suppose we are given two python functions do_procedure_f1 and do_procedure_f2. Each function processes a list L in some fashion (what these programs do is unimportant for this exercise). We are told that the order of growth of these procedures is:

• do_procedure_f1 is O(n) (where n is the length of the input list L)
• do_procedure_f2 is O(1) (where n is the length of the input list L)

What are the order of growths of the following computations?

def run_computation_1(L):
    do_procedure_f1(L)
    do_procedure_f2(L)

def run_computation_2(L):
    do_procedure_f1(L[0:5])
    do_procedure_f2(L)

def run_computation_3(L):
    for i in range(len(L)):
        do_procedure_f1(L)

def run_computation_4(L):
    for i in range(len(L)):
        do_procedure_f2(L)

def run_computation_5(L):
    if len(L) % 2 == 0:
        do_procedure_f1(L)
    else:
        do_procedure_f2(L)

def run_computation_6(L):
    if len(L) == 1:
        return 1
    else:
        do_procedure_f2(L)
        run_computation_6(L[0:len(L)/2])

Order of Growth for Basic Python Operations

You have read Think Python Appendix B.1 and B.2. One of the most important takeaways is the listing of the order of growth for various operations on Python data structures. Here are some key points:

• Removing an element from the end of a list is constant time
• Adding an element to the end of the list is constant time (on average)
• Testing if an element is in a list is linear time, O(n)
• Looking up the value stored with a given key in a dictionary is constant time
• Looking up an element stored in a list at a particular location is constant time

Empirical Analysis of Order of Growth

You should have received an invitation to a CoCalc project that Allen created. Next, you’ll be doing some exercises from this notebook.

This is an experiment, so as a backup in case you have issues with CoCalc, the notebook is available as part of the SoftDes website.

A couple of things to keep in mind when interpreting the results graphically:

• A straight line on a log-log plot does not mean the relationship is linear
• The slope of a straight line on a log-log is the exponent of the power relationship
• A slope of 1 on these plots in this notebook implies a constant-time algorithm (doing a constant-time operation to n things takes n time units). A slope of 2 implies a linear-time algorithm.

After you’ve completed the exercise, please help us out by completing this survey about your impressions of the exerience with CoCalc.

Project work time

A few things we’ve observed from several teams, along with some advice to keep in mind at this point in the project:

• scope - Many of the projects you’ve selected have an amazing but (over)ambitious final goal - this is OK. All of the projects we approved also have an achievable, interesting core. It is not a failure to continue to reevaluate project scope as you learn more, the important thing is to keep in contact with the teaching team about it.
• learning goals - Remember to keep your learning goals as a compass as you work on the project, and try not to get too distracted by tangents or perfecting a shiny version of your idea.
• focus - Many projects have several big things going on at once. It’s important at this point to locate the core idea and get a working prototype before adding in every bell and whistle.
• progress over perfection - Don’t wait until you have the perfect data set etc, make progress today.
• teaming and work times - You must find time to make progress outside of class periods and seek help and resources independently. Be direct about confronting teaming and scheduling issues that may arise, don’t bury them. The teaching team is here to help.