Recursion: Smaller Sibling Pyramids

1 468 Download(s)

Lesson synopsis

humanRecursion, Iteration (Looping), and Concurrency. In the first of two sessions (at most an hour each), students are asked to calculate a simple summation by themselves, based on a procedure they are given. Then, through a guided role-playing procedure, students are asked to do the same problem by pushing a sub-problem off onto a ‘little sibling’. In the second session, they use a divide-and-conquer approach to understand a simple formula for summation. During this session they also talk about the big ideas behind these three problem solving methods.

Age Levels

8 - 13 years

Objectives

Introduce students to:
how arithmetic sequences solve real world problems
tail-end recursive algorithms for arithmetic series
a divide and conquer approach that leads to a simple formula
informal ideas about time complexity.

Anticipated learner outcomes

Students will be able to describe how to solve an arithmetic sequence summation problem:
by doing it again and again (non-concurrent iteration)
with a smaller sibling (tail-end recursively)
articulate that both methods take the same number of steps, but recursion is less work for the individual
divide and conquer has a surprising outcome – namely a formula that can be calculated in only a few steps.

Optional Writing Activity

This activity introduced the idea of how to efficiently calculate an arithmetic series, such as 1+2+3+4. This could be used to calculate the simple human pyramid where one person is added as support for each layer. Invent your own problem that produces a different arithmetic pattern such as 1,5,9,13,17. Ask someone in your class to solve it by simple addition, by recursion, and to see if they can come up with a formula based on divide and conquer.
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.

Router
Sandra Lerner

It is difficult to imagine a time when computers were not capable of sharing information and resources with great ease. Sandra Lerner pushed the boundaries of network computing as one of the co-founders of Cisco Systems, which introduced one of the first commercially viable routers. The router was born while Sandra was working at Stanford University in the 1980’s after earning her Master’s degree there in Computer Science. To avoid the tedious task of transferring information between computers using floppy disks, she and co-founder of Cisco, Leonard Bosack, created a local area network, or LAN, between their campus offices using a multiprotocol router that Bosack developed. Shortly thereafter the pair started Cisco Systems, and began selling the router which was a success, because it could work with so many different types of computers. After Leaving Cisco in 1990, Lerner started the trendy cosmetics company Urban Decay and became a philanthropist and avid activist for animal rights.

MATLAB graph
Cleve Moler

Cleve Moler improved the quality and accessibility of mathematical software and created a highly respected software system called MATLAB. He was a professor of mathematics and computer science for almost 20 years at the University of Michigan, Stanford University, and the University of New Mexico. In the late 1970’s to early 1980’s he developed several mathematical software packages to support computational science and engineering. These packages eventually formed the basis of MATLAB, a programming environment for algorithm development, data analysis, visualization, and numerical computation. MATLAB can be used to solve technical computing problems faster than with traditional programming languages, such as C, C++, and Fortran. Today, Professor Moler spends his time writing books, articles, and MATLAB programs.

Listen to what Professor Moler has to say about his life’s work: http://www.youtube.com/watch?v=IT5umwNSAxE

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.

Bletchley Park
Dr. Sue Black
Dr. Sue Black

Dr. Sue Black has demonstrated the power of social networking. She used Web 2.0 technologies to help raise awareness of, and critical funding for, Bletchley Park, the UK World War II center for decrypting enemy messages. She has also been an active campaigner for equality and support for women in technology fields, founding a number of online networking platforms for women technology professionals. A keen researcher, Dr. Black completed a PhD in software measurement in 2001. Her research interests focus on software quality improvements. She has recently won the PepsiCo Women's Inspiration Network award, been named Tech Hero by ITPRO magazine and was awarded the first John Ivinson Award from the British Computer Society. In 2011 Dr. Black set up The goto Foundation, a nonprofit organization which aims to make computer science more meaningful to the public, generate public excitement in the creation of software, and build a tech savvy workforce. Read Sue's blog about The goto Foundation: http://gotofdn.org

Image credits