Sorting Socks is Algorithm Complexity

0 Review(s)
612 Download(s)
Rate & Review

Lesson synopsis

socksHow 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.

Age Levels

11 - 13 years

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.

Optional Writing Activity

Pick your favorite algorithm among the ones you’ve studied. Describe how the algorithm would work on a collection of objects. What attribute would you use for the searching or sorting. Why is it your favorite?

Rate this lesson plan

Add new review

Gordon and SenseCam QUT
Gordon Bell
Gordon and SenseCam QUT

Gordon Bell is a pioneering computer designer with an influential career in industry, academia and government. He graduated from MIT with a degree in electrical engineering. From 1960, at Digital Equipment Corporation (DEC), he designed the first mini- and time-sharing computers and was responsible for DEC's VAX as Vice President of R&D, with a 6 year sabbatical at Carnegie Mellon University. In 1987, as NSF’s first, Ass't Director for Computing (CISE), he led the National Research Network panel that became the Internet. Bell maintains three interests: computing, lifelogging, and startup companies—advising over 100 companies. He is a Fellow of the, Association of Computing Machinery, Institute of Electrical and Electronic Engineers, and four academies. He received The 1991 National Medal of Technology. He is a founding trustee of the Computer History Museum, Mountain View, CA. and is an Researcher Emeritus at Microsoft. His 3 word descriptor: Computing my life; computing, my life.

King's Quest
Roberta Williams

Video games immerse users in a world of high tech thrills, stunning visuals, unique challenges, and interactivity. They enable users to become a warrior princess or a gruesome ghoul, create a virtual persona, or even develop worlds that other gamers can play on. But before the games of today became reality, they were the dreams of a few innovative individuals.

Roberta Williams is considered one of the pioneers of gaming as we know it today. During the 80’s and 90’s along with husband Ken Williams through their company On-Line Systems, she developed some of the first graphical adventure games. These included such titles as Mystery House, Wizard and the Princess and the popular King’s Quest series. Williams also helped introduce more girls and women to the world of gaming by bringing games developed from a woman’s perspective to mainstream market.

Turing machine
Alan Mathison Turing
Alan Mathison Turing

Did you know that computing has been used in military espionage and has even influenced the outcome of major wars? Alan Mathison Turing designed the code breaking machine that enabled the deciphering of German communications during WWII. As per the words of Winston Churchill, this would remain the single largest contribution to victory. In addition, he laid the groundwork for visionary fields such as automatic computing engines, artificial intelligence and morphogenesis. Despite his influential work in the field of computing, Turing experienced extreme prejudice during his lifetime regarding his sexual orientation. There is no doubt that computers are ubiquitously part of our lives due to the infusion of Turing’s contributions.

First computer mouse
Douglas Engelbart
Douglas Engelbart

In 1967, Douglas Engelbart applied for a patent for an "X-Y position indicator for a display system," which he and his team developed at the Stanford Research Institute (SRI) in Menlo Park, California. The device, a small, wooden box with two metal wheels, was nicknamed a "mouse" because a cable trailing out of the one end resembled a tail.

In addition to the first computer mouse, Engelbart’s team developed computer interface concepts that led to the GUI interface, and were integral to the development of ARPANET--the precursor to today’s Internet. Engelbart received his bachelor’s degree in electrical engineering from Oregon State University in 1948, followed by an MS in 1953 and a Ph.D. in 1955 both from the University of California, Berkeley.

Punch card from a COBOL program
Jean Sammet

Jean E. Sammet was one of the first developers and researchers in programming languages. During the 1950’s - 1960’s she supervised the first scientific programming group for Sperry Gyroscope Co. and served as a key member of the original COBOL (COmmon Business-Oriented Language) committee at Sylvania Electric Products. She also taught one of the first graduate programming courses in the country at Adelphi College. After joining IBM in 1961, she developed and directed the first FORMAC (FORmula MAnipulation Compiler). This was the first widely used general language and system for manipulating nonnumeric algebraic expressions. In 1979 she began handling Ada activities for IBM’s Federal Systems Division. Ada is a structured, object-oriented high-level computer programming language, designed for large, long-lived applications, where reliability and efficiency are paramount. Jean has a B.A. from Mount Holyoke College and an M.A. from the University of Illinois, both in Mathematics. She received an honorary D.Sc. from Mount Holyoke (1978).

Image credits