Sorting Socks is Algorithm Complexity

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

RISC processor
John Hennessy
John Hennessy

Have you ever wondered how computers can execute complex commands in mere seconds? John Hennessy is a pioneer of reduced instruction set computing (RISC) architecture which employs small, highly-optimized sets of instructions to greatly enhance computer performance. He was instrumental in transferring the technology, specifically MIPS RISC architecture, to industry. He co-founded MIPS Technologies and co-authored the classic textbook with David A. Patterson, on Computer Architecture.

As Stanford faculty he rose to be the Chairman of the Computer Science Department, Dean of the School of Engineering, then Provost and finally the President of Stanford in 2000 (and till date). Hennessy holds a Master’s and Ph.D. in Computer Science from SUNY Stony Brook. He is an IEEE Fellow and was selected to receive the IEEE Medal of Honor in 2012. Hennessey also launched significant activities that helped to foster interdisciplinary research in the biosciences and bioengineering at Stanford.

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

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

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.

Image credits