CS 136 Assignment 4

Due Wednesday, Oct. 10 at 11:59 am sharp. Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp.

All work must be submitted to the Marmoset submission system. See the preamble of assignment 1 for more information.

Hand Marking: this assignment will include marks for handmarking (in addition to Problem 3) the style and documentation of your solution for Problem 2. A guideline and set of principles is found HERE.

Assignment 4 Problem 1. 40 Marks.

This problem has four parts: A4P1a through A4P1d.

For A4P1a, you are to submit a module scratchandwin.rkt that provides two functions that implement a "scratch and win" system like that used by stores to award discounts and other prizes:

  ;; (drawcard n) produces a new "scratch and win" lottery card which contains a
  ;;            secret number between 1 and n.

  ;; (scratch card) consumes a card that was produced by (drawcard n) for some n.
  ;;                Produces (list secret n) where secret is the secret number and
  ;;                n is the value such that (drawcard n) produced card.
  ;;                Produces 'fraud if card was not produced by drawcard.

You may not use mutation in the implementation of any of the parts of this problem. Marmoset will do a cursory check to ensure that you don't use any of the mutation operations presented in class (e.g. set!, set-date-year!). Do not attempt to defeat the Marmoset check by finding some other means of mutation. Alert students will observe that (random n) cannot in fact be implemented without mutation. You are allowed this one exception.

Example interaction:

  > (require "scratchandwin.rkt")
  > (define a (drawcard 2))
  > (scratch a)
  (2 2)
  > (define b (drawcard 2))
  > (scratch b)
  (2 2)
  > (define c (drawcard 2))
  > (scratch c)
  (1 2)
  > (define d (drawcard 1000000))
  > (scratch d)
  (131539 1000000)

For A4P1b, you are to implement a module prize.rkt that provides the following function:

  ;; (collect-prize cardlist) consumes a list of n cards, each created by (drawcard n),
  ;;                  where each card has a distinct secret number.  Produces 'prize
  ;;                  if cardlist is correct.  For any other input, regardless of
  ;;                  what it is, produces 'fraud.  That is, if cardlist is not a list,
  ;;                  or does not contain n elements, or the elements are not produced
  ;;                  by (drawcard n), or the secret numbers are not distinct.

For A4P1b, you may assume n≤1000, and that a correct implementation of scratchandwin.rkt is available in the testing environment.

Example interaction:

  > (require "scratchandwin.rkt")
  > (require "prize.rkt")
  > (define a (drawcard 2))
  > (scratch a)
  (2 2)
  > (define b (drawcard 2))
  > (scratch b)
  (2 2)
  > (define c (drawcard 2))
  > (scratch c)
  (1 2)
  > (collect-prize (list a c))
  prize
  > (collect-prize (list a b))
  fraud

For A4P1c, you are to submit a module playscratchandwin.rkt that provides the following function:

  ;; (playgame n) draws as many cards as necessary to accumulate n
  ;;              distinct ones, and produces cardlist such that
  ;;              (collect-prize cardlist) produces 'prize

Sample interaction:

  > (require "playscratchandwin.rkt")
  > (require "prize.rkt")
  > (collect-prize (playgame 30))
  prize

For A4P1c, you may assume n≤1000, and that a correct implementation of scratchandwin.rkt is available in the testing environment.

For A4P1d, you are to submit a version of prize.rkt that works for 1≤n≤1000000.

The CPU time limit for this problem is 10 seconds. Hint: the builtin function (sort lst <) has run time O(n log n) where n = (length lst).

Assignment 4, Problem 2. 35 marks (20 marked by marmoset, 15 hand-marked). File: powmod.c

Hand Marking: this assignment will include 15 marks for handmarking (in addition to Problem3) the style and documentation of your solutions for Problem 2. A guideline and set of principles is found HERE.

One of the most common operations in modern cryptography is to compute the eth power of a number x modulo another number m, where e is very large. For example, we might compute 7³¹¹⁴ mod 51449. The most naive approach would be to first compute y=7³¹¹⁴ (which is a huge number), then compute y%51449. A slightly better approach might be to multiply 7 by itself 3114 times, but each time compute the remainder by m. I.e., we could write the function

int powmod1(int x, int e, int m) { int y=1; for(int i=0; i<e; i++) { y= (x*y) % m; } return y; }

A better approach is to notice that e is either even or odd.

If e is even then x^e mod m = (x²)^e/2 mod m = (x² mod m)^(e/2) mod m
If e is odd then x^e mod m = x * (x²)^((e-1)/2) mod m = x * (x² mod m)^((e-1)/2) mod m

This gives a simple recursion for computing powers modulo m, we we can write in Racket as follows:

#lang racket (define (powmod2 x e m) (define xsqrm (remainder (* x x) m)) (cond [(= e 0) 1] [(even? e) (powmod2 xsqrm (/ e 2) m)] [(odd? e) (remainder (* x (powmod2 xsqrm (/ (sub1 e) 2) m)) m)]))

This method is called repeated squaring, and its speed is one of the crucial facets in many of the most common cryptography systems.

You are to provide a version of powmod2 in C which must not use recursion. A header file is provided in powmod.h. Implement both powmod1 (with the code given above) and powmod2 in the file powmod.c. You may assume that m<2¹⁵. In the comments for each of these functions give an estimate of the number of multiplications (*) required in terms of the exponent e, in the worst case.

Hint: Recall that the number of times we can divide a number e by 2 before getting a number less than or equal to 1 is less than 1+log₂(e).

Assignment 4, Problem 3. 25 marks. File: stack_frames.txt

For this question you write a plain text file showing a simulation of the runtime stack. Stack frames should have the following format:

----------------------------------- <Function_name> <variable1_name>: <variable1_value> ... <variableN_name>: <variableN_value> return addr: <return address> -----------------------------------

Note the use of hyphens to delimit the stack frame. An example of how we want a complete stack in stack_frames.txt to look is as follows (taken exactly from the stack in Module 3 Slide 71):

--------------------------- sum n: 3 r: 0 return addr: to main line 2 --------------------------- main i: 3 return addr: to OS ---------------------------

This question will be marked entirely by hand, so it is not necessary to have spacing, number of hyphens, etc. match exactly, but your stack frames must appear as close to this format as possible.

Consider the functions mystery2, mystery, and main appearing below. The line numbers in the left-hand side are for reference only and are not a part of the code. Answer each of the following questions with respect to those functions. While answering these questions, treat each question independently, do not base your answer on the other questions.

(i) Assuming a single call to main() is made, and i has a value of 3 in main (from scanf), draw the entire runtime stack when (A) is reached.

(ii) Assuming that we are at line (A) in the code, and the top of the runtime stack looks like the following:

------------------------------- mystery2 n: 4 k: 2 return addr: to mystery line 25 ------------------------------- mystery n: 4 t: 0 x: 0 y: 0 z: 0 return addr: to mystery line 32 -------------------------------

Draw the top frame of the stack when (B) is next reached.

(iii) Assume that we are at line (B) in the code, and the top of the stack looks like the following:

------------------------------- mystery n: 2 t: 0 x: 1 y: 0 z: 0 return addr: to mystery line 32 -------------------------------

Draw the top two frames of the stack when (C) is next reached.

No memory diagram is required for the following sub-question. Let F(n) represent the number of times line (A) is reached when mystery(n) is called.

(iv) State the value of F(15). Be sure to explain how you arrived at your answer.

You should submit just the file stack_frames.txt for this question. In the file, number each sub-question as indicated (i, ii, etc). For parts (i) through (iii) you should produce three clearly labeled separate diagrams.

01 #include <stdio.h> 02 #include <stdbool.h> 03 04 int mystery2(int n) { 05 int k = n/2; 06 // ******** (A) ********* 07 if (k == 0) 08 return 0; 09 else if (k % 2 == 0) 10 return mystery2(k); 11 else 12 return k; 13 } 14 15 int mystery(int n) { 16 int t = n % 2; 17 int x = 0; 18 int y = 0; 19 int z = 0; 20 if (n == 0) { 21 // ******** (C) ********* 22 return 0; 23 } 24 else if (t == 0) { 25 x = mystery2(n); 26 // ******** (B) ********* 27 y = mystery(n-1); 28 29 return x + y; 30 } 31 else { 32 z = 1 + mystery(n-1); 33 34 return z; 35 } 36 } 37 38 int main() { 39 int i; 40 scanf("%d",&i); 41 printf("%d\n", mystery(i)); 42 }