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,
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:
- 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.
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:
- 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.
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:
- 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 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
- 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
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 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 these kinds of small problems, the best method of explanation is
comments in the source code.
- 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.
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.
- 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.
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:
- 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?
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
- 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?
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.
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 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.
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:
- 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
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.
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.
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