2 - 13
# Algorithms: Layers of Abstraction

**Revision Date:** Jul 25, 2015
(Version 1.2)

**Duration:** 1 50-minute session

0b10 - 0b1101

Unit 2. Developing Programming Tools

**Summary**

This is the third session of a three-session lesson sequence with four topics covered by mini-lectures, explorations, and practice exercises.

**Outcomes**

- Students will translate sample pseudocode into a Python function.
- Students will recognize layers of abstraction for solving a Rubik's cube.
- Students will identify sequencing, selection, and iteration elements in a problem solution.

**Overview**

- Getting Started (5 min)
- Activities (40 min)
- Guided Activity 1 [20 min]
- [Optional] Mini-Lecture 1 [20 min]
- [Optional] Guided Activity 2 [20 min]
- Mini-Lecture 2 [20 min]

- Wrap-up (5 min)

- MP1: Make sense of problems and persevere in solving them.
- MP2: Reason abstractly and quantitatively.
- MP7: Look for and make use of structure.

- G-CO.6-8: Understand congruence in terms of rigid motions
- G-GMD.4: Visualize relationships between two-dimensional and three-dimensional objects

- RST 12.3 - Precisely follow a complex multistep procedure
- RST 12.8 - Evaluate the hypotheses, data, analysis, and conclusions in a science or technical text
- WHST 12.4 - Produce clear and coherent writing in which the development, organization, and style are appropriate to task, purpose, and audience

- 2. Developing and using models
- 5. Using mathematics and computational thinking
- 6. Constructing explanations (for science) and designing solutions (engineering)

- HS-ETS1-2. Design a solution to a complex real-world problem by breaking it down into smaller, more manageable problems that can be solved through engineering.

An algorithm is more than just a sequence of steps: levels of abstraction are crucial to the working of algorithms, and sequencing, iteration, and other control structures are ubiquitous.

- How does abstraction help us in writing programs, creating computational artifacts and solving problems?
- How are algorithms implemented and executed on computers and computational devices?
- How do computer programs implement algorithms?

Student computer usage for this lesson is: **optional**

In Lesson Resources folder:

- AlgorithmsPseudocode3.pptx : PowerPoint Slides for mini-lectures
- ConwayDoomsdayAlgorithm : file for "Day of the Week" algorithm, Conway's "Doomsday"

[Optional topic] Wikipedia article on Conway date algorithm.

Access to Youtube videos of people and Lego Robots solving Rubik's cubes.

Videos:

- CUBESTORMER 3 Smashes Rubik's Cube Speed Record by ARMflix

https://www.youtube.com/watch?v=X0pFZG7j5cE and /or

- CUBESTORMER 2 by ARMflix

https://www.youtube.com/watch?v=_d0LfkIut2M

- Human World Record: Kopie Van Mats Valk Official Rubik's Cube Single 5:55 by Mats Valk

https://www.youtube.com/watch?v=vhTMm85G9GE

One or more Rubik's cubes.

Links to PDF copies of youcandothecube's solution to Rubik's cube (also copied into the Lesson Resources folder):

You Can Do the Rubik's Cube

**Daily Homework Review**

- Review of pseudocode for determining if a year is a Leap Year

- Guided Activity 1
- Demonstrate Python function implementation for the "Is it a Leap Year" pseudocode.

- [Optional] Mini-lecture 1
- Teach Conway "Day of the Week" algorithm. Use the file called ConwayDoosmdayAlgorithm in the Lesson Resources folder.

- [Optional] Guided Activity 2
- Have students practice the Conway algorithm.

- Mini-lecture 2
- Walk through “Extended Example (Rubik's Cube) slides with associated videos; web links; and "props” (actual cubes or website:
- Coolmath-Games.com Rubik's Cube Game http://www.coolmath-games.com/0-rubikscube/ or
- Google's Rubik's Cube Game https://www.google.com/logos/2014/rubiks/rubiks.html );

- Walk through “Extended Example (Rubik's Cube) slides with associated videos; web links; and "props” (actual cubes or website:

- Review Table of Contents of selected Algorithms book.
- Review summary slide.
**Homework:**Take one of the youcandothecube.com solution stages. Identify the sequencing, selection, and iteration elements. Sketch a flowchart of that stage of the solution.

For the optional activity (Conway Algorithm), some students may have difficulty adding and subtracting dates to translate from a known day-of-the-week to another day in the same month. A chart on the wall, or a current calendar, could be a help.

Some students who are strong in other areas will have difficulty with the spatial aspects of manipulating a cube while retaining an orientation that will let them complete the steps of one of the sub-algorithms without errors. They may need to be paired with another student or the instructor until they master the technique of holding the cube fixed while rotating a face.

The notation of face turning (e.g. R versus R' or L versus L') can be confusing. Having the students practice with an empty jar with a lid can help. Orient the lid up (U), down (D), left (L), right (R), front (F), or back (B). The hand movement to screw the lid on is the same hand movement needed to perform the non-accented face turn. The hand movement needed to screw the lid off is the same as the accented turn (U', D', L', R', F', B').

Variation for class that does not have Rubik's cubes: Use the images from the Solution Guide: www.youcandothecube.com.

Online rubik's cube solver:

- Coolmath-Games.com Rubik's Cube Game http://www.coolmath-games.com/0-rubikscube/ or
- Google's Rubik's Cube Game https://www.google.com/logos/2014/rubiks/rubiks.html

The following "Checks for Understanding" could be used to guide the students towards the three learning objectives.

Objective: SWBAT translate sample pseudocode into a Python function.

- Word Sort. Students will evaluate isolated Python constructs as matching sequencing, selection, or iteration elements.
- Timed Pair Share. Pairs of students will translate the challange examples from pseudocode into Python.
- Project Study Group. Looking at pseudocode and non-working Python code: What is wrong? What is missing? How would you change it?

Objective: SWBAT recognize layers of abstraction for solving a Rubik's cube.

- Describe it. Students will first study and then will identify characteristics of Rubik's cubes (number of sides; possible movements; number and types of pieces -- center, edge, corner; ...)
- Predict and share -- students will predict strategies for solving the cube.
- Put in order -- groups of students will take a set of partially solved cubes and place them in "solution order". They will justify their choice. [Note: images from www.youcandothecube.com can be used if real cubes are not available.]
- Learn one layer. Every student will learn how to execute one full step of the solution sequence.

SWBAT to identify sequencing, selection, and iteration elements in a problem solution.

- Students will identify the sequencing, selection, and iteration steps of: their homework algorithm; two of the sample problems from the challenge set; and one of the stages of the Rubric cube solution. These will be done in pairs and small groups.

Students will translate prior pseudocode into Python routines. They will recognize if their programs work correctly.

Students will deconstruct one of the Rubik's cube solution stages. These analysis results will be shared and critiqued.