Exam 2: Pointers and More

Distributed: Monday, 28 April 2003
Due: 10 a.m., Friday, 9 May 2003
No extensions!

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS195/2003S/Exams/exam.02.html.

Contents

• Preliminaries
• Problems
  • Problem 1: Formal Development
  • Problem 2: Debugging Memory
  • Problem 3: Fun with Scheme
• Errors
• Questions and Answers

Preliminaries

There are three problems on the exam. Some problems have subproblems. Each full problem is worth about thirty-three points. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem. If you write down the amount of time you spend on each problem and the total time you spend on the exam, I'll give you two points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than that limitation, you should feel free to use all reasonable resources available to you. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web (at least not until after I return exams to you). And, in case it's not clear, you may not ask others (in person, via email, or by posting a please help message) to put answers on the Web.

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast you work. You should not spend more than ten hours on this exam. Stop at ten hours and write: There's more to life than CS and you will earn at least 80 points on this exam. I would also appreciate it if you would write down the amount of time each problem takes. I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. Since I worry about the amount of time my exams take, I will give two points of extra credit to the first two people who honestly report that they've spent at least seven hours on the exam or that they've finished the exam. (At that point, I may then change the exam.)

You must include both of the following statements on the cover sheet of the examination. Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. Note also that inappropriate assistance is assistance from (or to) anyone other than myself or our teaching assistant.

1. I have neither received nor given inappropriate assistance on this examination.
2. I am not aware of any other students who have given or received inappropriate assistance on this examination.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam. You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must both answer all of your questions electronically and turn them in in hardcopy. That is, you must write all of your answers on the computer, print them out, and hand me the printed copy with your name and the page number on every page. If you fail to write your name on every page, I will penalize you five points. You must also email me a copy of your exam by copying your exam and pasting it into an email message. Put your answers in the same order as the problems.

In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code.

You should fully document all of the primary procedures (including parameters, purpose, value produced, preconditions, and postconditions). If you write helper procedures (and you may certainly write helper procedures) you should document those, too, although you may opt to write less documentation. When appropriate, you should include short comments within your code. You should also take care to format your code carefully.

Just as you should be careful and precise when you write code, so should you be careful and precise when you write prose. Please check your spelling and grammar. Since I should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. I will limit that form of extra credit to five points.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes this week and next to discuss any general questions you have on the exam.

Problems

Problem 1: Formal Development

Devin and Daren Doubter (no relation to Devin Lindsey and Daren Brantley) have indicated concerns about the usefulness of Gries's program development methodology. I've decided to use their doubt as a learning exercise for other students in the classs.

Write a short (2-3 pages) narrative that shows how Gries's method might help a programmer write binary search correctly. Your narrative should be of a form that one might hand it to CSC201 students immediately after the write incorrect binary search algorithms.

Note that I'll be particularly interested in your loop invariant and your termination analysis.

Problem 2: Debugging Memory

Gries's program-development methodology is a useful tool for debugging programs that primarily involve assignment, conditionals, and loops. Unfortunately, it does not speak to pointers.

a. Suppose Mervin and Mary Malloc find that the values that their pointers point to change without them changing those values directly. What steps might you take to identify potential error in their code?

b. Suppose Arnie and Amelie Allocator find that their programs run out of memory regularly. (Yes, they seem to work for Netscape.) How might you identify potential errors in their programs?

Problem 3: Fun with Scheme

Sarah and Steven Schemer like C, but love Scheme. They've decided to implement Scheme in C. As a first step, they've created scheme.h, a file containing type definitions they expect to be useful.

/*
 * Some plans for a simple implementation of Scheme.
 */

#include <stdio.h>

/*
 * Types of Scheme values
 */
typedef enum { PAIR, INT, REAL, CHAR, STRING, SYMBOL } schemetype;

/**
 * Scheme pairs.
 */
typedef struct pair {
  struct sval *car;
  struct sval *cdr;
} pair;

/*
 * Scheme values.
 */
typedef struct sval {
  schemetype type;
  union {
    pair p;
    int i;
    double d;
    char c;
    char *s;
  } contents;
} sval;
 
/*
 * Print a Scheme value to the given file.
 */
int printSVal(FILE *outport, sval *val);

/*
 * Read the next Scheme value from the given file.
 */
sval *readSVal(FILE *inport);

/**
 * Free the memory associated with a Scheme value (and any
 * Scheme values it references, in the case of pairs).
 */
void freeSVal(sval *val);

a. Implement the printSval(port,sval) procedure.

b. Implement the readSval(port) procedure.

c. Implement the freeSval(sval) procedure.

Errors

These are the errors observed by students. Since I have threatened to take off for grammatical or spelling errors, I give the whole class one point of extra credit for each such error they notice in this exam. Such extra credit is capped at five points.

All five points are already awarded. Please send me errors anyway.

Questions and Answers

Here you may eventually find questions from your colleagues and my answers to those questions.

What internal type should we use for symbols in Scheme?

char *, since a symbol is simply a sequence of characters.

Then how does a symbol differ from a string?

You print them differently. You compare them differently. For example, the symbol hello and the string "hello" are different values.

What do you want us to do about procedure values?

Nothing. I've left them out on purpose.

How tired were you when you wrote this exam?

Very.

What is the format for laboratory writeups.

Nevermind. I've eliminated the comment (which was taken from an exam in another class).

Do we really have to distinguish ints and doubles?

Nah.

Can we require that symbols start with non-numeric characters?

Yes.

Can we limit the length of symbols and strings?

Yes.