Exam 2: Intermediate C

Assigned: Tuesday, 8 March 2011
Due: 11 p.m., Thursday, 17 March 2011

Preliminaries

Exam Format

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.

There are four problems on this examination. You must answer all of them. The problems are not necessarily of equal difficulty. Each problem may include subproblems. Four correct or mostly-correct solutions will earn you an A. Three correct or mostly correct solutions will earn you a B. Two correct or mostly correct solutions will earn you a C. One correct or mostly correct solution will earn you a D. Zero correct or mostly correct solutions will earn you an F. Failure to attempt the exam will earn you a 0. Partially correct solutions may or may not earn you a partial grade, at the discretion of the grader.

Read the entire exam before you begin.

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. In particular, this exam is likely to take you about five hours, depending on how well you've learned the topics and how fast you work. You should not work more than eight hours on this exam. Eight hours of work, documented attempts on all problems, and a signed statement that There's more to life than computer science will earn you at least a C on this exam.

I would also appreciate it if you would write down the amount of time each problem takes. Doing so may earn you a modicum of extra credit.

Academic Honesty

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 as restricted by 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. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. And, in case it's not clear, you may not ask others (in person, via email, via IM, by posting a please help message, or in any other way) to put answers on the Web.

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 include both of the following statements on the cover sheet of the examination.

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.

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. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

Presenting Your Work

You must present your exam to me in two forms: both physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, put your name on the top of every page, and hand me the printed copy. You must also submit an electronic copy of your exam. You should create the electronic version by making a tarball of any relevant code and submitting that tarball on Pioneerweb. Failure to name and number the printed pages will lead to a penalty. Failure to turn in both versions may lead to a much worse penalty. Failure to turn in a legible version of the exam is also likely to lead to a penalty.

If your answer relies on provided files but you have not modified the files, you should include them in the tarball but should not include them in the printed copy of the exam.

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 do your best to format that code to GNU coding standards.

Unless I explicitly tell you to document a procedure, you need not document that procedure. If I do tell you to document a procedure, you should document it with six-P style documentation. If I do not tell you to document a procedure, you may still document that procedure and may use whatever form you find most appropriate.

Just as you should be careful and precise when you write code and documentation, 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 may give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

Getting Help

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. You should also feel free to send me electronic mail at any time of day.

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.

Problems

Problem 01: What Does It Do?

Topics: Code reading, Commenting, Formatting

Hannah and Harvey Hacker don't particularly like all the extra stuff they think I make them do when writing code. In particular, they don't see the point to clear variable names, standard formatting, or comments. They say Our goal is to write code that works efficiently. Why should we care about the rest?

Recently, they sent me the following code. As you may note, they've been a bit aggressive in avoiding my recommendations.

void s (int x[], int y, int l[], int k, int r[], int q) { int i; for
(i = 0; i < k; i++) l[i] = x[i]; for (i = k; i < y; i++) r[i-k] = x[i];
} void m (int x[], int y, int l[], int k, int r[], int q) { int a = 0;
int b = 0; int c = 0; while ((a < k) && (b < q)) x[c++] = (l[a] < r[b])
? l[a++] : r[b++]; while (a < k) x[c++] = l[a++]; while (b < q) x[c++] =
r[b++]; } int h (int x[], int y) { int k = y/2; int q = y - k; int l[k];
int r[q]; if (y <= 1) return y; s (x, y, l, k, r, q); h (l, k); h (r,
q); m (x, y, l, k, r, q); return k + q; }

They've even provided a header file (even though they don't use it).

#ifndef __HHH_H__
#define __HHH_H__

int h(int x[], int y);

#endif // __HHH_H__

Rewrite the code so that it meets my standards. That is, reformat it, choose good names for variables and functions, use mnemonic constants when appropriate, and add comments to help the reader.

You may find the following command-line tester helpful.

/**
 * hhh-ui - a simple UI for the strange code produced by H & H H.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <stdlib.h>
#include "hhh.h"


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

void
print_ints (int nums[], int size)
{
  int i;        // Index variable

  // Special case
  if (size == 0)
    {
      printf ("{}");
      return;
    }

  printf ("{%d", nums[0]);
  for (i = 1; i < size; i++)
    printf (",%d", nums[i]);
  printf ("}");
} // print_ints


// +------+-----------------------------------------------------------
// | Main |
// +------+

int 
main (int argc, char *argv[])
{
  int i;                // Everyone's favorite index
  int size = argc-1;    // The size of the number array
  int nums[size];       // A bunch of numbers
  int result;           // The result of h.

  // Convert arguments to numbers
  for (i = 0; i < size; i++)
    nums[i] = atoi (argv[i+1]);

  // Print preliminary information
  printf ("Original array: ");
  print_ints (nums, size);
  printf ("\n");
  printf ("Size:           %d\n", size);

  // Do the work
  result = h (nums, size);
 
  // Print the results
  printf ("Result:         %d\n", result);
  printf ("Final array:    ");
  print_ints (nums, size);
  printf ("\n");

  // And we're done
  return 0;
} // main

Problem 02: Testing the Testers

Topics: Testing, Binary search, Sorting

Bif and Bitsie Binsearch have been studying binary search and the ways in which we might use it. They note that

In order for binary search to work, the array must be in order from smallest to largest.

Being good students, Bif and Bitsie then write a function to check this condition.

/**
 * Procedure:
 *   is_in_order
 * Parameters:
 *   values[], an array of integers
 *   size, an integer
 * Purpose:
 *   Determine if the first size values in values are in order.
 * Produces:
 *   in_order, an integer that represents a Boolean
 * Preconditions:
 *   0 <= size <= length of values
 * Postconditions:
 *   If values[i] <= values[i+1] for all reasonable i, then
 *     in_order is true (1).
 *   Otherwise, in_order is false (0).
 */
int
is_in_order (int values[], int size)
{
  int i;
  for (i = 1; i < size; i++)
    if (values[i] >= values[i+1])
      return 0;
  return 1;
} // is_in_order

Their colleagues, Terry and Terry Tester suggest that while this function will make some things easier, if is_in_order is not implemented correctly, then it's pointless to have it, and it won't ensure that binary search can be applied. (Of course, you would rarely want to spend the effort checking if the array is in order, since that's much more expensive than binary search, but, hey, it's still an important function.)

How do we determine if there are errors? We write unit tests. What do we do if the unit tests fail? We try to figure out why they've failed.

a. Write unit tests for is_in_order.

b. Correct any errors that your unit tests revealed.

You should turn in two files: A file with the revised version of is_in_order and a file with the unit tests.

Problem 03: Floating-Point Exponents

Topics: IEEE floating-point representation, Bitwise operations

Flo and Flint Floater are having trouble understanding IEEE floating point representation and have come to your class mentor for help. In helping them, your mentor has decided that it would be helpful to extract the key parts of a floating point number (sign, exponent, significand).

Write a program that reads in a 32-bit floating-point number (a float) from the command line and prints out the sign, exponent, and significand.

% ./ieee-exponent 1
For float 1.000000, the sign is +, the exponent is 0, and the significand is 1.000000.
% ./ieee-exponent 2
For float 2.000000, the sign is +, the exponent is 1, and the significand is 1.000000.
% ./ieee-exponent 0.5
For float 0.500000, the sign is +, the exponent is -1, and the significand is 1.00000.

As you solve this problem, I would like you to use the following strategy.

• Convert the number from float to int without affecting the bits.
• Extract the bit that corresponds to the sign.
• Extract the bits that correspond to the exponent.
• Convert those to an unsigned integer.
• Convert that unsigned integer to a signed integer.
• Extract the bits that correspond to the significand.
• Convert those bits to a float.
• Print out the result.

To convert from float to int while preserving the bits, you can use the following procedure. (No, you need not understand how the procedure works.)

int
f2i (float f)
{
  return *((int *) &f);
} // f2i

Problem 04: atoi, Revisited

Topics: Strings, Integers, Library functions

Pam and Pat Parser need to use the atoi function to solve some homework assignments. Since they feel their understanding of atoi is incomplete, they've written the following program.

/**
 * atoi args
 *   Applies atoi to each of its parameters and prints out the results.
 */

#include <stdio.h>
#include <stdlib.h>

int
main (int argc, char *argv[])
{
  int i;
  for (i = 1; i < argc; i++)
    printf ("'%s' => %d\n", argv[i], atoi (argv[i]));
  return 0;
} // main

When they run it, they get some output that doesn't make sense.

$ ./atoi 23 033 0x44 hello 111111111111
'23' => 23
'033' => 33
'0x44' => 0
'hello' => 0
'111111111111' => 2147483647

As this output suggests, atoi does not seem to work well with either octal or hexadecimal numbers. It also does not do well with integer overflow. And it gives no error message if there's an error.

Write a new version of atoi that resolves these problems. In particular, you should support octal and hexadecimal numbers. If an error occurs (e.g., overflow, invalid input) you should return INT_MIN and set the shared variable atoi_error.

Here's a revised version of the Parser's program that takes advantage of this new interface.

/**
 * atoi args
 *   Applies atoi to each of its parameters and prints out the results.
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

extern char *atoi_error;

int
main (int argc, char *argv[])
{
  int i;
  int result;
  for (i = 1; i < argc; i++)
    {
      result = atoi (argv[i]);
      if (result == INT_MIN)
        printf ("Could not parse '%s' because '%s'\n", argv[i], atoi_error);
      else
       printf ("'%s' => %d\n", argv[i], result);
    } // for
  return 0;
} // main

And here's some simulated output.

$ ./atoi 23 033 0x44 hello 111111111111
'23' => 23
'033' => 27
'0x44' => 68
Could not parse 'hello' because 'not a number'
Could not parse '111111111111' because 'integer overflow'

Questions

Here you will find answers to questions of general interest. Please check here before emailing me your questions!

Problem 1

Did you really write the code in this ugly way? [2011.03.08]

No. I wrote nice code, and then used some programs to make it ugly. Otherwise, there was no way I could check for errors.

Can you explain your process for uglifying code? [2011.03.08]

I'll add notes later.

Can you undo it? [2011.03.08]

There's no way to undo the stripping of comments. I haven't tried to write a program to undo the rest, but I think I can.

What's the point of the command-line tester? [2011.03.12]

You can link it with their code to try to see what their code does.

Should we write code that is as carefully structured as yours? [2011.03.12]

You should try.

Should one of the functions s, m, or h be converted to main? [2011.03.14]

Definitely not. None of them have the right parameter types. I've provided a separate file with the main method. You should save that as a separate file (e.g., h-expt.c) and compile the two together.

Problem 2

Can we pass non-numbers to the procedure? [2011.03.13]

Unit tests need only verify that the procedure works correctly when given correct inputs.

What should happen with the array ['a', 'b', 'c']? [2011.03.13]

Since a character is just an integer, this is the same as the array [97,98,99], and is in order.

Is an array with duplicate numbers, such as [0,1,1,2,3] in order? [2011.03.14]

It's up to you, as long as you document it.

What should we turn in for this problem? [2011.03.14]

Two files: A file with the revised version of is_in_order and a file with the unit tests.

How many errors should we find? [2011.03.15]

All of them.

Any hints on tests? [2011.03.15]

I would try different size lists. I would pick some small list size (e.g.., 3 or 4) and systematically pick all reasonable variants.

Problem 3

How do I read a float from the command line? [2011.03.14]

  float f;
  f = (float) atof (argv[1]);

When I call f2i, should I get an integer equal to the float? [2011.03.14]

No. Since we're just telling C to reinterpret the bits, we'll get a very different value. For example, if the float is 1.0, the integer will be something like 1065353216. If the float is 2.0, the integer will be something like 1073741824. You may want to look at this sample code.

Problem 4

Do we have to support negative hex and octal numbers?

No.

.

Miscellaneous

Can we get extra credit for errors in the Q&A section or the errata section?

Certainly not.

There's a TC origami competition on the evening of Thursday, 17 March 2011. I'd really like to go, but I worry about its effect on my ability to complete the exam on time. What should I do? Spring break starts Friday afternoon, so I don't mind getting insufficient sleep. [2011.03.07[

If you attend the TC origami competition, you may have an extra two hours to complete the examination.

Can you explain this really weird error message I get from the compiler? [2011.03.14]

Certainly. Please send me your .c files, your .h files, and your Makefile.

Errata

Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. We usually limit such extra credit to five points. However, if I make an astoundingly large number of errors, then I will provide more extra credit.

• A bug in the HTML resulted in Problem 3 showing up incorrectly. [EL, 1 point]
• In problem 3, will things easier should be Will make things easier. [RL, 1 point]
• The output for problem 3 was hand-generated, and had an error. [KS&CT, 1 point]
• 0x44 is 68, not 67. [CT, 1 point]
• Problem 2 was misnamed. [SR, 1 point]

• Problem 2: Incorrect bound on size. [CA, 0 points]