Lesson Focus

How do you know how fast a computer can calculate an answer, or whether an answer can be calculated at all? The field of Computational Complexity is the study of whether problems can be solved, and how fast. This lesson introduces some simple ideas about algorithms and their complexity through a series of exercises involving a collection of socks. Of course, other objects can be used as well. This is an active learning lesson that does not require access to a computer. Linear, polynomial, and logarithmic algorithms are explored building an intuitive understanding of order of magnitude.


Download:

Full Lesson Plan


Age Levels:

11 – 13

Objectives

Introduce students to classic algorithms:
  • for finding something in a sequence.
  • for finding something in an ordered list.
  • for simple sorting.
  • and provide informal methods for determining algorithm complexity.

Anticipated Learner Outcomes

Students will be able to:
  • describe why finding an item in a collection may require looking at each item.
  • discuss that ordering objects significantly reduces the time needed to find a specified one.
  • discuss that there are many ways to sort objects.

Lesson Activities

This lesson introduces some simple ideas about algorithms and their complexity through a series of exercises involving a collection of socks.

Alignment to Curriculum Frameworks

Curriculum alignment sheet is included in PDF.