CS 136 Assignment 1

Due Wednesday, Sept. 19 at 11:59 AM sharp (noon). Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp.

There is no hand marking on this assignment.

All work must be submitted to the Marmoset submission system. Submitted programs are graded automatically by Marmoset. Typically, you may view the grades using the Marmoset system a few minutes after submission. "Written problems" must also be submitted electronically, but are marked later by hand. Assignment 1 has no written problems.

You may submit to Marmoset and view your results at any time from any computer on the internet. You do not need to use the student.cs computing environment, but you may if you wish. You may even submit after the deadline and see your results, but you will receive half credit. Marmoset takes your best result for every problem, so there is never any harm in resubmitting.

If Marmoset fails to accept submissions for more than two of the six hours immediately prior to the deadline, or is down at the deadline, a 12-hour extension will be granted. For an extension to be granted, Marmoset must fail to accept submissions; failure or delay in displaying results is not grounds for extension. It is bad practice, and risky, to rely on Marmoset as your primary means of testing. The failure must be due to problem with Marmoset or a widespread network failure; your home connection is your own responsibility.

Each problem requires an independent submission. Although the problems often build on a common theme, you are welcome to submit them in any order.

Each submission is allowed 1 second of CPU time and 128MB of memory to solve several test cases. If either limit is exceeded, an error message is shown in the detailed Marmoset results.

You should continue providing design recipes as you learned in CS 135.

Assignment 1 Problem 0. 10 Marks. File: runc.txt

In CS 136, we strongly recommend that you use the RunC environment to compile and run your C programs. To remove the stress from setting up the environment at the time when you have to work on your C assignments, we are asking you to set up the environment early in the semester. Please visit the CS 136 Software page and follow the instructions to set up RunC. Once you are done, please submit a file named runc.txt that contains "RunC, I'm afraid of you no longer!" (without quotes) confirming that you got the environment working correctly.

Assignment 1 Problem 1. 10 Marks. File: a1p1.rkt

Write a module in Scheme that evaluates to the sum of the integers between 1 and 10, inclusive. Your module must be in a file named a1p1.rkt (all lower case). To test your solution prior to submission, create and run the following client module:

   ;; Test module for a1p1.rkt
   ;; The number 55 should be displayed
   #lang racket
   (require "a1p1.rkt")

Assignment 1 Problem 2. 30 Marks. File: playgame.rkt

Write a module in Scheme that plays a simple guessing game. Your module will attempt to guess a secret number chosen by an opponent module. The opponent module, "game.rkt", will be supplied in the Marmoset environment.

The interface for game.rkt is as follows:

   ;; Implementation of simple guessing game
   ;; Provides:  startgame, guess

   ;; (startgame n) starts a new game in which the
   ;;    game [this module] chooses a secret integer
   ;;    between 1 and n, and you [the client module]
   ;;    try to guess it

   ;; (guess x) consumes an integer x and produces
   ;;     either 'right or 'wrong, depending on whether
   ;;     or not x is the secret integer

The interface for your playgame.rkt module must be as follows:

   ;; Player for simple guessing game
   ;; Provides:  playgame

   ;; (playgame n) uses "game.rkt" to start and play an entire
   ;;              game of size n, and produces m,
   ;;              the total number of guesses actually 
   ;;              used by playgame to complete the game

For this problem, any strategy will do, so long as (playgame n) is never larger than n. For testing you may wish to use this implementation of game.rkt. However, you should not submit a game.rkt file, and you should not assume that the version supplied by Marmoset will have the same implementation. It will however conform to the same interface, that is, it will provide the same functions. For assignment 1, problem 2 you may assume that n ≤ 100000.

Assignment 1 Problem 3. 30 Marks. File: alist.rkt

Write a module that implements association lists, which were introduced in CS 135 (Module 6). Each key and each value can be of any data type whatsoever. All keys must be unique (you can use the equal? procedure to test keys for equality, as in (equal? a b)); values are not necessarily unique. This question is primarily to refresh your knowledge of CS 135. The module must provide the following procedures:

(define (make-alist kvl) ...) ;; given a list of key-value pairs kvl (kvl may contain key-value pairs with the same key) creates an association list that maps a to b for all pairs (list a b) in kvl. The items in kvl should be added to the association list from left to right.

(define (alist-lookup alst key) ...) ;; produces the value associated with key, or false if key is not mapped to anything in the association list alst.

(define (alist-remove alst key) ...) ;; produces an association list identical to alst, except without key (and its corresponding value).

(define (alist-add alst key value) ...) ;; produces an association list identical to alst, except with key mapping to value.

(define (alist? x) ...) ;; produces true if x is an association list, false otherwise.

Assignment 1 Problem 4 (Bonus). 11 Marks. File: playgame.rkt

For this problem, you must implement (playgame n) to use (n+1)/2 guesses, on average, after playing a large number of games. Marmoset will try to defeat you, but it will not cheat. That is, Marmoset will pick secret numbers that it thinks you will have difficulty guessing, but will not change the number it has picked in the middle of a game. For assignment 1, problem 4 you may assume that n ≤ 100000.