Santa's Dirty Socks (Divide and Conquer Algorithms)

This original story introduces the idea of a divide-and-conquer algorithm using a narrated picture-book verse about the serious problem of finding a pair of dirty socks that have been accidentally wrapped with a child's present. The idea is that this can be played or read to students, and then can be used as the basis for a follow-up discussion. A set of discussion starter questions is available (http://csunplugged.org/divideAndConquer) to encourage students to engage in computational thinking and think about algorithm analysis in the story 1024 presents are searched in 10 steps, and students can be asked to extend this to other cases, and generally think about the implications of having an algorithm with logarithmic complexity.

Category:

Education

Tags:

• csunplugged
• santa
• dirty
• socks
• divide
• and
• conquer
• christmas
• elves
• presents
• toys
• 1024
• comparisons
• scales

[juliojdp]

would've sucked if after that.. the socks wasn't in that box lol

[tburny]

I don't think so :) I mean what happens if you divide into 1024 "piles" so it "would be faster"? It would not be faster of course :)

[mpetriful]

@wildwillrock so? divide it into 3 piles of 341,341 and 342 and weigh the two with equal size.

[mpetriful]

dividing into piles of three would be faster though...