COMP 40: Details

Prerequisites

You must grasp basic algorithms, data structures, and good programming practice. Moderate proficiency in either C or C++ is required. In particular,
  • You should have experience with implementation and use of binary search trees, hash tables, and linked lists.
  • You should be comfortable working with stacks and queues.
  • You should be able to write a recursive function (or procedure or method) and explain why it terminates.
  • You should have mastered the ability to write, organize, and document a 250-line program in C or C++.
  • You should have some practice writing, organizing, and documenting a 500-line program in C or C++.
  • You should have written programs that use new and delete (C++) or malloc and free (C).
  • If you have successfully taken COMP 15 at Tufts, it should have provided you with the experience and skills you will need. If not, you will need the instructor's permission to take COMP 40. Students in the bachelor-certificate program or other graduate programs will be granted permission provided they are confident they can make up any missing material.

    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:

    If you have these habits, the other prerequisites are almost irrelevant. If you don't, you can expect to have difficulty no matter what your background.

    Interactions are Expected

    Engineering is not a solitary profession. To maximize your chances of success in 40 and beyond, I have designed a number of interactive experiences into the class:

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

    Homework is critical

    In this class, you will learn most of the material on your own as you complete the homeworks and labs. The importance of homework is reflected in the
    weight it is assigned. Many students get stuck on homework; if you get stuck, here are some things it is useful to know: If you get stuck, seek help early. In a large course, your difficulties could be overlooked until they get out of control. Keep an eye on yourself, and remember that a short conversation during office hours or lab can save hours of aimless frustration.

    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

    Your written work must carry your name, and it must be neat and well organized. Use a computer to prepare your written work if you can. Any work that cannot be read easily will earn No Credit. Clear English expression is required; grammar and spelling count. The same requirements apply to exams.

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

    Extra Credit

    Some homework assignments will offer opportunities to earn extra credit. Extra credit on homework is independent of the ordinary grade for that assignment; extra credit cannot turn Good work into Very Good or Very Good into Excellent. (Were it otherwise, giving extra credit would amount to nothing more than a sneaky way of assigning more homework.) I use extra credit to adjust final letter grades. For example, if your final grade falls in the borderline between A– and B+, extra-credit work will help me assign you the higher grade. I will also mention extra credit if I write you a letter of recommendation.

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

    Clarity of programming assignments

    A solution to a problem is of little value if that solution cannot be understood and modified by others. For that reason, your homework will be graded on your presentation of what you are doing as well as your results. For many homeworks, especially those involving substantial programming, half of your grade will be based on presentation. Presentation encompasses the structure and organization of your code as well as comments and other documentation.

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

    For these kinds of small problems, the best method of explanation is comments in the source code. For these larger problems, you must describe your thinking at least as well as your code. These kinds of long explanation should be in the README file, not in the code itself. It is as bad to write too much explanation for a simple solution as to write too little explanation for a complex solution.

    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.

    Good style normally includes using library functions where possible, instead of duplicating effort by re-implementing something yourself. However, some libraries have such complex interfaces that you may be justified in avoiding them; when in doubt, ask the course staff.

    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:

    Large-scale documentation is usually not a good place to list a lot of information about the names of functions and their arguments and other low-level details that are most easily understood in the context of reading the code.

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

    Please don't use comments to repeat information that is readily available in the code. Here is an example of poor style:
    /* (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;
    }
    
    Everything in the comment is more easily learned just by looking at the code.

    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);
         ...
      }
    }
    
    The comment explains what the function is doing, notes that there are side effects, and explains what the parameters mean. The comment also explains why the function terminates; the key phrase is ``structural recursion.'' This comment should be supported by comments on the global variables output and visited, saying what they represent and what the representation invariants are.

    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

    Code you submit must be accepted by the appropriate compiler without errors or warnings. If you are using gcc, use these options:
      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
    
    Very important single-line comments, and all multiple-line comments, should look like this:
       /*
        * 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

    Professional engineering is a collaborative endeavor. And yet, while you are a student, you earn an individual grade. To balance these competing concerns, we support

    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:

    While we strongly encourage both discussion and pair programming, your course staff is also charged with guarding Tufts's standards of academic integrity. The following policies will help ensure that these standards are upheld:

    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:

    If I find it necessary to revoke your pair-programming privileges and you believe I have done so unfairly, you may appeal to the department chair.

    Using the library and the Internet

    You may look in the library (including the Internet, etc.) for ideas on how to solve homework problems, just as you may discuss problems with your classmates. Library and Internet sources must be acknowledged when you submit your homework, even if you find little or nothing useful.

    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

    All homework will be submitted electronically and will be due at the 11:59 PM on the due date. We will grant an automatic extension of ten minutes at no cost to you, so the real deadline is 12:09 AM the following day. If you plan on submitting your work at midnight, you will have nine minutes for last-minute changes.

    Homework is expected to be submitted on time. However, we recognize that the exigencies of college life occasionally interfere with on-time submission. If you have difficulty getting homework in on time, you have two options:

    Solutions to homeworks will not be placed on the Web until the last assignment is turned in or until the 48-hour deadline has passed. Students turning homework in on time may have solutions sent to them by sending a request to the course staff.

    Regrading

    If we have made a mistake in grading a homework assignment, you have seven days after the return of the assignment to call the mistake to the attention of your TA or instructor. In such cases, we will reassess the entire assignment and assign a new grade. The new grade may be higher or lower than the original grade.

    Submission and automatic validation

    We expect to provide a submission script for each assignment. By executing
    use comp40
    
    you ensure that these scripts are on your execution path. It is very convenient to put this line in your .cshrc or .profile file, but to work around a bug in use (still present as of 6 September 2010) you will need the line
    use comp40 > /dev/null
    
    Without the redirection to /dev/null you may have difficulties with scp, ssh, git, VNC, or rsync.

    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

    To reach the course staff, write to comp40-staff@cs.tufts.edu. Also, be sure that you are signed up for the class mailing list, which is comp40-everyone@cs.tufts.edu. You can register online (or if you drop the course, you can remove yourself), at https://www.eecs.tufts.edu/mailman/listinfo/comp40.
    Please do not email the course staff directly to their personal accounts.

    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

    This class has a mandatory 75-minute laboratory session. Each session will be guided by the class instructor or a teaching assistant. Our objective is to get you launched on a problem by providing 75 minutes of guidance and real-time feedback. If we can manage to reserve the room, we will do our best to have office hours immediately following lab.

    Handouts

    All class handouts should be available from the class web page.

    Computer software and accounts

    The class will be run using Red Hat Enterprise 64-bit Linux, as installed on the departmental servers and in the laboratory in Halligan 118. For remote access use linux.cs.tufts.edu. For some assignments you will need to use machines in Halligan 118; you can get there from the servers via
      ssh lab118x
    
    where x stands for the letter a, b, c, and so on. Please be considerate of others using the machine at the console; for information about who may be using a machine, try the
    who command.

    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.


    Back to the class home page