CS 136 - Winter 2016 - Assignment 5

Due Date: Friday, 12 February 2016 at 11:59am.


LANGUAGE FEATURES

In this assignment, you must use only the C language features introduced up to section 06 of the course notes.


HAND MARKING

[10 marks style]

In addition to the marks provided below, at least one question will be additionally hand-marked for style (see the preamble).

If you do not submit a question that is marked for style, you will lose the style marks assigned to that question.


BLACK QUESTION (moderate collaboration is allowed)

[3 marks correctness] [??? marks style]

Question 1: Basic pointer manipulation

Create a module basic_pointer that provides the function:
int *down_value(int *x, int *y).

The function changes the larger value (i.e., *x or *y) to be the same as the smaller value and returns the address of the value that was mutated (i.e., previously larger). If the values are the same, the function should make no change and return NULL.

We have provided a very basic test client equivalent to the MARMOSET basic (public) test. You will want to test your code more thoroughly.


Question 2: Using pointers to "return" multiple values

Use the provided readnat module for reading natural numbers from user input. It is unchanged from previous assignments.

For the purposes of this question, a "failure" is when readnat returns -1.

BLACK QUESTION (moderate collaboration is allowed)

[5 marks correctness] [??? marks style]
  1. Create a module pointer_fun_black that provides the function:
    int read_two(int *n1, int *n2).

    The function tries to read in two natural numbers using readnat() and stores the first number in *n1 and the second in *n2. If the first read fails it does not attempt to read in the second number and the function leaves the values in *n1 and *n2 unchanged. If only the second read fails, then the value in *n2 is unchanged. In other words, values are only mutated if the corresponding read succeeds.

    The return value must indicate how many numbers were successfully read (0, 1 or 2).

    We have provided a very basic test client equivalent to the MARMOSET basic (public) test. You will want to test your code more thoroughly.

GOLD QUESTION (no collaboration allowed)

[7 marks correctness] [??? marks style]

For the following questions, the MARMOSET basic (public) tests will not actually test your code. You are encouraged to write your own tests.

Create a module pointer_fun_gold that provides the following two functions:

  1. bool sum_and_range(int n, int *sum, int *smallest, int *largest)

    The function attempts to read exactly n natural numbers and:

    1. mutates *sum to store the sum of all n numbers, or 0 if n is 0.
    2. mutates *smallest and *largest to stores the smallest/largest of all numbers, or 0 if n is 0.

    If a failure occurs before n numbers are read in, the function stops reading in numbers and mutates *sum, *smallest and *largest based on the numbers read in before the failure.

    If all n numbers are successfully read in, the function returns false (0) to indicate success, otherwise it returns true (1).


  2. int sum_numbers(int *sum).

    This function reads natural numbers until a failure occurs. The function mutates *sum with the sum of all the numbers that were successfully read (or 0 if none were read) and returns how many numbers were successfully read.


Question 3: Stack Frames

In assignment 4 we specified a format for representing stack frames in a text file. This question uses the same representation, except for one addition.

We introduce new notation to represent the contents of pointer variables. Since memory addresses are only determined once a program begins executing, we will use labels to represent addresses. It is only necessary to add a label to a variable if its address is stored in a pointer variable. In a stack frame, the value of a pointer variable is either NULL or a label. A label has the format "addr_NUM" e.g. addr_1.

As an example, consider the following code:

int main(void) {
  int x = 10;
  int *px = &x;
  int **ppx = &px;
  //point A
}

The following is the representation of the stack frame for the main function at point A:

=========================
main:
  x: 10 [addr_1]
  px: addr_1 [addr_2]
  ppx: addr_2
  return address: OS
=========================

Looking at this stack frame, one can infer that the variable px contains the address addr_1 which is labelled to be the address of variable x.

(Note that it is unnecessary to label ppx because there are no pointers pointing at it.)

BLACK QUESTION (moderate collaboration is allowed)

[5 marks correctness (hand marked)]
  1. This question is a puzzle that requires understanding how the call stack is built and being comfortable with using pointers. We have provided you with a program in puzzle.c which contains an incomplete implementation of the function void twice_the_difference(struct posn *p1, struct posn *p2). Your job is to complete this implementation so that it will result in the stack contents given below, right before the function returns.

    Note: The main function is already implemented.

    IMPORTANT! To make the puzzle even more fun: you may not use any integer value other than 0. A statement temp.x = 0; is allowed, the statement temp.x = 7; is not.

    Note: We realize that there are an unbounded number of "correct" solutions. Your code must compile and should achieve the call stack state using as few C statements as possible. However, you will not be penalized if your solution does not use the smallest number of statements that can achieve this task.

    =========================
    twice_the_difference:
      temp:
        .x: 7
        .y: 3
      p1: addr_1
      p2: addr_2
      return address: main:???
    =========================
    main:
      first_pos [addr_1]:
        .x: 10
        .y: 5
      second_pos [addr_2]:
        .x: 14
        .y: 6
      return address: OS
    =========================
    

GOLD QUESTION (no collaboration allowed)

[10 marks correctness (hand marked)]
  1. In this question, you will manually determine the contents of the call stack at three different points (Point A, Point B and Point C) in the execution of the following C program. You will submit a plain text file using the representation discussed above. Please clearly separate the answers for each part of this question with a label (such as "Point A"), and a line of asterisks (*) above and below the answer. For example, something like the following:

    ************Point A************
    (your answer to what the stack looks like at point A)
    ************Point B************
    ...

    Note:Write your answer in the file stack_frame.txt

    Mountain View


GOLD QUESTION (no collaboration allowed)

[30 marks correctness] [??? marks style]

Question 4: Student records

In this question, you will write a student module to help the Math Faculty keep track of the progress of their students.

A skeleton declaration of struct student has been declared in the file student.h. You should use the id field that is already there but you should add additional fields to implement the required functions.

You can not store in the student structure the grades of each course taken (by using a Sequence or an array). You may only store summary statistics. You should be careful to collect the correct statistics to ensure that your functions will return the correct results.

IMPORTANT! A description each function you must provide can be found in the provided student.h interface.

The MARMOSET basic (public) tests will use the provided simple test client test-student.c. It is highly recommended that you test your module more exhaustively before making them available to the Faculty (by submitting them to marmoset).


Question 5: Mutable Sequence ADT in C

Recall from Section 02 that a Sequence is a Collection ADT that can store an arbitrary number of items.

We are not yet at the point where we can write our own complete ADTs in C. However, we can now use an ADT as a client.

We have provided an implementation of a Sequence ADT that can store int values. The interface for the ADT is provided in sequence.h and provides all the standard functions one would expect from a Sequence ADT.

We have provided the file extra-testseq.c that provides of an example of how a Sequence can be used.

You are required to write a module seq-tools that provides functions for working with sequences.

IMPORTANT! A description each function you must provide can be found in the provided seq-tools.h interface. Only the function names are listed below.

We have provided a testing framework (the seqio module) and a testing client test-seqtools.c, along with a README.TXT that describes how you can write your own .in and .expect files.

For this question, the MAMOSET basic tests ("public" tests) will be the same as the simple test files provided.

Mixed BLACK & GOLD Question

In this question you will be writing a module with both BLACK and GOLD questions. Be very careful when collaborating on BLACK questions to avoid disclosing any details of your GOLD solutions.

BLACK QUESTION (moderate collaboration is allowed)

[5 marks correctness] [??? marks style]
  1. void Sequence_add_one(struct Sequence *seq)
  2. struct Sequence *Sequence_build(int n)
  3. void Sequence_map(int (*fp)(int), struct Sequence *seq)

GOLD QUESTION (no collaboration allowed)

[25 marks correctness] [??? marks style]
  1. bool Sequence_equal(const struct Sequence *seq1, const struct Sequence *seq2)
  2. void Sequence_add_sum(struct Sequence *seq)
  3. void avg_and_variance(const struct Sequence *seq, int *avg, int *var)
  4. struct Sequence *Sequence_fib(int n)
  5. struct Sequence *Sequence_collatz(int n)
  6. void Sequence_filter(bool (*fp)(int), struct Sequence *seq)
  7. int Sequence_foldl(int (*fp)(int, int), int base, const struct Sequence *seq)

GOLD QUESTION (no collaboration allowed)

BONUS [5 marks]
  1. void Sequence_reverse(struct Sequence *seq)