Compsci 101, Fall 2014, Lab 11

Part 1: Thesaurus APT

Consider the following example: 

["point run score", "point dot", "cut run tear score", "cut valley", "cute pretty"]
Returns: [ "cut point run score tear", "cut valley", "cute pretty", "dot point" ]
  1. Explain how to identify which two entries need to be combined. Which kind of collection (list, set, or dictionary) would be helpful in determining that?

  2. Explain how to actually combine two entries. Which kind of collection (list, set, or dictionary) would make combining the entries easier?
    3.

  3. Explain how to loop over the entries to compare each pair for possible combination. How will you update the list of entries once you have combined two entries?

  4. Write the function combine_entries that simply finds a pair of entries to combine, combines them, and returns True if such a combination took place, False otherwise.

Now consider this example: 

["ape monkey wrench", "wrench twist strain", "monkey twist frugue strain"]
Returns: [ "ape frugue monkey strain twist wrench" ]
  1. Explain how to determine when to stop combining entries.
    2.

  2. Write an indefinite, i.e., while, loop that calls the function combine_entries, until all entry pairs have been combined.

Part 2a Recursion

Consider the mystery function. 
def mystery(x, y):
    if x <= y:
        return 1
    return 2 + mystery(x-1, y+1)
  1. Consider the statement print mystery(5,5). How many recursive calls are there? What is the output?

  2. Consider the statement print mystery(7,4). How many recursive calls are there? What is the output?

  3. Consider the statement print mystery(10,3). How many recursive calls are there? What is the output?

Part 2b Recursion

For each of these after answering the first two questions, try commenting out your old code and putting in your new recursive code and running them in eclipse.

    Consider the APT Acronym that was part of APT Problem Set 2. Consider rewriting it using recursion.

  1. What is the smaller problem to solve? (hint: consider using find)

  2. What is the way out to stop the recursion, the smallest problem that does not use recursion?

  3. What is the recursive code for this problem?

    Consider the APT CountAppearances that was part of APT Problem Set 3. Consider rewriting it using recursion.

  4. What is the smaller problem to solve?

  5. What is the way out to stop the recursion, the smallest problem that does not use recursion?

  6. What is the recursive code for this problem?

    Consider the APT Bagels that was part of APT Problem Set 3. Consider rewriting it using recursion.

  7. What is the smaller problem to solve?

  8. What is the way out to stop the recursion, the smallest problem that does not use recursion?

  9. What is the recursive code for this problem?