Students will be able to...
- Define "algorithm"
- Construct algorithms for performing simple tasks
Needed for this lesson:
- Supplies to create a peanut butter & jelly sandwich (ingredients, utensils, plates, napkins, etc.)
- Paper/writing implements for each group of students
- Large poster paper and markers will allow for display of the algorithms, but standard paper will work fine
- Unit 0 Tips
| 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 |
-
Introductory discussion
- 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 Cafe"
- 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).
- Invite discussion about what constitutes a computer, what computers do, and what computer science is.
-
Activity
- Write algorithms
- In pairs or small groups, students will attempt to develop an algorithm for preparing a peanut butter and jelly sandwich. 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. OR ask students to develop a 10 step algorithm to teach a computer to brush their teeth.
- 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."
- Algorithm execution
- 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.
- 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
- Failing to open a container before using what is inside
- Most algorithms will fail. If there is time, repeat the process with one or two other groups.
- Debugging algorithms
- 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.
- Execute debugged algorithm
- 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.
- Many algorithms will still have similar problems to the first iteration. Others will have too much detail (see below) or other, subtler problems (such as skipping trivial steps like putting the two slices of bread together). Try to take note of issues while circulating so you can address them quickly.
- Write algorithms
-
Debrief
- 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.
- 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.
- BJC Video Suggestion: BJC Lecture 6: Algorithm (With Luke Segar
- Algorithm Definition 3:20-4:20
- Early Algorithms 4:25-5:55
- Familiar Algorithms 6:00-7:30
- BJC Video Suggestion: BJC Lecture 7: Algorithm Complexity
- Algorithm Analysis: The Basics 6:00-7:40
- Algorithm Analysis: Running Time 7:41-8:25
- BJC Video Suggestion: 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 Good for Classroom Instruction
- Early Algorithms 4:25-5:55 Good for Classroom Instruction
- Familiar Algorithms 6:00-7:30 Good for Classroom Instruction
- 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 Video Suggestion: 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** Good for Classroom Instruction 6:00-7:40***
- Algorithm Analysis: Running Time** Good for Classroom Instruction 7:41-8:25**
- Algorithm Analysis: Runtime Analysis Problem and Solution 8:25-9:55
- Runtime Analysis: Input Size and Efficiency 9:58-11:25
- Runtime Analysis: Worst of Avg Case 11:25-13:20
- Run Time: Final Assessment 13:20-16:46
- Example:Finding a student by ID (detailed explanation of input/output) 17:00-31:20
- Ex: Finding a shared birthday (Constant, Logarithmic, Linear, Quadratic, Exponential) 31:21-33:30
- Ex: Finding Subsets 33:40 to End
- 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.
- This can lead to an excellent conversation about abstraction.
- 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.
- If you feel students can handle the discussion, you can draw a parallel to machine code here.