COMP 105: Details
Prerequisites
You must grasp basic algorithms, data structures, and good programming practice.
You should have substantial programming experience.
Those without such experience will have difficulty keeping up with the
homework.
Proficiency in C is needed for a few homework assignments;
if you have
a strong background in C++, some details will be different, but
your background should be sufficient.
You must have some basic mathematics (e.g., simple propositional
calculus, elementary set
theory) and must be able to prove a theorem, including proofs by induction.
You need some Unix experience.
You must understand the basics of files, directories, creating and
editing files, printing, compiling and loading programs, and using
make.
You will be much, much happier if you also can write a simple shell
script (sh) and use Awk and grep effectively.
Kernighan and Pike cover these
topics at the appropriate level.
Your programming experience should include work with dynamically
allocated data structures and with recursive functions.
You should be very comfortable writing recursive functions in the
language of your choice, as well as proving that such functions
terminate.
You should have implemented some of the basic data
structures and algorithms used in computer science, like stacks, queues, lists,
tables, search trees, standard sorts (quick, insertion, merge, heap),
topological sort, and graph algorithms.
These topics are well covered in COMP 15 at Tufts.
Prior exposure to exhaustive search (backtracking) will also be helpful.
Some students spend many, many hours thrashing out homework
assignments.
This course uses unusual programming paradigms, and the techniques you
are accustomed to may not be much help.
Although this material is not a formal prerequisite for this course,
you will be happier if you have a nodding acquaintance
with formal methods, including the following intellectual tools:
- Loop invariants and termination conditions as they apply
to imperative programs.
- Contracts for functions, including
preconditions and postconditions.
- Termination conditions for recursive functions.
When writing recursive functions, try to develop your understanding
of the deep connections between recursion and loops; the ideas of invariants
and termination conditions apply in both cases.
- Representation invariants and abstraction functions for
abstract data types.
You can brush up on this material by looking at the article by Bentley on the reading list.
Chapter 4 of Liskov and
Guttag has a nice tutorial on reasoning about data, which you will
find helpful in several assignments.
You must have taken Discrete Math (Math 22 or COMP 22).
If not, you must produce some other
evidence that you can reason precisely about computational objects.
You should be able to write an informal mathematical proof.
For example, you should be able to prove that a sort routine returns
the same set of elements that it was passed.
You should be comfortable using basic mathematical formulas with
``forall'' and ``exists'' quantifiers, i.e., the propositional and
predicate calculi, although
it will not be necessary to write formal proofs using these calculi.
You should know basic set theory, e.g., the mathematical definition of
functions as sets of ordered pairs.
You should be comfortable reading and writing formal
mathematical notation,
or at least not run screaming from the room.
The most important prerequisites for this course cannot be taught.
To do well in this or any other course that involves programming,
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 trouble no matter what your
background.
Interactions are Expected
Engineering is not a solitary profession.
To maximize your chances of success in 105 and beyond,
I have designed some interactive experiences into the class.
- 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, class, 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.)
-
Much of the programming in 105 is about your own individual
understanding of new language features and new ideas, and you will
tackle this sort of programming on your own.
But sometimes you will have the opportunity to build something more
substantial.
And in the real world, substantial artifacts are seldom built by
individuals working alone.
COMP 105 will therefore provide you with some
opportunity to practice
pair programming
(more at Wikipedia).
You will have the opportunity to practice pair programming on selected
problems throughout the term.
No single pair may work together on more than three assignments.
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
homework assignments.
The importance of homework is reflected in the weight it is assigned.
Most homework for this course involves short programming assignments.
Many of them will be based on the text by
Ramsey and Kamin.
There will be also be some larger programming assignments.
There will be some theory homework, involving more proving
and less programming.
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.
If you can,
use a computer
to prepare your written work.
Otherwise, write it by hand and scan it.
Any work that cannot easily be read will receive No Credit.
Clear English expression is required; grammar and spelling count.
The same requirements apply to exams.
Every assignment should include a README file that describes
the work.
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-muhn RAM-zee)
- Identify
what aspects of the work have been correctly
implemented and what have not.
- Identify anyone with whom you have collaborated
or discussed the assignment.
- Say approximately how many hours
you have spent completing the assignment.
Extra Credit
Most homework assignments will offer opportunities to earn extra credit.
I use extra
credit to adjust final letter grades.
For example,
if your grade average falls in the borderline between A- and B+,
I will assign you the higher grade at my discretion if
you have done extra-credit work.
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.
Readability 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 explanation 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 your explanation.
For most homework assignments, your explanations should appear
in a README file that accompanies the assignment.
Appropriate explanations vary with 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 with the source code itself.
- For a solution of a hundred lines or more, I would expect several
paragraphs of explanation.
Here the explanation needs to 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, a couple of pages on planning, organization, and so on
are appropriate.
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
readable assignment.
Good style includes the use of functions, modules, and abstract data types where
appropriate.
Select 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 is usually a sign of poor documentation.
Documentation should focus on high-level issues such as design and
organization, data representation, and data invariants.
As noted above,
even programs that run perfectly will lose
points for poor documentation.
Documentation is a deep topic in its own right, which I am not
prepared to address here, but here are a few suggestions.
Good large-scale documentation should answer such questions as:
- What algorithms are used, if any?
- Why is the implementation correct?
- Why does it terminate?
- What are the important invariants,
preconditions, and postconditions?
- What are the major data structures and their representations?
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?
- 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 is the `recursion invariant'
(analogous to a loop invariant)?
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 the car of the car of the given element.
;
(define caar (x)
(car (car x))
)
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 and every successor of vertex 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;
; we use structural recursion on edges.
(define dfsvisit (vertex edges graph)
(if (null? edges) '()
( ... (dfsvisit mumble (cdr edges) graph) ...)))
The comment explains what the function is doing, notes that there is
no return value but 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 two examples of very poor commenting style:
++i; /* Use the prefix autoincrement operator to increase i by one. */
for (;;) { /* Infinite loop. */
Guidelines for coding style
Code you submit should be accepted by the appropriate compiler
without errors or warnings.
Your code must not wrap when displayed in 80 columns.
Your ML code must not have redundant parentheses,
as described in the relevant section of the ML supplement.
We emphasize readability and clarity, but we do not enforce
any particular coding
style.
Work that we find obscure or difficult to read will earn lower grades.
Programming is a creative process.
Individuals must reach their own understanding of problems and
discover paths to their solutions.
During this time, discussions with friends and colleagues are
encouraged—you will do much better in the course, and at
Tufts, if you find people with whom you regularly discuss problems.
But those discussions should take
place in English, not in code. If you start communicating in
code, you've broken the rules.
When you reach the coding stage, therefore, group discussions are no
longer appropriate.
Each program, unless explicitly assigned as a pair problem,
must be entirely your own work.
Do not, under any circumstances, permit any other student to
see any part of your program, and do not permit yourself to see any
part of another 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 your section leader or the instructor.)
Using another's code in any form or writing code for use by
another violates the University's academic regulations.
Suspected
violations will be reported to the University's Judicial Officer
for investigation and adjudication.
Be careful!
As described in the
handbook
on academic integrity, the penalties for violation can be severe.
A single bad decision made in a moment of weakness could lead to a
permanent blot on your academic record.
The same standards apply to all homework assignments;
work you submit under your name must be entirely your own work.
Always acknowledge those with whom you discuss problems!
Use of the library
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 sources must be acknowledged when you submit your
homework, even if you find little or nothing useful.
Some students rely heavily on the library.
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 write your
exams or go on job interviews!
Wikipedia considered harmful
For COMP 105 in particular, Wikipedia merits special warning.
Wikipedia is a terrible source of information on
programming languages.
Many of the entries are just plain wrong,
and Wikipedia's rules make it nearly impossible for experts to correct
bad articles.
(Yes, I have tried.)
Don't use Wikipedia for 105.
Late Policy
Homework that is submitted electronically (most homework) 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 comp105
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 misfeature
in use you will need the line
use -q comp105
Without the -q option you may have
difficulties with scp, ssh,
git, VNC, or rsync.
A submission script is named submit105-name, so for
example the submission script for the first assignment is called
submit105-intro.
(Actually there are two submission scripts:
for your individual work, there is
submit105-intro-solo,
and for the part of the work you do with a partner, there is
submit105-intro-pair.)
Normally you should change to the directory in which you have placed
your solutions and run the script.
Most submission scripts do some sort of sanity checking.
If the submission script complains, fix the problems 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
comp105-staff@cs.tufts.edu.
Also, be sure that you are signed up for the
class
mailing list, which is
comp105@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/comp105.
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/comp105/.
You will need your mailing-list password, which should have been
emailed to you.
This class has a mandatory 75-minute small-group discussion section.
Each section will be guided by the class instructor or by an
Engineering
Fellow.
All of the Engineering Fellows are practitioners who know and like the
course material, and some of them are experts of world renown.
The purpose of the sections is to give you a place to ask questions
about your homework, to receive expert feedback on work you've turned
in, and to understand the connections between the topic of programming
languages and the world of programming practice—also known as
how a knowledge of programming languages can give you a competetive
advantage.
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 laboratores in
Halligan 116&nsbp;and 118.
For remote access use linux.cs.tufts.edu.
The software from the book will be installed on these machines,
but you can also grab the software and compile it yourself; try
git clone linux.cs.tufts.edu:/comp/105/book-code
If you need an account for CS machines, please send email to
staff@cs.tufts.edu.
Ask for bash as your login shell.
Stupid software tricks
The Linux servers have the wonderful ledit program,
which is extremely handy for interacting with our interpreters.
Try typing, e.g., ledit impcore, and you will be able to get
an interactive editing loop with the impcore interpreter.