2.3. Algorithm Basics

This lesson focuses on the concepts of algorithms and programming, which is one of the course's big ideas. As one of the many lessons in the course on algorithms, it begins by providing a definition and introducing some of the fundamental building blocks that are used to construct algorithms. They will use the three fundamental constructs for building algorithms: sequence, a sequence of statements; selection, a branching between two alternative statements; and repetition, a loop that repeats statements. Students will evaluate and write algorithms using pseudocode, which is part of the AP Exam, and make connections to App Inventor. This lesson reinforces the enduring understanding that algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages. Also, in this lesson students will complete a group work activity using the POGIL structure. (POGIL stands for Process-Oriented Guided Inquiry Learning; more information is provided in the background knowledge and teaching tips sections below and in the pedagogy lesson in Unit 10.) 

CSP Framework
Big Idea 3: Algorithms and Programming (AAP)
Enduring Understanding AAP-2: The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.A: Express an algorithm that uses sequencing without using a programming language.
Skill 2.A AAP-2.A.3 Essential Knowledge AAP-2.A.3: Algorithms executed by programs are implemented using programming languages.
Learning Objective AAP-2.B: Represent a step-by-step algorithmic process using sequential code statements.
Skill 2.B AAP-2.B.1 AAP-2.B.6 Essential Knowledge AAP-2.B.1: Sequencing is the application of each step of an algorithm in the order in which the code statements are given. Essential Knowledge AAP-2.B.6: Sequential statements execute in the order they appear in the code segment.
Learning Objective AAP-2.E.a: For relationships between two variables, expressions, or values: a. Write expressions using relational operators. Learning Objective AAP-2.E.b: For relationships between two variables, expressions, or values: b. Evaluate expressions that use relational operators.
Skill 4.B AAP-2.E.1 Essential Knowledge AAP-2.E.1: A Boolean value is either true or false.
Learning Objective AAP-2.G: Express an algorithm that uses selection without using a programming language.
Skill 2.A AAP-2.G.1 Essential Knowledge AAP-2.G.1: Selection determines which parts of an algorithm are executed based on a condition being true or false.
Learning Objective AAP-2.H.a: For selection: a. Write conditional statements. Learning Objective AAP-2.H.b: For selection: b. Determine the result of conditional statements.
Skill 4.B AAP-2.H.1 Essential Knowledge AAP-2.H.1: Conditional statements or if-statements affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
Learning Objective AAP-2.J: Express an algorithm that uses iteration without using a programming language.
Skill 2.A AAP-2.J.1 Essential Knowledge AAP-2.J.1: Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.
Learning Objective AAP-2.K.a: For iteration: a. Write iteration statements. Learning Objective AAP-2.K.b: For iteration: b. Determine the result or side-effect of iteration statements.
Skill 4.B AAP-2.K.1 Essential Knowledge AAP-2.K.1: Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.
Learning Objective AAP-2.M.a: For algorithms: a. Create algorithms. Learning Objective AAP-2.M.b: For algorithms: b. Combine and modify existing algorithms.
Skill 2.B AAP-2.M.1 AAP-2.M.2 AAP-2.M.3 Essential Knowledge AAP-2.M.1: Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms. Essential Knowledge AAP-2.M.2: Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include: -determining the maximum or minimum value of 2 or more numbers - computing the sum or average of 2 or more numbers - identifying if an integer is or is not evenly divisible by another integer - determining a robot’s path through a maze Essential Knowledge AAP-2.M.3: Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.

Professional Development

The Student Lesson: Complete the activities for Mobile CSP Unit 2 Lesson 2.3: Algorithm Basics.

Materials

• Projection System
• Slides
• POGIL role cards
• Worksheet for POGIL Activity

2.3.1. Learning Activities

Estimated Length: 45 minutes

• Hook/Motivation (5 minutes): Ask the students to define what an algorithm is. Explanation: Provide the definition of an algorithm: An algorithm is a sequence of precise instructions, a step-by-step procedure, that solves some problem or does some computation. Next, review the Blockly Maze activity as needed, emphasizing that there are multiple solutions to the problems, but that some may be more efficient than others as well as reinforcing the concepts of sequence, selection and repetition types of control structures.
• Experiences and Explorations (30 minutes):
  • Lecture (10 minutes): Use the slide presentation to provide an overview of algorithms to the students
  • POGIL Roles and Teams (5 minutes): Divide students into groups of 3-4 teams. Review the POGIL structure and roles with the students, having groups assign each member a role. Since this is the first time using the POGIL format, you might find it useful to distribute the POGIL role cards to the groups. Be sure to emphasize that POGIL has been shown to help students learn the concepts better and that most students prefer this format. 
  • POGIL Activity (15 minutes) In the POGIL teams, students should work through the critical thinking questions. Make sure that they identify the complete repetition and selection structures, not just the first line of each. The answers to the POGIL questions are in the Assessment section below. Look ahead at the answers to anticipate questions you may be asked.
• Rethink, Reflect and/or Revise (10 minutes): Have the students complete the interactive questions and their portfolio reflection.

AP Classroom

The College Board's AP Classroom provides a question bank and Topic Questions. You may create a formative assessment quiz in AP Classroom, assign the quiz (a set of questions), and then review the results in class to identify and address any student misunderstandings.The following are suggested topic questions that you could assign once students have completed this lesson.

Suggested Topic Questions:

• Topic 3.6 Conditionals

Assessment Opportunities and Solutions

Solutions Note: Solutions are only available to verified educators who have joined the Teaching Mobile CSP Google group/forum in Unit 1.

• Quizly Solutions
• Portfolio Reflection Questions Solutions

The POGIL exercise solutions are below:

1. CAN_MOVE(forward) is true. CAN_MOVE(right) is false.

2.   MOVE_FORWARD
     MOVE_FORWARD
     ROTATE_RIGHT
     MOVE_FORWARD
     MOVE_FORWARD
     MOVE_FORWARD
     MOVE_FORWARD
     ROTATE_LEFT
     MOVE_FORWARD
     MOVE_FORWARD

3. REPEAT 2 TIMES
     {
       MOVE_FORWARD
     }
     ROTATE_RIGHT
     REPEAT 4 TIMES
     {
       MOVE_FORWARD
     }
     ROTATE_LEFT
     REPEAT 2 TIMES
     {
       MOVE_FORWARD
     }
   
              

4. • Example of Selection:IF CAN_MOVE forward MOVE_FORWARD;
   • Example of Repetition:

     REPEAT UNTIL GoalReached
       IF CAN_MOVE forward
         MOVE_FORWARD
       IF CAN_MOVE left
          ROTATE_LEFT
       IF CAN_MOVE right
          ROTATE_RIGHT

   • Most students will say the algorithm works for this maze in 10 iterations since there are 10 commands needed. However, you should point out in class discussion that the loop body actually runs for 8 iterations, because sometimes you can do 2 commands inside the loop if you can move forward and then rotate_right or left. After the first if statement is finished, we sequentially move down to the next if statement, and it can be executed right away if it is true. So, the 2 turns are done right after a move_forward in the same iteration of the loop. You could even say that the loop condition at the top runs for the 9th and final time to exit the loop.
   • The algorithm will get stuck in mazes where there is a dead end and the robot needs to turn back to find another way. The robot will not be able to turn back, because to rotate, the space to its right or left needs to be available.

5.            REPEAT 10 times
                IF cup
                   hot_wash
                IF dish
                   cold_wash
                 

Differentiation: More Practice

Have students be the robot themselves, putting squares of paper on the floor to represent the maze. One student can read off the algorithm while another student "executes" the commands by walking through the maze. Alternatively, a student could walk the maze and then write the algorithm from it.

Here are some additional resources if students are struggling with lesson concepts:

• Algorithms: Have them complete more of the Blockly Maze activities, asking them to identify which mazes they use sequence, selection, and repetition concepts.
• Pseudocode: Show students the AP Exam Reference Sheet as it has some common pseudocode commands that they can use to help write their own pseudocode. (Students can access it directly in Lesson 8.2.).
• Pseudocode: pHave students try ractice questions on Khan Academy.
• Guess your birthday (day and month) using math calculations. Have students watch this birthday calculation video and have them practice writing the algorithm. Students can swap algorithms with a classmate to see if their algorithm is correct and works to calculate their birthday.

Differentiation: Enrichment

One idea is to have the students write an algorithm for opening a locker with a combination lock. Another idea is to have the students write an algorithm, in pseudocode, for how they eat lunch. See Betsy Dillard's example assignment. Ask students to compare different algorithms. Is an algorithm that takes fewer steps better? more efficient? Is there a difference in difference in clarity between two algorithms? This should be a brief introduction. Students do not need to understand this yet. But, they should start thinking about it. Efficiency and clarity will be taught in the Analyzing Algorithms lesson. If using the base conversion example, you could discuss the questions above in terms of base conversion algorithms. You could also have students compare the algorithms they wrote in class.

Background Knowledge: More on Algorithms

• Iteration and repetition both refer to loop structures in programming.
• Wikipedia has a nice explanation on Algorithms and Pseudocode.
• Computer Science Fact: It has been proven that sequence, selection, and repetition are the only control structures needed to build any algorithm that can be thought of. In other words, any algorithm can be expressed using only sequence, selection, and repetition. So, the students have already been introduced to all of the algorithm building tools they would need to solve any computing problem that can be solved. (This is not to say every computing problem can be solved -- that's another story.)

Background Knowledge: POGIL

POGIL, Process Oriented Guided Inquiry Learning, as used in Mobile CSP, is a structured cooperative learning approach where students work in teams of 3-4 students to solve problems. Research suggests that the POGIL approach helps students master the content more effectively and that most students prefer to learn in POGIL teams over more traditional approaches. This video provides an overview of POGIL. Learn more about the POGIL Project and POGIL being used in computer science courses.

Teaching Tip: Algorithm Vocabulary

In this lesson and future lessons, make sure that you revisit the terms sequence, selection, and repetition, especially when programming in App Inventor.

Teaching Tip: Pseudocode for More Practice

If students are struggling with writing App Inventor code, encourage them to express their ideas by: 1) explaining it out loud to someone else and 2) writing the pseudocode for the algorithm.

Teaching Tip: Enforcing POGIL Roles

One key to POGIL being effective in the classroom is ensuring that students are participating cooperatively - each student is assuming responsibility for their role in the group. As students are working, teachers should be moving around the room and listening to groups to make sure that students are not only staying on task with activities, but are also actively fulfilling their roles. You can print and distribute the role cards to each group, or even post them in your classroom for easy reference.

2.3.2. Professional Development Reflection

Discuss the following questions with other teachers in your professional development program.

• How do the lesson activities reinforce the idea that algorithms are precise sequences of instructions that can be executed on a computer? 
• In this course we will building and analyzing algorithms throughout our study of computer science. Is there anything else you would need to have or know to teach this lesson effectively? What specific elements of this lesson (examples, activities, etc.) would you change? How would you modify or add to the interactive exercises (formative assessments)?
• How does the use of POGIL reinforce the computational thinking practices of communication and collaboration?

I am confident I can teach this lesson to my students.
• 1. Strongly Agree
• 2. Agree
• 3. Neutral
• 4. Disagree
• 5. Strongly Disagree