Exam 1

Distributed: Wednesday, 5 March 2003
Due: 11:59 p.m., Friday, 14 March 2003
No extensions.

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

Contents

• Preliminaries
• Problems
  • Problem 1: Reading Lines
  • Problem 2: Reading Lines, Revisited
  • Problem 3: Specifying Insertion
    • Some Examples
  • Problem 4: Partitioning Vectors
  • Problem 5: Java vs. C
  • Problem 6: Exponentiation
  • Problem 7: How Complex is Complex?
  • Problem 8: Copying Strings
  • Problem 9: Weakest Preconditions of Sequences
• Some Questions and Answers
• Errors

Preliminaries

There are nine problems on the exam. Some problems have subproblems. Each full problem is worth 11 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 eight to twelve hours, depending on how well you've learned topics and how fast you work. I would 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 three points of extra credit to the first two people who honestly report that they've spent at least nine hours on 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. 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: Reading Lines

Write a procedure, readLine(file, str, max), that reads one line of text from file into str. It should stop reading when one or more of the following holds: max-1 characters have been read, the end-of-line character has been read, or the end-of-file character has been read. It should not store either end-of-line or end-of-file in the string. It should put a 0 at the end of the string. You may only use getc to read characters.

If a complete line was read, readLine should return 1. Otherwise, it should return 0.

When evaluating your answer, I will look at conciseness in addition to correctness (although it is clearly better to be correct than concise).

Problem 2: Reading Lines, Revisited

Rather than reading into an existing string, it is often useful to build a new string for each line read. Assume that the values are input in such a way that each line begins with an integer that gives the number of characters in the rest of the line. For example,

5Hello
16Once upon a time
0
4SamR

Write a rdln(file) procedure that allocates, reads, and returns a string that corresponds to the text on the current input line.

For example

  char *alpha;
  char *beta;
  alpha = rdln(file);
  beta = rdln(file);
  printf("Alpha: '%s'; Beta: '%s'\n", alpha, beta);

Problem 3: Specifying Insertion

A typical insertion sort procedure for arrays of integers steps through the indices of the array, inserting each value into the sorted subarray of previous values. That is, insert(arr, pos), inserts the value at position pos in the subarray at positions 0 through pos-1, expanding that subarray into position pos.

For example,

void insertionSort(int values[], int len)
{
  int i;
  for (i = 0; i < len; i++)
    insert(values, i);
} /* insertionSort(int[], int) */

Document as carefully as you can the preconditions and postconditions for insert.

Some Examples

Suppose we start with the following array

We start by inserting the value in position 0 (94) into the empty subarray in positions 0..-1. That operation has no real effect.

Next, we insert the value in position 1 (63) into the subarray that contains only [94]. We need to put the 63 before the 94 and shift.

Next, we insert the value at position 2 (42) into the subarray [63,94]. We need to shift both values to make room for the 42.

As we continue, we now need to insert the value at position 3 (71) into the subarray [42,63,94]. In this case, we only need to shift one value (the 94).

As we insert the 81 at position 4, we once again need to shift only one value.

Inserting the 95 at position 5 is comparatively simple. We don't really need to do anything.

Inserting the 32 at position 6 requires us to shift all of the other values.

Inserting the 11 at position 7 again requires us to shift all of the other values.

Inserting the 13 at position 8 requires us to shift most, but not all of the values.

Finally, inserting the 48 at position 9 requires us to shift some of the values.

And we're done sorting.

Problem 4: Partitioning Vectors

Here is an incorrect implementation of the partition procedure that Quicksort typically uses. It assumes that an appropriate pivot has been put in values[lb]. It returns the position in which it places the pivot.

int swap(int values[], int i, int j)
{
  int tmp = values[i];
  values[i] = values[j];
  values[j] = tmp;
} /* swap(int[], int, int) */

int partition(int values[], int lb, int ub)
{
  int start = lb;
  int pivot = values[lb++];
  while (lb <= ub) {
    while (values[lb] <= pivot) 
      ++lb;
    while (values[ub] > pivot)
      --ub;
    swap(values, lb, ub);
    ++lb;
    --ub;
  } /* while */
  swap(values, start, lb);
  return lb;
} /* partition(int[], int, int) */

a. What's wrong with this implementation of partition? Note that you cannot just present a correct implementation; you must identify flaws in the implementation.

b. How might (or did) careful use of preconditions and postconditions have helped identify those errors? Be as specific as you can.

Problem 5: Java vs. C

Suppose you were asked to teach C to a Java programmer. What two key differences between C and Java would you most emphasize? Argue that those are the appropriate ones to emphasize.

You should write about one paragraph (at least three sentences, no more than ten) for each difference.

Problem 6: Exponentiation

Here's a recursive way to think efficiently about exponentiation.

x⁰ = 1
x^2k = (x^k)²
xⁿ⁺¹ = x*xⁿ for even n

Implement this efficient exponentiation procedure iteratively in C. The running time of your algorithm should be in O(log₂n).

Problem 7: How Complex is Complex?

a. Define a complex struct that contains the two parts of a complex number (that is, a real part and an imaginary part).

b. Document, implement and test a cmult procedure, which multiplies two complex numbers and returns their product.

Problem 8: Copying Strings

Implement strncpy as concisely as you can. You may not call the built-in strncpy.

Problem 9: Weakest Preconditions of Sequences

Programmers typically assume that it doesn't matter whether the sequence S1 ; S2 ; S3 is interpreted as (S1 ; S2) ; S3 or as S1 ; (S2 ; S3). Gries even makes a statement to this effect in his discussion of the weakest precondition of instruction sequences.

Verify this assertion by showing that wp(((S1 ; S2) ; S3), P) is the same as wp((S1 ; (S2 ; S3)), P) .

Some Questions and Answers

These are some of the questions students have asked about the exam and my answers to those questions.

On problem 6, you give an elaborate description of the recursive definition of exponent. However, we are supposed to write the procedure iteratively. I was just wondering if we are actually supposed to write it iteratively.

Yes, you are supposed to write it iteratively. I gave the recursive definition because that's the more natural one. You'll need to think about how to make that strategy iterative.

On problem 2, could you elaborate on how the string is supposed to be returned? Are we supposed to print the string out in stdio or are we supposed to return the pointer to the string?

You are supposed to return the new string (which is a pointer to a character).

Can you explain more about the insert procedure on problem 3?

Positions 0 through pos-1 contain a sequence of integers in order. Position pos contains another integer. insert finds the right place for the integer in position pos and inserts it there. There is now an example in that problem.

Errors

Each error identified by any student counts as one point of extra credit for everyone in the class. This form of extra credit has a limit of five points.

• Referred to a non-existent set of guidelines for lab writeups. [WB 1 point]
• Corrected a spelling error in the previous correction. [LK 1 point]
• Updated the recursive definition of exponentiation.