CS538: Spring 2003

Assignment#1: Scheme

Handin procedure

  1. Your handin folder is in ~cs538-1/public/handin/proj1/login where login is your login name.

  2. Put your solutions in a SEPARATE FILE for each sub-part: 1a, 1b, 2, 3a, 3b, 3c, 3d, 4a, 4b, 5a, 5b, 5c. You can also include a file called README with any notes about your submission, especially analysis of the timing results for part 4b.

  3. Make each file SELF-CONTAINED. Don't load code used in another question (e.g., loading file 3a in the solution for 3b), and don't assume that your code will execute in the handin folder. To achieve this, you may need to make copies of code that is common to multiple sub-parts of the same question.

  4. Each file should make available (at least) the Scheme functions required by the question. Here's the complete list of functions that need to be present in each file. Note that you can have more functions defined, this are just the minimum definitions required in each file:
  5. Your submission must work correctly with DrScheme v101 installed here in CS (in ~fischer/public/drscheme/plt/bin) with the "Full Scheme" Language option. You are free to work on your own with a newer version of DrScheme which you might have downloaded and installed at home but before submission, you must make sure your code runs with our version of DrScheme. You can minimize problems by making sure you set the Language to full Scheme in whichever version you use (see bottom of this page for setting the Language option in newer versions of DrScheme). And if you use DrScheme library functions, please make sure that these library functions are also available in DrScheme v101 installed here in CS.

  6. Your code will be tested for correctness using automatic scripts and a test suite. So please make sure that the code you submit does not generate extraneous output by calling the display or write or other Scheme output functions. Each of the functions listed in bullet 4 above should silently return values as required by the question. Also, please make sure that your files are free of any top-level tests or timings that you may have used during development.

  7. You can assume that your functions will always be passed valid input, so you do not need to check, for example, that the input argument is a list or a number and so on. But your functions should be able to correctly handle all valid input, including boundary conditions such as empty lists.

  8. Your handins will be picked up by automatic scripts on the midnight of the due date (Mar 24), and then again on the midnights of each of the 3 allowed later days (Mar 26, 28, 31). Any files found in a handin folder by our scripts on these 4 days will be deemed to be part of a submission, and that handin folder will be made unwritable immediately. So if you plan to submit late, make sure that your handin directory is empty on the earlier submission days. You can also email me at plakal@cs.wisc.edu to let me know that you are submitting late.

Grading criteria

The first and foremost criteria for grading is correctness. Your programs should execute without errors and produce the correct output with our test suite. Points are awarded for each test input successfully handled by your code.

You can use any algorithms or Scheme functions to produce the correct output, you are not restricted to following the path set by the questions. But you must follow the question when it comes to mandatory requirements, such as using continuations to exit early in Q.5(c) or lazy evaluation in Q.4 or not simply generating all subsets in Q.1(b).

No extra points for the most elegant programs but you are encouraged to write in a functional style, making best use of Scheme's natural abstractions: lists, recursion, higher-order  functions, continuations, and so on. These will invariably reward you with compact, natural-looking code which is easy to read and understand. See the lecture notes and look online for Scheme programs to get a flavor of Scheme programming.  

We will penalize programs that are excessively kludgy and hard to read or understand. Don't try to write C++ or Java in Scheme. In particular, the excessive use of the update operator set! (and its relatives) is frowned upon and will be penalized. Note that this does not apply to question 2 (the queue) where the use of this operator is somewhat natural.

Partial credit will be given for programs that seem to be on the right track.

Scheme Tips

First of all, check out the 538 Scheme page for information on DrScheme and how to use it in the CS Department.

See the Scheme Language Definition for the final word on standard Scheme language constructs and some of the standard built-in functions which you can use (see the Standard Procedures section).

See the PLT MzScheme Language Manual for information on the language constructs and standard library procedures available in the Scheme interpreter of the DrScheme environment.

Note that we have DrScheme v101 installed here in ~fischer/public/drscheme/plt/bin. If you are using the latest version of DrScheme (v201 or later), then be aware of things that work differently in the new versions:
- Manoj Plakal <plakal@cs.wisc.edu>