Lesson 0.2: Algorithms

Learning Objectives

Students will be able to…

  • Define algorithm.

  • Construct algorithms for performing simple tasks.

Materials/Preparation

Needed for this lesson:

Pacing Guide

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

Instructor’s Notes

1. 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 Café”.

  • Remote Guidance: Chalk talks could be accomplished remotely using a digital whiteboard tool such as:

  • Remote Guidance: World Café could be accomplished using breakout rooms built into your class meeting tool. If the breakout room feature isn’t available this could be accomplished using multiple live rooms and assigning students into groups.

  • 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).

Remote Instruction Guidance

Here is a great video to introduce Algorithms: https://youtu.be/ZnBF2GeAKbo

2. Activity

  1. Write algorithms

    • 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.

  2. 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.

    • 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:

  3. 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.

  4. 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.

3. 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.

BJC Lecture Suggestions

BJC Video Suggestion: BJC Lecture 6: Algorithm (With Luke Segar

BJC Video Suggestion: BJC Lecture 7: Algorithm Complexity

Background Information for Instructors

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

  • 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 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

Accommodations/Differentiation

  • 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.

Forum discussion

Lesson 0.2 Algorithms (TEALS Discourse account required).