ALEX Classroom Resource

  

Divide and Conquer

  Classroom Resource Information  

Title:

 Divide and Conquer

URL:

 https://classic.csunplugged.org/divideandconquer/

Content Source:

 Other
CS Unplugged
Type: Learning Activity

Overview:

Santa’s Dirty Socks

This activity introduces the idea of “divide and conquer” using a fictitious but serious problem – a pair of dirty socks have accidentally been wrapped in one of the presents that Santa is about to deliver, and he needs to figure out which one to avoid a child getting a nasty surprise.

You can either play the video (linked in the activity) or download the PDF of the book (see the PDF files in the link to the activity) to read aloud or give to students.

The solution in the story points out that when there are 1024 boxes to test, instead of having to open all of them until the socks are found, one half can be eliminated at a time, and repeatedly halving the problem very quickly narrows it down to one box (the size of the problem starts at 1024, then with one weighing there are 512 boxes, then 256, 128, 64, 32, 16, 8, 4, 2 and 1.) This idea comes up frequently in the design of fast computer algorithms.

Content Standard(s):
Digital Literacy and Computer Science
DLIT (2018)
Grade: 5
2) Create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.

Examples: Program the movement of a character, robot, or person through a maze.
Define a variable that can be changed or updated.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • create an algorithm to solve a problem.
  • detect and debug logical errors within an algorithm.
Teacher Vocabulary:
  • algorithm
  • debug
  • detect
  • logical errors
Knowledge:
Students know:
  • an algorithm is a logical set of steps to solve a problem.
  • detecting and debugging logical errors within an algorithm will ensure the algorithm serves to solve a problem successfully.
Skills:
Students are able to:
  • create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.
Understanding:
Students understand that:
  • debugging an algorithm is searching for logical errors within the algorithm.
  • an algorithm is a set of steps to solve a problem.
  • how to create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 5
3) Create an algorithm that is defined by simple pseudocode.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • create set of steps that is written in simple pseudocode.
Teacher Vocabulary:
  • algorithm
  • pseudocode
Knowledge:
Students know:
  • simple pseudocode resembles language used to communicate with computers.
Skills:
Students are able to:
  • create an algorithm that is written in simple pseudocode.
Understanding:
Students understand that:
  • an algorithm that is written in simple pseudocode is similar to an algorithm written using a programming language.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 6
5) Identify algorithms that make use of sequencing, selection or iteration.

Examples: Sequencing is doing steps in order (put on socks, put on shoes, tie laces); selection uses a Boolean condition to determine which of two parts of an algorithm are used (hair is dirty? True, wash hair; false, do not); iteration is the repetition of part of an algorithm until a condition is met (if you're happy and you know it clap your hands, when you're no longer happy you stop clapping).

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • find algorithms that demonstrate the three basic programming structures.
Teacher Vocabulary:
algorithm sequence selection iteration
Knowledge:
Students know:
  • differences between the three basic programming structures.
Skills:
Students are able to:
  • explain the differences in sequencing, selection, and iteration.
Understanding:
Students understand that:
  • differences exist in sequencing, selection, and iteration.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 7
3) Create algorithms that demonstrate sequencing, selection or iteration.

Examples: Debit card transactions are approved until the account balance is insufficient to fund the transaction = iteration, do until.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • create an algorithm using one of the three basic programming structures: sequencing, selections, or iterations.
Teacher Vocabulary:
  • algorithm
  • sequence
  • selection
  • iteration
Knowledge:
Students know:
  • how to use the programming structures to create algorithms and how many algorithms make use of all three programming structures.
Skills:
Students are able to:
  • create and recognize various programming structures found in algorithms.
Understanding:
Students understand that:
  • each structure sequencing, selections, and iterations have a purpose.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 7
6) Create and organize algorithms in order to automate a process efficiently.

Example: Set of recipes (algorithms) for preparing a complete meal.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • use algorithms to automate a process such as sorting numbers in a random list or playing cards in a deck.
Teacher Vocabulary:
  • algorithm
Knowledge:
Students know:
  • algorithms can be used to automate a process efficiently.
Skills:
Students are able to:
  • use search and sort algorithms to automate organizing a set.
Understanding:
Students understand that:
  • algorithms organized and applied to the appropriate task can significant increase proficiency.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 8
5) Discuss the efficiency of an algorithm or technology used to solve complex problems.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • examine a given artifact used to aid in problem solving.
  • discuss the efficiency of that artifact in problem solving.
Knowledge:
Students know:
  • that many solutions exist to solve a problem.
Skills:
Students are able to:
  • communicate their opinion on the efficiency of problem solving methods.
Understanding:
Students understand that:
  • while many solutions exist for a problem, some are better suited to meet specific needs, such as efficiency.
Digital Literacy and Computer Science
DLIT (2018)
Grade: 8
6) Describe how algorithmic processes and automation increase efficiency.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • explain how algorithms and automation have and can increase efficiency.
Teacher Vocabulary:
  • algorithmic process
  • automation
Knowledge:
Students know:
  • how algorithmic processes and automation have increased efficiency.
Skills:
Students are able to:
  • explain how algorithmic processes and automation increase efficiency.
Understanding:
Students understand that:
  • automation is a useful tool for increasing efficiency.
  • while many things can and have been automated, not everything can be automated using algorithmic processes.
Tags: algorithm, binary, binary search algorithm
License Type: Attribution Non-Commercial Share Alike
For full descriptions of license types and a guide to usage, visit :
https://creativecommons.org/licenses
AccessibilityText Resources: Content is organized under headings and subheadings
Video resources: includes closed captioning or subtitles
Comments

This is a free resource from CS Unplugged.

  This resource provided by:  
Author: Aimee Bates
This site may contain links to other websites or content belonging to or originating from third parties or links to websites and features in banners or other advertising. Such external links are not investigated, monitored, or checked for accuracy, adequacy, validity, reliability, availability, or completeness by us. WE DO NOT WARRANT, ENDORSE, GUARANTEE, OR ASSUME RESPONSIBILITY FOR THE ACCURACY OR RELIABILITY OF ANY INFORMATION OFFERED BY THIRD-PARTY WEBSITES LINKED THROUGH THIS SITE.
Copyright © 2017, Alabama Learning Exchange
Alabama State Department of Education
Alabama State Department of Education