- Be able to explain why we care about the algorithmic complexity of our programs on a practical level
- Be able to explain why we analyze algorithms in terms of asymptotic and worst-case performance
- Explore the performance characteristics of some common algorithms/operations
- Cut/banded number cards like 1-27
- Post-It notes of 1-27 for instructor board demos
Post on the board before class:
- https://www.youtube.com/watch?v=XaqR3G_NVoo on the TV
- Pairings for sitting / Part 1
- Write your answer in your notebook: why does the speed of software matter?
- Distribute the number cards
- Recap: why speed matters -- fast software makes people happy, slow software makes people sad, happy people pay money, developers like having jobs
Together, illustrate the steps of a bubble sort on the board:
- Post six random post-it numbers
- Eval left to right
- Maintain a current and previous
- Follow this algorithm:
1. Start with previous at element-0, current at element-1
2. If current is > previous
* Move previous = current, current = current + 1
* If current = nil, you're done!
* Else, go to Step 2
3. Else (current < previous)
* Swap current and previous in the set
* Return to Step 2
- Person on the right is the RECORDER, person on the left is the WORKER
- RECORDER should select six random number cards, shuffle them, hand them to the WORKER
- WORKER lays out the cards in their current order left to right
- RECORDER is going to track how many "operations" it takes to sort the numbers fully
- Make a tally for each comparison (a >?< b) and each swap
- WORKER executes the bubble sort algorithm talking out loud
- RECORDER notes the total number of operations
Group questions:
- How many operations did it take? (lots of different answers)
- What does this tell you about bubble sort? (nothing)
- RECORDER shuffles the same six cards
- Repeat the process and get the new operation count
Group questions:
- How did the count of operations differ from your first run? (lots of different answers)
- What does this tell you about bubble sort? (still nothing)
- Tell the RECORDER to select four cards from the six at random and put them in the worst-possible order for this algorithm
- WORKER should sort them while RECORDER counts
- RECORDER adds in one more card and puts them back in the worst order
- WORKER should sort them while RECORDER counts
- RECORDER adds in sixth card and puts them back in the worst order
- WORKER should sort them while RECORDER counts
Pair Questions:
- How did the operation count grow from 4 to 5 to 6 cards?
- What would you guess about how many operations 7 cards would take? 10?
- What does this tell you about bubble sort?
break and set up for station activity
- Post the sequences for each pair on the board
- Lay out three stations with the sort documents below
- Each station they have ~12 minutes to complete the exercises, then rotate
break
Cover the following key points in a whole-group lecture with questions:
- Big-O is how we refer to the algorithmic complexity
- The important part of complexity is how it scales with the number of inputs
- If we only have a dozen or few hundred inputs, complexity usually doesn't matter
- But what about thousands or millions?
- Draw the graph of complexity with a logarithmic Y axis
- Include O(1), O(log(n)), O(n), O(nlog(n)), O^2, O^3 like https://cdn-images-1.medium.com/max/800/1*_nsMVEEkIr1CH8aHjTNbzA.jpeg
- If your data set is finite or your users don't matter, then who cares?
- Ex: building a reporting system that runs once a week and could be scheduled for 2AM on Friday morning. If it takes 30 minutes or 3 minutes is irrelevant
- If your data set grows, especially if it grows n^2 as your number of users increases, then you could be in trouble
- Ex: imagine you're building discussion software or Reddit. As the number of users increases and number of forums increases you get a spiraling quantity of content. Imagine you're pulling the "top 10 threads of the hour" page -- complexity will matter.
- In your web application, your "operation" is probably a SQL query or API call
- If you have 1, 2, or a fixed number, you're probably OK
- But if you have N calls for N pieces of data, or 2N, or N^2, you're in trouble
- Consider: N+1 example like that a news site that lists the top articles on the front page and does a follow up query for each article to get the number of comments
With five minutes left, get into these key understandings:
- There's often more than one way to solve a problem
- Everything in software is a collection of tradeoffs
- You might consider...
- Difficulty of implementation
- What do you already know about the data?
- Can you cut/limit the size of inputs?
- Best-case run time? Worse-case run time?
- How will the run time change with an increase of N?
Prep: Seed a binary tree near the door with six random but balanced nodes
- Grab 6 of your numbers at random and shuffle them
- Insert them into the Binary Tree on the table near the door
- Notice how the tree is or isn't balanced