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.)
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.
The POGIL exercise solutions are below:
- CAN_MOVE(forward) is true. CAN_MOVE(right) is false.
MOVE_FORWARD MOVE_FORWARD ROTATE_RIGHT MOVE_FORWARD MOVE_FORWARD MOVE_FORWARD MOVE_FORWARD ROTATE_LEFT MOVE_FORWARD MOVE_FORWARD
REPEAT 2 TIMES { MOVE_FORWARD } ROTATE_RIGHT REPEAT 4 TIMES { MOVE_FORWARD } ROTATE_LEFT REPEAT 2 TIMES { MOVE_FORWARD }
- 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.
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