Recursion: Smaller Sibling Pyramids

1 573 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.
Liz Gerber - Image credit Lisa Beth Anderson
Liz Gerber
Liz Gerber - Image credit Lisa Beth Anderson

Liz Gerber earned her MS and PhD in Product Design and Management Science and Engineering at Stanford. She specializes in design and human-computer interaction, particularly how social computing supports the innovation process. Her current research investigates crowd-funding as a mechanism for reducing disparities in entrepreneurship.
Gerber's work funded by the US National Science Foundation and the National Collegiate Inventors and Innovators Alliance has appeared in peer-reviewed journals, including Transactions on Computer Human Interactions, Design Studies, and Organization Science.
As an award-winning teacher and researcher, Liz has touched the lives of more than 6,000 students through her teaching at Northwestern's Segal Design Institute and Stanford University's Hasso Plattner's Institute of Design and through her paradigm-shifting creation, Design for America, a national network of students using design to tackle social challenges.

Image credit - Lisa Beth Anderson

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.

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

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

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.

Image credits