9 Design with Generative Recursion

Purpose The purpose of this lab is to practice the design of functions that use generative recursion.

Textbook references Part V: Generative Recursion

Partnering

5 minutes

The Head TA will organize the re-partnering of everyone in the lab.

The Shoulder TA will then collect the names and record them.

Introduction

5 minutes

As discussed in class and the book, the design recipe for generative recursion is adapted from the strucutral design recipe. A breakdown of the recipe is below with changes from the stuctural design recipe italicized.

1. Data representation & definition. Remember to think of the data definition as representing a (class of) problems not just information.

2. Signature and purpose statement

   (including how the function does what it does)

3. Examples

   (work through the ’how’ with several examples)

4. Template

5. Code

   To develop the template and code for a generative recursive function, ask these four questions:

   • What is a trivially solvable problem?

   • How are trivial solutions solved?

   • How does the algorithm generate new problems that are more easily solvable than the original one? Is there one new problem that we generate or are there several?

   • Is the solution of the given problem the same as the solution of (one of) the new problems? Or, do we need to combine the solutions to create a solution for the original problem? And, if so, do we need anything from the original problem data?

6. Test

7. Step 7 Termination argument (either a ’size’ argument for each recursive call or examples of exceptions to termination)

Social Networking Part 2

We’ve decided to build a start-up around our social network design from last lab. Before it’s ready for private beta, we need to flesh out some basic functionality. Check out this starter file for the data definition as well as some helper functions to help you with the lab. Remember to follow the design recipe for generative recursion when needed.

Terminology For the following exercises contacts includes all the people to which a user relates, including ’mies.

Close Contacts

10 minutes

We’re going to want to show a user different content based on whether the person who posted it is one of their contacts.

Exercise 1 Design the function contact?, which determines whether a given user is directly connected with another given user in a social network.

Code Review #1

10 minutes

The Teaching Assistants will pick a pair to explain their solution to the lab following the design recipe steps.

I Know a Guy Who Knows a Guy Who...

25 minutes

Have you ever wondered if you’re somehow connected to someone famous, like say... Kevin Bacon?

Exercise 2 Design the function distant-contact?, which determines if a given user in a social network is connected with another given user through a chain of contacts. For instance, in the examples provided, Irene is connected to Katey who is connected to Louis, so Irene is distantly connected to Louis. You may wish to work through this example and turn it into a test.

Code Review #2

15 minutes

The Teaching Assistants will pick a pair to explain their solution to the lab following the design recipe steps.

The More the Merrier

25 minutes

Everyone knows that if a social network isn’t growing, it’s dying. We’ll suggest people for a user to connect to from their extended network; that is, their contacts, contacts of contacts, contacts of contacts of contacts... get the idea?

Exercise 3 Design the function up-to-depth, which gets the names of all the users that are at most a given number of relationships away from a given user in some social network.

Code Review #3

15 minutes

The Teaching Assistants will pick a pair to explain their solution to the lab following the design recipe steps.