Recursion: Smaller Sibling Pyramids

2 140 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.
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.

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.

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.

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

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.

Image credits