Sorting Socks is Algorithm Complexity

1 561 Download(s)

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

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.

CGA palette
Mark Dean

If you have ever used a PC with a color display you have been acquainted with the work of Mark Dean. After achieving a Bachelor’s degree in electrical engineering from the University of Tennessee, Dean began his career at IBM. Dean served as the chief engineer on the team that developed the first IBM PC, for which he currently holds one third of the patents. With colleague Dennis Moeller, he developed the Industry Standard Architecture (ISA) systems bus, which enabled peripheral devices such as printers, keyboards, and modems to be directly connected to computers, making them both affordable and practical. He also developed the Color Graphics Adapter which allowed for color display on the PC. Most recently, Dean spearheaded the team that developed the one-gigahertz processor chip. Dean went on to obtain a MSEE from Florida Atlantic University and a Ph.D. in electrical engineering from Stanford University. He is a member of the National Academy of Engineering, has been inducted into the National Inventors Hall of Fame, and is the first African-American IBM Fellow.

@ symbol
Ray Tomlinson
Ray Tomlinson

Have you ever considered that someone, at some point, was in a position to choose what symbol would be used separate the user from their location in an email address? That person, it turns out, was Ray Tomlinson, and in 1971 he chose "@". Tomlinson is credited with demonstrating the first email sent between computers on a network, and when asked what inspired him to make this selection he said, “Mostly because it seemed like a neat idea.”

After completing his Master’s degree at MIT in 1965, Ray joined the Information Sciences Division of Bolt Beranek and Newman Inc. of Cambridge, Massachusetts. Since then he has made many notable contributions to the world of network computing. He was a co-developer of the TENEX computer system that was popular in the earliest days of the Internet; he developed the packet radio protocols used in the earliest internetworking experiments; he created the first implementation of TCP; and he was the principle designer of the first workstation attached to the Internet.

Image credits