Students will be able to...
- Define algorithm.
- Construct algorithms for performing simple tasks.
- 0.2 slide deck
- Unit 0 tips
- Sandwich ingredients: Bread, peanut butter, jelly, utensils, plates, napkins
- Large poster paper and markers
- https://youtu.be/ZnBF2GeAKbo
- Video quiz - See additional curriculum materials accessed from the TEALS dashboard.
- CodeScty algorithm music video
- CodeScty algorithm dance challenge
| Duration | Description |
|---|---|
| 5 minutes | Welcome, attendance, bell work, announcements |
| 10 minutes | Introductory discussion; present activity |
| 10 minutes | Students write first algorithms |
| 5 minutes | Sample algorithm execution |
| 10 minutes | Students debug/rewrite algorithms |
| 5 minutes | Second sample algorithm execution |
| 10 minutes | Debrief and wrap-up |
Show this video to activate disucssion: https://youtu.be/ZnBF2GeAKbo
- Invite discussion about what constitutes a computer, what computers do, and what computer science is.
- An excellent protocol for these types of discussions is "Chalk Talk" or "World Café".
- Develop definitions for important terms ("computer," "computer science," "algorithm," "program," "programming language").
- Display each term on the board or projector and ask students to provide key ideas or concepts they know that relate to the term. From this, you can develop a classroom definition. Feel free to have a pre-written definition and guide students to that definition using leading questions.
- You can introduce the idea that the first computers were human (a person who makes calculations, especially with a calculating machine) with the story about Katherine Johnson whose calculations were used for manned and unmanned orbital missions (read more here).
In pairs or small groups, students will attempt to develop an algorithm to teach a robot to brush their teeth, or to prepare a peanut butter and jelly sandwich (check for food allergies before performing this exercise). Specify to students that their algorithm must be complete and detailed enough for a "computer" (the teacher) to unambiguously follow the steps and achieve the desired result.
- Give little guidance at this stage, as the confusion (and the errors that are likely to result) will both reinforce the importance of specificity and detail as well as provide entertainment value later on.
- Algorithms should be written on paper to be shared and reviewed. Students should not be writing any code, nor should they develop algorithms "in their heads."
Remote Learning Guidance - This activity could be done using a shared document and then links could be shared. Consider pairing students in advance or building in a procedure on how students will pair up moving forward in the semester.
After groups have finished, choose a group and have them read their instructions. Act as a computer and follow each step as literally as possible. If there is ambiguity, or if a step is not possible to complete, point out the error.
When an instruction is ambiguous or impossible, interpret the algorithm in the most atypical (and hilarious) way possible. This will reinforce to students that many seemingly clear instructions can be taken many ways.
For the PBJ activity, common errors will include:
- Failing to open a container before using what is inside.
- Response: Try (and fail) to access the inside in a humorous fashion (e.g. try to reach through the bag or jar, acting confused as to why you cannot reach the ingredient inside).
- Failing to specify in which orientation or position to use something (e.g. "grab the knife" but not by the handle, "put down the bread" but not on the plate).
- Response: use or place the ingredient in an obviously (and humorously) incorrect way (e.g. grab the knife (carefully) by the sharp end, put the slice of bread on the table next to plate, spread peanut butter around the crust instead of on the face).
- Using instructions that are too broad (e.g. "pick up the bread" to mean a single slice, "put the peanut butter on the bread" to mean spreading a small amount).
- Response: Ask for more detail, or interpret the instruction literally.
- Combining multiple steps into one instruction (e.g. "spread peanut butter on the bread" without specifically opening the jar, putting peanut butter on the knife, using the knife to spread, etc.)
- Response: Ask for more detail.
Most algorithms will fail. If there is time, repeat the process with one or two other groups.
-
Here is an example video of the PBJ activity:
<iframe class="markdeep" width="400" height="315" src="https://www.youtube.com/embed/FN2RM-CHkuI" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
Spend a brief moment explaining that programming is an iterative process, and that errors are expected. Introduce the concept of "debugging." Then, have students "debug" their algorithms and attempt to fix all errors and ambiguities.
- Changes should be made on paper. Consider introducing a standard notation for edits (strike-through for deletion, carat (^) for insertion, circle for modify, etc.) to make changes easy to spot.
- If possible, have students make changes using a different color marker or pen.
While students are working, circulate and look for a promising algorithm. The goal is to have a successful algorithm at the end of the class.
Once groups have finished debugging, repeat the execution process. Hopefully, at this point, at least one algorithm will result in a proper sandwich.
- If no successful algorithm is found, try to debug on the fly. When you hear an incorrect or unclear instruction, point out the error and either propose or request a fix before proceeding. The goal is to create a sandwich before the end of class.
Take note of issues while circulating through the class so you can address them quickly.
Ask students to describe why there were problems with the first round of algorithms, and how those problems were fixed. Encourage the use of computer science terminology.
- Keep students from fixating on the specifics of any one error and guide discussion to the general approaches and concepts used to resolve problems. Have students discuss what lessons can be learned from this activity and how they can be applied to programming and computer science.
Check for food allergies before performing this exercise. If any student has allergies that would put them at risk, substitute another food item or simulate the process with stand-in ingredients. The most common allergy will be to peanuts. Possible alternatives in this case include cream cheese & jelly, toast with butter and jam, or even a deli sandwich (turkey/ham/roast beef) with mayo and/or mustard.
- For other allergies, or if no options are acceptable, simulate using fake ingredients. (Even slips of paper with the ingredients written on them can suffice.)
Students who have previous programming experience may tend to dominate the algorithm generation process. Encourage these students to avoid pointing out errors directly and help the other members of their group find and fix errors. If students are struggling with the level of specificity required, allow them to make some basic assumptions to ease the process. In the "debugging" round, some students may go overboard with the level of detail in an attempt to resolve all possible ambiguities. Remind these students that there are some basic instructions that can be easily understood by most people, and there is no need to go into further detail in those cases.
BJC Lecture 6: Algorithm (With Luke Segar)
- Computer Worms 0:00-1:30
- Algorithm Concept Intro: Rubic Cube Competition 1:40-2:40
- Algorithm Definition 3:20-4:20
- Early Algorithms 4:25-5:55
- Familiar Algorithms 6:00-7:30
- Commonly Used Algorithms (Page Rank, etc.) 8:00-10:45
- Choosing an Algorithm Technique 10:50-12:15
- Ways to Tackle Problems (Brute Force, Top Down, Bottom Up) 12:20-15:30
- Algorithms vs Functions and Procedures 15:30-16:00
- Turing Completeness (Computer Theory-BYOB is Turing Complete) 16:05-21:15
- Algorithm Correctness 21:25-26:00
- Algorithm Summary 26:00-end
BJC Lecture 7: Algorithm Complexity
- Yahoo predicts America’s political winner 0:00-1:25
- Function abstraction (Explanation of Functions and Algorithms) 1:28-2:45
- What is IN a Spec 2:45-3:30
- What is NOT in a Spec 3:30-5:15
- Reference Text “Introduction to Algorithms” 5:18
- Algorithm Analysis: The Basics
- Algorithm Analysis: Running Time