COMP 210 Homework #10

Fall 2002

Due Mon. Nov. 25. at the start of class

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

IMPORTANT HAND-IN INSTRUCTIONS

Hand in a printed copy of your work as usual, but in addition, upload a copy of your code to the Exciton server (same as you did for Exam 2):

• Your file should be named: [username]HW10.scm
  Examples: mmouseHW10.scm, ianHW10.scm, swongHW10.scm.
  
  
• Upload your files to this URL (same password as for Exam 2): ftp://comp210@exciton.cs.rice.edu/comp210/dropoff/hw10
  Drop your homework into the folder corresponding to your lab section. If you and your partner are in different labs, drop your work off into the lab where your grader is, i.e. the one that usually hands back your graded homework.
  
  
• Remember that newer versions of Netscape won't work and to hit the Refresh/Reload if the page fails to appear.
  
  
• Make sure you type the password in correctly!!

You are NOT required to show the template for your programs (woo-hoo!). However, your functions should still follow the template, as appropriate. And of course, each function should still have a contract and purpose, and reasonable test cases.

Generative Recursion: Missionaries and Cannibals

Do Exercises 32.2.1 -- 32.2.7.

Warning: This problem is manageable only if taken in bite-sized chunks. Start on this homework promptly.

Clarifications (these will make sense only after you've read the problems completely):

• For Exercise 32.2.3, just generate all successor states, even if some of them aren't sensical (e.g. having -1 people on a side of the river). (Problem 4 will filter out the illegal and nonsense states.)
  
  
• For Exercise 32.2.6: The picture given helps illustrate the described process. It shows the starting state, below that all the states reachable in one trip (stating that two of them are illegal). Ideally, below that it would show not just the successors from one of the three legal states, but rather the successors of all legal states of the previous layer, i.e. all the states reachable in two boat-trips. (That would best illustrate the process.) After three iterations, you'll have all the states reachable in exactly three boat-trips.
  
  
• You can also Exercise 32.2.8, for 15 pts of extra credit. If you do, note how it changes the running-time of your program. Also answer: How many different legal states are there?
  
  
• You do not need to use any set-struct! for this assignment. Let me strengthen that: Do not use any exclamation points (!s) in your code.
  
  
• Note: You should be able to change either of the constants MC or BOAT-SIZE and get results for the corresponding problem (w/o needing to change any other code at all). For bigger boat-trip sizes, can cannibals outnumber missionaries? I don't see an important reason to go one way or the other; for standard comparison of results let's go with:
  Yes, two cannibals and a missionary will cooperate on the treacherous rapids.
  (In fact, you could even have a boolean constant MUTINY_POSSIBLE?, which switches this effect on and off. Probably only changes two lines in your code.)

Points:

Exercise 32.2.1: 5 pts

Exercise 32.2.2: 10 pts

Exercise 32.2.3: 15 pts

Exercise 32.2.4: 15 pts

Exercise 32.2.5: 10 pts

Exercise 32.2.6: 15 pts

Exercise 32.2.7: 15 pts

85 total points plus 15 extra credit