Day 19
Today
- Analysis of algorithms
- Work on final project “first draft”
For Next time
No reading journal. Prepare for first Architectural Review. Some tips:
- You will have 10-12 minutes for the Architectural Review. Plan your agenda and activities for the session as a team.
- Focus on your key questions, and make sure the audience is capable of addressing them.
- You’ll want to have some visuals (e.g. slides, handouts) to guide the conversation and deliver information, but you should not waste time on a polished slide deck - focus on the content.
- It’s challenging to effectively solicit feedback from a large group of people (hint: simply throwing out a list of questions to the room as a whole wastes time and brain power), so think of some strategies in advance
- Submit framing document to Canvas. Create your feedback form and share link well ahead of class time (so we can collect and share them)
Appendix B Debrief
With the people sitting around you, discuss the following questions:
- What are some of the challenges in comparing the efficiency of two algorithms?
- How does order of growth analysis address these challenges?
- In what situations might order of growth analysis be misleading (or at least tell an incomplete story)?
- 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_linear_operation
and do_constant_operation
. 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_linear_operation
is O(n) (where n is the length of the input list L)do_constant_operation
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_linear_operation(L)
do_constant_operation(L)
def run_computation_2(L):
do_linear_operation(L[0:5])
do_constant_operation(L)
def run_computation_3(L):
for i in range(len(L)):
do_linear_operation(L)
def run_computation_4(L):
for i in range(len(L)):
do_constant_operation(L)
def run_computation_5(L):
if len(L) % 2 == 0:
do_linear_operation(L)
else:
do_constant_operation(L)
def run_computation_6(L):
if len(L) == 1:
return 1
else:
do_constant_operation(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
Here are some exercises to empirically study order of growth of algorithms. Download the Jupyter notebook and run it on your machine.
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.
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. On the other side, some proposals have set the sights a bit low - this is OK too for now, and the teaching team can help you expand your idea in ways that are authentic to your learning goals.
- 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.
Project planning strategies
When undertaking a large project like this one, there are (>=) two schools of thought:
Top-down design
Starting with the big idea, continue to refine the plan and decompose things into smaller pieces with more and more detail until each is small enough to implement.
Bottom-up design
Work on small components of your project organically as needed, then compose them into a larger system at the end.
Each strategy has pros and cons - so which approach is right?
In this class as learners, we recommend that you take a bit of a middle path: do a bit of planning up front (but be willing to change course as you learn more), develop your code bottom up (but don’t forget to pop your head up every once in a while to make sure you’re still going in the right direction).
Final project “first draft”
We want you to finish today with three deliverables. These will form the core of your Architectural Review next time.
If you have not yet created a team GitHub repository, please create one now by accepting the GitHub classroom assignment and adding all team members to the repository. You can/should start by adding a README describing what your project is about (can be short for now), and a Python .gitignore to help keep unintended files out of your repository. Note that this repository will be public from the beginning, unlike your mini project work.
Non-zero amount of code written and committed
This is your “first draft”, and like all first drafts it will be edited later or thrown away entirely. It might look like an extremely minimal version of your main idea, with most functions/classes/etc replaced with stub versions with mock functionality. This is still valuable, since it gives you:
- practice developing code as a team
- an working and test-able baseline to start from no matter how minimal, to help avoid the “we’ll just integrate everything at the last minute” trap
- insight into the major components you’ll need to build your system (even though they’re not written or working yet)
System architecture diagram
Again, first draft. We wouldn’t expect you to have every function and variable specified at this point, and this plan will change, but you should begin to develop a sense of what are the major components that will form your final system. One of the highest skills in software design is developing the ability to break a complex system into reasonable pieces that work together well.
Running list of questions
As you work, you will generate a long list of questions, unknowns, and things to research further as a team. You can select an appropriate subset of these to bring to the audience for your Architectural Review.