## 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. Digital Literacy and Computer Science DLIT (2018) Grade: 5 3) Create an algorithm that is defined by simple pseudocode. 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). 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. 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. Digital Literacy and Computer Science DLIT (2018) Grade: 8 5) Discuss the efficiency of an algorithm or technology used to solve complex problems. Digital Literacy and Computer Science DLIT (2018) Grade: 8 6) Describe how algorithmic processes and automation increase efficiency.
Tags: algorithm, binary, binary search algorithm