COMP 40: Details

You need some Unix experience. You must understand the basics of files, directories, creating and editing files, printing, and compiling programs. You will be much, much happier if you also can write a simple shell script (sh, ksh, or bash) and use Awk and grep effectively. Kernighan and Pike cover these topics at the appropriate level; the book is on reserve at the library.

This course uses the 64-bit instruction-set architecture of Intel Core 2 Duo, which may be the most complicated architecture money can buy. To avoid spending many, many hours thrashing out written assignments, you must have or develop the ability to identify relevant information buried in a sea of irrelevant detail. Your course staff will help as we are able.

The most important prerequisites for this course cannot be taught. To do well in this or any other systems course, develop these habits:

• Think carefully about a problem before you begin to write code.
• When having difficulty writing code, stand up, walk away from your computer, and think about the difficulty.
• Never be satisfied with a ``working program,'' but strive for the simplest, clearest, most elegant implementation.

Interactions are Expected

• Lecturing is at best moderately effective at helping students develop new skills. Also, typical people cannot devote sustained attention to a continuous 75-minute lecture. Class time will therefore be divided between lecture and small-group activites designed to foster active, collaborative learning. Although nobody is expected to attend every class, you must normally come to class and participate in small-group activities.

• Part of your job as a student is to get to know some of the faculty. To help you with this part of your education, I count up to five minutes of office-hour visits as part of your course grade. Each minute you spend in conversation with me during my office hours will earn one percent of your overall course grade, up to a possible total of five percent. While you may find it helpful to talk about homework, 40, engineering, or Tufts overall, any mutually agreeable topic of conversation is acceptable. (I find the Red Sox disagreeable, but I will talk endlessly about the Patriots.) To earn your five percent, you must come to my office hours by the end of October.

• In the real world, computer programming is rarely a solitary activity. The solitary programmer is often alienated and unproductive, and his or her output has repeatedly been shown to be inferior to the work produced by programmers working in groups. COMP 40 will therefore provide you with some instruction in and opportunity to practice pair programming (more at Wikipedia). Every student will be expected to use pair programming for most assignments. By the terms of our accreditation, you must use pair programming for at least two assignments. And no single pair may do more than three assignments together. At need, course staff will help students form pairs.

Spontaneous interactions may be welcome or unwelcome depending on the interaction:

• A particularly useful form of interaction is the question asked in class. Questions are always welcome; if you have a question, chances are other people in class have a similar question. Ask it! One question that is always legitimate is "why are we doing this?"

• A particularly pernicious form of interaction is the telephone call. During class, please put your cell phone on vibrate. If you must take a call, please leave the classroom immediately and do not return until you have finished your phone call.

• What Hanson has already implemented for you that you don't have to implement again
• How to use Hanson's data structures and how his T convention works, where a name is defined to be a pointer to an incomplete struct
• How to write a compile script that compiles and links against Hanson's libraries
• How to compile and linking against course software, without having your own private copy
• That C strings are not at all like C++ strings! C strings can't be compared using pointer equality!
• How to do file I/O in C (printf, fopen, fgets, fwrite, and all that)
• How a C struct differs from a C++ struct
• How to program with void * pointers and function pointers
• How to use typedef
• A little bit about the C macro preprocessor, especially the conventions Hanson uses for #ifdef, #define, and typedef

If you complete and understand all the homework assignments, you are almost certain to do well on the exams and earn a high grade. If you miss assignments or don't really understand the homework, it will be difficult for you to earn a satisfactory grade. Extensive details about grades are available online.

Format of homework

Each programming assignment must begin with a comment sheet, README file, or introductory section, which must describe the project. This description must

• Identify you by name (and on the first assignment, please tell me how to pronounce your name—my name is pronounced NORE-mun RAM-zee).
• Identify what aspects of the project have been implemented correctly and what aspects have not been implemented correctly.
• Identify anyone with whom you have collaborated or discussed the assignment.
• Identify what parts of the assignment were done using pair programming, if any, and with whom you were paired.
• Say approximately how many hours you have spent completing the assignment.

Extra Credit

Extra credit is just that: extra. It is possible to earn an A+ without doing any extra credit.

Clarity of programming assignments

In your comments and other documentation, find a way to explain your work that is appropriate to the size of the problem.

• For a trivial solution of a few lines of code, it may be best to have no explanation at all. (We're not entering the Obfuscated C Contest!)
• For a solution of a dozen lines of code, a sentence or two is usually sufficient.

• For a solution of a hundred lines or more, I would expect several paragraphs of explanation. The explanation should cover not so much the code itself, but the organization of the code and the plan that produced it.
• For larger programs, especially programs that are divided into multiple files, it is appropriate to use a design checklist, some elements of which should be used to explain your work.

Good programming style and documentation are essential ingredients in a clear and readable assignment. Good style includes the use of functions, modules, and abstract data types where appropriate.

• Document every representation, with special attention to run-time invariants.

• For all but the smallest problems, divide your own code into files, using the interfaces and implementations style. Use the slogan "every module hides a secret".

• Choose appropriate names for functions and variables:
  • Exported names should be long enough to be descriptive, like Seg_addhi.
  • Private names, including the names of parameters, can be shorter, but the should still be descriptive, like add.
  • For short-lived temporaries, use C's conventions for one-letter names: i for index, n for integer, s for string, p for pointer, and so on.

Choose algorithms appropriate to the task at hand, and make your code structured and easy to read. Good use and placement of documentation is vital. Lots of comment text does not necessarily mean good documentation. Documentation should should focus on high-level issues such as design and organization, data representation, and data invariants. Even programs that run perfectly will receive low grades if they have poor documentation.

Documentation is a deep topic in its own right, which I am not prepared to address comprehensively. The essentials of good documentation are described in a handout called How to Write Documentation for COMP 40, which is available online. Some other suggestions follow.
Good large-scale documentation should answer such questions as:

• What are the major data structures and their representations?
• What are the important invariants of the data structures?
• What are the preconditions and postconditions of the operations?
• What algorithms are used, if any?
• Why is the implementation correct?
• Why does it terminate?

Small-scale documentation (comments in the code) should say

• What are the arguments of the most significant procedures? For example, is a list of edges the list of all edges in the graph or the list of edges not yet visited?
• What does each variable represent? (Aside from trivial variables like loop indices)
• If any code is tricky (e.g., you had trouble getting it right the first time), what are the local invariants? What are the pre- and post-conditions of the procedures? What invariants apply to loops or recursive calls?

/* (example of poor commenting style)
 *
 * Function: caar
 * Description: Returns second element of a list
 */

void *caar(List_T list) {
  assert(list && list->rest);
  return list->rest->first;
}

Here is an example of better style:

/* (example of better commenting style)
 * 
 *  Visit vertex v and every successor of v that appears in 'edges',
 *  in depth-first order.  Executed for side effects on the global 
 *  variables output and visited.
 *  'graph' is the complete list of edges in the graph; 
 *  to guarantee termination, we use structural recursion on edges.  
 */

void dfs_visit(Graph_Vertex v, List_T edges, List_T graph) {
  ...
  if (edges != NULL) { 
     ...
     dfsvisit(mumble, edges->rest, graph);
     ...
  }
}

Here are three examples of very poor commenting style:

   ++i;   /* Use the prefix autoincrement operator to increase i by one. */

   for (;;) {   /* Infinite loop. */

   //Print results to standard output.
   fprintf(stdout,"%.3f \n", result);

Here is a good rule of thumb: in a well-designed function, the only comments are those that document the meanings of variables or the invariants of loops. The actual statements (control structures, assignments, and calls) should need no comments at all.

You may write documentation using appropriate comments and a README file, or you may wish to follow the example set by Hanson and use the noweb tool for literate programming. Literate programming provides a way to mix code and documentation freely, then extract the code automatically. If you use a literate-programming tool, you may not need a separate README file.

Guidelines for coding style

  gcc -std=c99 -pedantic -Wall -Wextra -Werror

A program that dumps core without a meaningful error message earns No Credit. "Segmentation fault" is not considered meaningful; an assertion failure or an uncaught exception is considered meaningful.

To earn a grade of Very Good or better, code must run under valgrind without leaks or errors. To earn a grade of Good or better, code must run under valgrind without errors.

Your code must not wrap when displayed in 80 columns.

In C, most single-line comments should look like this:

   /* I am an acceptable single-line comment. */

   // I am also an acceptable single-line comment, but I am not preferred

   /*
    * I am a multi-line comment.  My indentation should match the indentation
    * of the code that surrounds me.
    */

A comment on the declaration of a variable or other comment on one line of code should almost certainly use the C99 // comment convention:

  int nvisited = 0;    // number of pixels in visited map

We emphasize readability and clarity, but we do not enforce any particular coding style. TAs will, however, downgrade work that they find obscure or difficult to read.

Collaboration

• Wide but shallow collaboration when discussing ideas and problems
• Deep but narrow collaboration when creating and debugging computer programs

Wide but shallow collaboration means that while you are striving to understand a problem and discover possible paths to its solution, you are encouraged to discuss the problem and your ideas with friends and colleagues—you will do much better in the course, and at Tufts, if you find people with whom you regularly discuss problems. When the time comes to write code, however, group discussions are no longer appropriate.

Deep but narrow collaboration means pair programming. In pair programming, you work with a partner under the following constraints:

• When work is being done on the program, both partners are present at the computer. One partner holds the keyboard; the other watches the screen. Both partners talk, and the keyboard should change hands occasionally.

• You submit a single program (or design) under both your names. That work gets one grade, which you both receive.

• Every source of assistance must be acknowledge in writing. This rule applies to discussions with classmates or course staff as well as assistance you might find in the library or on the web. There is never a penalty for seeking help with a problem, but help must be acknowledged.

• If circumstances, such as scheduling difficulties, make it impossible for you to work as part of a pair, you may ask the course staff for permission to divide an assignment into parts and to do some parts as a member of a pair and other parts as an individual. Such parts must appear in different files, and each file must be clearly identified as the work of an individual or the work of a pair. Work done jointly by the pair should be submitted by both members of the pair. Files containing joint work must be identical. If you as an individual modify a file containing joint work, and you submit the modified file, that act will be considered a violation of academic integrity.

• It is never acceptable to divide an assignment into parts and have some parts done by one partner and other parts done by the other. Submitting work done by someone else as your own will be considered an egregious violation of academic integrity. Submitting individual work as the product of pair programming is also a violation of academic integrity.

  (If your partner disappears in mid-project, the correct procedure is submit the work done in partnership at that point, even if it is incomplete or broken. You may then follow up with an additional submission of whatever you complete on your own.)

• Unless you are working with another student as part of a programming pair, it is not acceptable to permit that student to see any part of your program, and it is not acceptable to permit yourself to see any part of that other student's program. In particular, you may not test or debug another student's code, nor may you have another student test or debug your code. (If you can't get code to work, consult a TA or the instructor.) Using another's code in any form or writing code for use by another will be considered a violation of academic integrity.

• You are encouraged to submit general programming questions to online forums such as Stackoverflow. Questions about particular homework problems must never be posted online—send mail to the course staff.

  We recommend that you use Stackoverflow and have provided detailed guidelines about how to use it in a way that maintains your integrity and respects the norms of the Stackoverflow community. Please also be aware of the Stackoverflow community guidelines for homework questions.

Finally, be aware that pair programming is a privilege, not a right. If you foul up and don't fix it, I may revoke your pair-programming privileges. Fouling up consists in any of the following unacceptable behavior:

• Repeatedly failing to keep appointments with your partner
• Lying to your partner about what you have done
• Violating academic intergrity
• Other similarly egregious offenses

Using the library and the Internet

Some students rely heavily on the external sources. Although this is permitted within the letter of the rules, I discourage it. I assign homework problems not because I want to know the answers, but because doing homework is the best way for you to learn. While library skills are important in our profession, the homework in this course is designed to develop other skills that are even more important. Remember, you will not have the library with you when you go on job interviews!

Late Policy

• For ordinary difficulties, each student is automatically issued five ``extension tokens.'' By expending an extension token, you can get an automatic 24-hour extension on all deadlines associated with a single assignment. For example, if a design document is due Tuesday and code is due Friday, expending a single extension token makes the design document due Wednesday and the code due Saturday.

  Expenditure of extension tokens is governed by these rules:

  When expending an extension token, you must notify the course staff. We must receive this notification before the assignment is due. (Notification ensures that we don't post solutions before all homework is in.)
  At most two extension tokens may be expended on any single assignment. This rule enable us to post solutions in a timely manner.
  When you are out of tokens, late homework will no longer be accepted. It will be returned ungraded, and you will receive No Credit for the work.

• For extraordinary difficulties, such as serious illness, family emergencies, or other extraordinary unpleasant events, your first step should be to make contact with your associate dean for undergraduate education. You must take this step before the assignment is due. Ask your dean to drop me an email or give me a call, and we will make special arrangements that are suited to your circumstances.

Regrading

Submission and automatic validation

use comp40

use comp40 > /dev/null

A submission script is named submit40-name, so for example the submission script for the first assignment is called submit40-intro. Normally you should change to the directory in which you have placed your solutions and run the script. Most submission scripts compile your programs and check for compiler warnings or errors. If you get a warning while submitting, fix the errors (i.e. missing files or non-compiling code) and resubmit.

We encourage you to submit work early and often, even if it is incomplete, so that you have may have an independent check that what you plan to submit is what the course staff are expecting.

Questions and discussion

It is a great idea to post some kinds of questions to Stackoverflow; please follow our guidelines.

It is OK to send instant messages to the course instructor via Skype; his id is norman-ramsey.

We will make every effort to answer questions once a day, even on weekends. In the last two days before an assignment is due, we strive for even quicker turnaround. Answers to questions and other useful information will be sent to the class. Perhaps at some future point we will be able to have a web forum. Meanwhile, you can view the mailing-list archives at https://www.eecs.tufts.edu/mailman/private/comp40/. You will need your mailing-list password, which should have been emailed to you.

Labs are mandatory

Handouts

  ssh lab118x

If you need an account for CS machines, please send email to staff@cs.tufts.edu. Ask for bash as your login shell.

Source code should be available for all of the software used in the course. It will therefore be possible for you to work on some assignments using other machines; however, several assignments will definitely require access to this hardware or to other hardware that uses the same instruction-set architecture. Moreover, if we provide test binaries or other tools for you to compare your work against, they will be available only on the CS servers. When possible, we will link these binaries statically so you can use them on other 64-bit Intel Linux systems.