Exam 3: Structures, Sorting, and Such

Assigned: Wednesday, 27 April 2011
Due: 5 p.m., Friday, 6 May 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, 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. If you fail to name and number the printed pages, you may suffer a penalty. If you fail to turn in both versions, you may suffer to a much worse penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of 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 1: Deleting Elements from Lists

Topics: Linked Lists, Structures, Pointers

Code: Examples/Lists

As you may recall, we've recently been working on a new model of lists in which lists are dynamic, indexed, sequences of values. We've started to implement a variety of operations.

For some strange reason, your imaginary classmate, Della 133+ (yes, she's enough of a hacker that she legally had her last name changed to that), is particularly intrigued by the idea of deletion in lists. She decides it would be useful to have a function that deletes all copies of a string from a list.

She even writes a stub with minimal documentation.

/**
 * Delete all elements of str from lst.  Returns whether or not we
 * succeeded.
 */
int
list_delete_all (struct list *lst, char *str)
{
  return 0;     // STUB
} // list_delete_all

Document (six P's), test (unit), and write (implement) list_delete_all.

Some of your tests should be that list_delete_all appropriately frees memory. For example, suppose that mem_allocated returns M. We then add five copies of "whatever" (which does not currently occur in the list) to our list. Adding elements to a list typically allocates some memory, so the next call to mem_allocated should return some N greater than M. Finally, we call list_delete_all to delete all copies of "whatever". At this point, not only should there be no copies of "whatever", mem_allocated should once again return M.

Problem 2: Checking Permutations

Topics: Arrays, Sorting, Unit Testing

Code: Examples/Exam3/Perm

As you may recall, your imaginary classmates, Terrence and Theresa Tester, like writing unit tests. In order to test sorting routines, they know that they need two operations, one to check whether an array is sorted, and one to check whether an array is a permutation of another. (After all, sorting routines are supposed to produce arrays that are in order and are permutations of the original array.)

They produce a declaration of one version of the is it a permutation function.

#ifndef __PERM_H__
#define __PERM_H__

/**
 * perm.h
 *   Declarations for some utilities for fun with permutations.
 */

// +--------------------+---------------------------------------------
// | Exported Functions |
// +--------------------+

/**
 * Procedure:
 *   ia_is_permutation
 * Parameters:
 *   a0, an array of integers
 *   a1, an array of integers
 *   size, an integer
 * Purpose:
 *   Determine if the subarray of the first size elements of a1 is a 
 *   permutation of the subarray of the first size elements of a0.
 * Produces:
 *   is_perm, an integer representing a Boolean value
 * Preconditions:
 *   a0 contains at least size elements.
 *   a1 contains at least size elements.
 * Postconditions:
 *   a0 is unmodified
 *   a1 is unmodified
 */
int ia_is_permutation (int a0[], int a1[], int size);

#endif // __PERM_H__

Of course, as people who love testing, they write tests of ia_is_permutation, which you can find in perm-utest.c.

However, they seem to be unable to write the definition of ia_is_permutation.

Write that definition. That is, implement ia_is_permutation. You may find it useful to add tests.

While you may be tempted to decide if one array is a permutation of another by sorting both arrays and comparing the results, that strategy is inappropriate if we plan to use the function to test sorting algorithms.

Problem 3: Erroneous String Code

Topics: Strings, Lists, Memory, Segfaults, Debugging, File Input

Code: Examples/Exam3/Strings

Your imaginary colleagues, Strongheart and Struana, have had some difficulties with their string programming. They've written the following program, which seems to segfault a lot. Even when it doesn't segfault, it seems to give them strange output. For example, although they think they've read all the lines from the Makefile, they don't seem to see all of those lines.

/**
 * uc.c - Fun with uppercase.  Takes a variety of strings (from the command
 *   line, from the Makefile or stdin, elsewhere), converts them to uppercase,
 *   and then prints them out.
 *
 * Sample command:
 *   ./uc hello goodbye
 */

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

#include <ctype.h>	// For islower
#include <stdio.h>	// For fun with input and output
#include <string.h>	// For strchr

#include "list.h"	// We're working with lists


// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

// The maximum length of a string
#define MAXLEN 128


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

/**
 * Convert a string to uppercase.
 */
int
uc (char *str)
{
  static int offset = 'A' - 'a';

  // For each character in the string
  while (*str != '\0')
    {
      // If the character is lowercase
      if (islower (*str))
        // Make it uppercase
        *str = *str + offset;
      // And move on to the next character.
      str++;
    } // while

  // Return 1 to match the requirements for foreach
  return 1;
} // uc


/**
 * Print out a horizontal rule of a particular length.
 */
void
hrule (int len)
{  
  int i;
  for (i = 0; i < len; i++)
    putchar ('-');
  putchar ('\n');
} // hrule

/**
 * Print out a string on a line by itself.
 */
int
print_string (char *str)
{
  return printf ("%s\n", str);
} // print_string


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

int
main (int argc, char *argv[])
{
  struct list *lst;             // A list of strings.  
  char *line;                   // One line (for input)
  int i;                        // A favorite counter variable

  // Build the list.
  lst = list_new ();
  if (lst == NULL)
    {
      fprintf (stderr, "Could not create a list.  Giving up!\n");
      return 1;
    }

  // Add all of argv.
  for (i = 1; i <= argc; i++)
    list_append (lst, argv[i]);

  // Add some simple strings, such as our names.  Include some lc and uc
  // and non-chars.
  list_append (lst, "Strongheart");
  list_append (lst, "Strauna");
  list_append (lst, "Green Eggs and Green Ham");
  list_append (lst, "Latin@ is a *very* strange word.  I'd give it a 8.");

  // Add the empty string
  list_append (lst, NULL);

  // Add the lines of the Makefile.  (The Makefile is a file we know should
  //   be in the current directory.)
  FILE *fp = fopen ("Makefile", "r");
  if (fp == NULL)
    {
      fprintf (stderr, "Could not open the Makefile.  Giving up.\n");
      return 2;
    }
  while (fgets (line, MAXLEN, fp) != NULL)
    {
      // Drop the \n.
      *(strchr(line, '\n')) = '\0';
      // Add it to the list.
      list_append (lst, line);
    }

  // Print out all of the strings
  hrule (80);
  list_foreach (lst, print_string);

  // Convert all of the strings to uppercase.
  list_foreach (lst, uc);

  // Print out all of the strings again
  hrule (80);
  list_foreach (lst, print_string);

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

Repair their code. That is, you should not only stop the code from crashing, you should ensure that it meets the goals specified in the comments.

Problem 4: Sorting Complex Structs

Topics:: Structures, Sorting, Function Pointers

Code: Examples/Exam3/Students

Your imaginary classmates, Stu and Denton, have defined a simple struct to represent students.

struct student 
  {
    char *fname;        // First name
    char *lname;        // Last name
    char *sid;          // Student id number
    double gpa;         // Grade point average
    int debt;           // Debt to the College, in cents
  };

They even create a method that creates new pointers to student structs.

struct student *
student_new (char *fname, char *lname, char *sid, double gpa, int debt)
{
  struct student *result = (struct student *) malloc (sizeof (struct student));
  if (result == NULL)
    return NULL;
  result->fname = fname;
  result->lname = lname;
  result->sid = sid;
  result->gpa = gpa;
  result->debt = debt; 
  return result;
} // student_new

And they use that method to set up a template for a simple program that creates a bunch of students, processes them, and prints them out. (Okay, no processing currently happens.)

/**
 * student-experiments
 *   Some experiments with students.
 */

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

#include "student.h"	// Duh.
#include <stdio.h>	// For printf, stdout, and such


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

int 
main ()
{
  // Set up a group of sample students.
  struct student *class[] =
    {
      student_new ("John", "Doe", "00001234", 3.4, 0),
      student_new ("John", "Ode", "10203040", 2.0, 100000),
      student_new ("Jane", "Doe", "00001233", 3.9, 1005000),
      student_new ("Jack", "Doe", "00112233", 3.2, 234012),
      student_new ("Jan",  "Edo", "20199999", 2.7, 123450),
      student_new ("Sam",  "Are", "20199998", 1.5, 50),
      student_new ("Sam",  "IAm", "20199908", 3.5, 543210),
      student_new ("Jane", "IAm", "20199908", 3.5, 543210)
    };
  int num_students = sizeof (class) / sizeof (struct student *);

  // Do something with them.  (Say, sort them.)

  // Print them out.
  int i;
  for (i = 0; i < num_students; i++)
    {
      printf ("%2d: ", i);
      student_print (class[i], stdout);
      printf ("\n");
    } // for each student

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

Now it's time to do something interesting. Extend their program so that it is possible to sort the array of students by name (normal mechanism: prioritize last name, but go to first name if the last names are the same), student-id number, gpa, or debt. It is probably easiest if you do all four kinds of sorting. That is: Print the class, sort the class by name, print it again, sort the class by student-id, print it again, sort the class by gpa, print it again, sort the class by debt, and print it again.

I would recommend that you (a) write a sorting routine that takes a comparator as a parameter and (b) build comparators for those four sorting policies.

Here's a sample signature for your sorting routine.

void
sort_students (struct student *students[], int size, 
               int (* compare) (struct student *, struct student *));

And here's a sample comparator.

int
compare_students_by_gpa (struct student *s, struct student *t)
{
  if (s->gpa < t->gpa)
    return -1;
  else if (s->gpa > t->gpa)
    return 1;
  else
    return 0;
} // compare_students_by_gpa

Questions

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

General

Now that the CS picnic is postponed, can we turn in the exam later than 5 p.m. on Friday? [2011.01.03, 9:00 a.m.]

I still need time to grade it, so no.

Problem 1

For problem 1, do you want our implementation, unit tests, and documentation to be in list.c and list.h, or do you want us to create a new .c and .h file for list_delete_all? [2011.04.29, 16:30]

I would prefer that you do the updates in list.c and list.h. However, it would be nice if you just gave me the new code in your printed version. (Save trees!)

Can we use your node and list code? [2011.04.29, 19:30]

Certainly. Since it's an implicit part of the exam, you need not cite it.

Problem 2

Problem 3

Are the bugs in their code, or could the bugs be in uc, list_foreach, or list_append? [2011.05.01, 19:30]

You should be able to resolve all of the bugs by fixing code in main.

The code doesn't seem to be doing very well reading the Makefile. In particular, once I fix the other errors, I see lots of copies of the last line, but not the other lines. What should I do? [2011.05.03, 9:00 a.m.]

That's another problem with their code that you've identified. (There are lots, but they all mimic problems we've discussed in class.) You'll need to fix it. I'd suggest drawing a picture, stepping through the debugger, or adding annotations (printing status) to see what's going wrong.

Can you give us any more hints for the problem in general? [2011.05.03, 9:00 a.m.]

Think about the relationship between

char *str = "A String";

and

char str[] = "A String";

K&R included a picture to illustrate the difference, and we went over that picture in class.

Problem 4

Miscellaneous

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

Certainly not.

Can we get extra credit for pointing out grammatical errors in your code?

Not for the list code (which was not prepared for this class), but certainly for the other code.

Can we get extra credit for pointing out flaws in your code.

Yes.

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.

• In problem 4, there's a missing right paren in (Okay, no processing currently happens. [DF, 1 point]
• There's a missing comma on line 31 of student-experiments.c. [CJ, 1 point]
• Link to perm-utest.c was broken. [CJ, 1 point]
• student_new in the exam does not match student_new in student.c. The latter correctly includes a return statement, the former does not. [KI, 1 point]
• When Sam updated the code for liked lists to include mem.h, he did not make sure that it was only included when needed. This had an effect when compiling in the strings example. [SR, 1 point]

• "all the strings" and "all of the strings" are used in neighboring comments. Be consistent! [DU, 0 points]
• commmand should only have two ms. [CT, 0 points]