COMP 105: Detailed information all students must know

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 must have taken Discrete Math (Math 61, or Math 22 before 2011, or COMP 61, or COMP 22 before 2012). If you have 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. Enlist the whiteboard as your ally.
• Never be satisfied with a ``working program,'' but strive for the simplest, clearest, most elegant implementation.

Interactions are Expected

• 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. To earn your five percent, you must come to my office hours by the end of February. 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. If you need help finding a partner, advertise on Piazza.

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 and do not return until you have finished your call.

Quizzes

Quizzes will be graded on the following scale:

• If you are not present for the quiz, you earn No Credit.
• If you are present for the quiz, but cannot demonstrate that you have read something, you earn a low pass (Fair).
• If your quiz answer shows that you have read something, you earn a regular pass (Good).
• If your quiz answer shows that you have read something and understood something, you earn a high pass (Very Good).

• Participating in the in-class midterm course evaluation (for 105, the online departmental midterm evaluation is optional)
• Submitting evidence that you wrote online end-of-term course evaluations
• Writing sane and sensible answers on quizzes
• Asking appropriate questions in class
• Answering questions when called on in class
• Asking appropriate questions on Piazza
• Answering questions well on Piazza
• Organizing study groups
• Interacting professionally with programming partners and course staff
• Working out ideas with teaching assistants
• Helping other 105 students in Halligan

What questions are appropriate? Any question about programming languages. However, it may not be appropriate to insist that every question be tracked to its lair and answered. If a question becomes inappropriate during class, I will let you know.

Professional interactions with other students and with course staff are the same as those which are expected in any workplace. It is also professional for you to recognize that a member of the course staff may be present but not actually available to talk about 105.

Homework is critical

As in most classes (exceptions, you know who you are), it helps to start the homework early. But in 105, starting early seems to produce unusually good benefits. Many students report that if they start early, even if they don't appear to make much progress, a solution will “come to them” while they are doing something else.

Another reason to start early is that if you get stuck, early help is a lot better than late help. 105 is a large course, and 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

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

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

Readability of programming assignments

• For homeworks that involve small programming problems, most explanations will take the form of documentation for the code you write. Each assignment explains what documentation is expected.
• For homeworks that involve a large programming problem or that have a substantial design component, an explanation should appear in a README file that accompanies the assignment.

• For a trivial solution of a few lines of code, it's often best to have no explanation at all. Ideally the names of your functions and their parameters will be all the explanation anyone needs to understand the code.
• 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. 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.

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 earn low grades if they are badly documented.

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?

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

• What is the contract of each function? (The contract of a simple function should be evident merely from the name of the function and from the names and types of its arguments and result. The contract of a more complex function may require a comment.)

  There's more about contracts below.

• What are the arguments of the most significant functions? 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)?

; (example of poor commenting style)
;
;  Function: caar
;  Description: Returns the car of the car of the given element.
;
(define caar (x)
  (car (car x))
)

; (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) ...)))

Here are two examples of very poor commenting style:

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

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

Requirements 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. and it must not contain TAB characters. (Why this stuff matters and how to deal with it.)

• Your ML code must not have redundant parentheses, as described in the relevant section of the ML supplement.

• All submitted code must obey the offside rule, as explained below.

The offside rule

Here's the rule given more precisely:

Code respects the offside rule if and only if whenever the first token of a construct appears in column i, every other token appears in a column greater than i.

 (define gcd (m n)
     (begin (while (!= (set r (mod m n)) 0)
         (begin
           (set m n)
           (set n r)))
       n))

Here is the same function formatted in a way that respects the offside rule:

 (define gcd (m n)
     (begin
       (while (!= (set r (mod m n)) 0)
         (begin
           (set m n)
           (set n r)))
       n))

 (define gcd (m n) (begin
                     (while (!= (set r (mod m n)) 0)
                        (begin (set m n) (set n r)))
                     n))

Here is a C declaration that violates the offside rule:

static Valuelist evallist(Explist el, Valenv globals, Funenv functions, Valenv
                                                                      formals);

static Valuelist evallist(Explist el, Valenv globals, Funenv functions,
                          Valenv formals);

What is a contract?

• The point at which the function is called
• The point at which the function returns

As an example, a function to compute the greatest common denominator of two natural-number arguments m and n might say simply:

Returns the largest integer that evenly divides both m and n.

Another example of a contract would be for a sort function:

Takes a list of integers ns and returns a new list containing the same elements as the argument list, but in nondecreasing order.

Here is an example of documentation that is not a contract:

The function walks through the tree and at each step checks to see if the node contains a prime number. If not, it checks the left subtree and the right subtree for prime numbers.

• The documentation says nothing about what the function returns.
• The documentation contains a narrative description of an algorithm, i.e., a computation that evolves over multiple points in time.
• The algorithm being described is almost impossible to write a contract for. Probably the author intended to implement a different algorithm.

Takes as argument a binary-search tree full of integers, and returns the smallest prime number in that tree, or if the tree contains no prime number, returns -1.

Collaboration

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 a teaching assistent or the instructor.) Using another's code in any form or writing code for use by another violates the University's academic regulations.

Do not, under any circumstances, post a public question to Piazza that contains any part of your code. Private questions directed to the instructors are OK.

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

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 ordinary difficulties, each student is automatically issued seven ``extension tokens.'' By expending an extension token, you can get an automatic 24-hour extension on all deadlines associated with a single assignment.

  Expenditure of extension tokens is governed by these rules:

  When expending an extension token, you must notify the course staff by email to comp105-staff@cs.tufts.edu. 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 ONE extension token may be expended on any single assignment. This rule is a change from past years and is designed to enable me to give you feedback in the next class after the deadline.
  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.

• If a serious illness affects your ability to complete homework on time, your first step is to report the illness using the "Illness Notification Form" that is available in WebCenter for Students. We will make suitable arrangements.

• For extraordinary difficulties, such as bereavement, 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 comp105

use -q comp105

A submission script is named submit105-name, so for example the submission script for the first assignment is called submit105-impcore. 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.

Questions and discussion

I will use information in SIS to enroll most of you in Piazza. But if you are not enrolled, you can enroll yourself using the COMP 105 signup page. Do not enroll yourself on the class mailing list that has been used in past years. We are planning not to use it.

Please never email the course staff directly to their personal accounts. If~you have a question that is not suitable as a private question on Piazza, you may write to the staff at comp105-staff@cs.tufts.edu. But Piazza will be faster.

Finally, if you have posted a question to Piazza and not gotten a timely response, many questions are appropriate to post to Stackoverflow, which can respond very quickly indeed. If you use Stackoverflow, please follow our guidelines.

It is OK to send me instant messages via Skype; my id is norman-ramsey.

We will make every effort to answer questions in a timely fashion.

Handouts

  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