Divide and Conquer

By
Not available
(2013-07)

Video

This activity introduces the idea of "divide and conquer" using a fictitious but serious problem - a pair of dirty socks have accidently 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 (below), or download the PDF of the book (see the PDF files below) 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.

Published by:

Computer Science Unplugged

DOER Persistent Identifier: http://doer.col.org/handle//123456789/3015
Collections: