Syllabus for COMP 105, Programming Languages
(Information Every Student Must Know)

Norman Ramsey

Spring 2019

Hard work is great but working smarter is even better. At times, you have to take a break, back off, and use your time efficiently.

— Bill Belichick

Introduction and Welcome

Welcome to COMP 105! Here you will learn to write code from scratch, in a language you have never seen before, in a way that sails through code review.

COMP 105 serves as the fourth course in our required programming sequence. In this sequence, it is the only 100-level course. It is the most technically deep, the most intellectually challenging, and the one in which you’ll develop the most diverse and highest-level thinking skills. You will think hard, stretch beyond the skills you have grown comfortable with, and emerge with a permanently higher level of skill.

COMP 105 introduces you—through extensive practice—to ideas and techniques that are found everywhere in today’s programming languages. These ideas and techniques infuse many languages you have not yet seen, and they will continue to infuse the programming languages of the future. Foremost among these ideas are functions, types, and objects. COMP 105 also introduces you to the mathematical foundations needed to talk precisely about languages and about programs: abstract syntax, formal semantics, type systems, and lambda calculus. Mathematics helps you recognize ideas and techniques that you have seen before, even when they are disguised.

To provide a sane and sensible context in which to learn, COMP 105 immerses you in case studies, conducted using tiny languages that are designed to help you learn. In any given case study, you may act as a practitioner (by writing code in a language), as an implementor (by working on an interpreter for the language), as a designer (by inventing semantics for a related language), or as a scholar (by proving mathematical properties of the language).

COMP 105 develops high-level, flexible programming skills that you can transfer. For example, you will find you can apply your skills to projects written in older languages such as Perl or Java, in currently popular languages such as Python, Ruby, Scala, and Swift, and in weird languages that might be important in the future, such as Haskell, Rust, Agda, Coq, and who knows what else. No matter what language you work in, when you finish 105, you’ll be writing more powerful programs using less code. In a profession where complexity is the enemy, your 105 skills will equip you to tackle the most demanding jobs—and succeed.

What will the experience be like?

COMP 105 is as difficult as any course in our program, and it’s a difficulty of a kind you are not used to encountering. I want every student to succeed, and you are more likely to succeed if you know what to expect.

How does 105 compare with 40?

For most students, COMP 105 is as difficult as COMP 40. Some students find 105 a little easier, and some find 105 a little more difficult.

If you know 40, you know that your feeling of accomplishment comes primarily from building the projects. The 40 projects are easy to talk about: they look big, and many of them sound impressive, like “I built an image compressor.” Most important, the 40 projects require that you apply the same skills that you learned in 11 and 15, just to a greater degree. In brief, 40 yields to force.

COMP 105 also has a couple of projects that look big and sound impressive, like “I built a type inferencer.” But overall, 105 is much more about finding a small, elegant, precise solution to a small problem—usually a programming problem, but sometimes a math problem. As a result, compared with COMP 40,

But even though 105 is quite different from 40, there are lots of skills that transfer. If you have taken COMP 40, then

But you must also be aware that some of not all of your habits in COMP 40 will necessarily transfer to COMP 105:

Why do I feel lost?

To succeed in 105, you must understand that it is normal to feel lost. There is nothing wrong with you, and there is nothing wrong with the course—feeling lost is a consequence of the situation: where you’re coming from and where you’re going.

Where you’re coming from is most likely 11, 15, and possibly 40. All of these courses use a single programming paradigm, and they use almost the same language: imperative programming with unsafe pointers and explicit memory management, close to the machine. Even the syntax and the data are the same—compared to what you can see in the world, and to what you are introduced to in 105, differences between C and C++ barely matter. If you’ve completed 40, you’re going to feel like an expert. And rightly so! You are an expert. But you’re a narrow expert, and 105 introduces you to the demands of a wider world.

The most important way in which 11, 15, and 40 are narrow is that their programming model is a thin veneer over the machine model. These courses don’t rely heavily on functions or types, and they do not commit deeply to objects. (While C++ makes it possible to commit strongly to types and to objects, it imposes such staggering complexity that these techniques cannot be taught in introductory courses.) Your inexperience with functions, types, and objects makes you a beginner again. And beginners often feel lost.

The other factor that comes into play is that when you learn challenging new material, you feel bad. Here’s the neuroscience:1

Many labs have observed that these critical brain regions increase in activity when people perform difficult tasks, whether the effort is physical or mental… [The road is difficult], though, because these brain regions have another intriguing property: When they increase in activity, you tend to feel pretty bad—tired, stymied, frustrated. Think about the last time you grappled with a math problem or pushed yourself to your physical limits. Hard work makes you feel bad in the moment.

What should I do about it?

When a successful student suddenly feels lost and confused, it’s discouraging. To keep up your courage, I recommend two steps:

Both these steps will help you feel better.

You will also need to learn to proceed with your work despite feelings of confusion, uncertainty, or anxiety. To help with that, you need support.

What tactics do and don’t work?

In 105, the slow approach is the fastest one. Effective 105 students stop, think, pause frequently, and work in short sessions. These tactics can be hard to put into practice, especially if you have used other tactics to succeed in other courses. But the work tactics often preferred by beginners do not promote success in 105. I paraphrase Garth Flint:

[Talented students] are very resistant to [a systematic, thoughtful, slow] approach. They do not want to plan; they want to do trial and error at the keyboard. They have not learned an important axiom of programming: “three hours of trial-and-error coding will save fifteen minutes of planning.” (I wish I knew who came up with that. They deserve an award.) [Students] want to hammer keys [in Halligan for hours on end and] then complain [that the course is too much work].

If you approach 105 by hammering away at the keyboard, be aware how the approach is working for you. If the course starts taking too much time, you can adjust your tactics—but only if you are mindful of them.

If you have already learned systematic tactics for program design and implementation, you should be able to apply them to COMP 105. If you have not had to learn a systematic approach, which is common after early courses, you will easily master a nine-step design process described in Seven Lessons in Program Design.

How does the class support my success?

To help you navigate the learning process successfully, we have built a variety of support structures into COMP 105.

How can I use office hours effectively?

COMP 105 office hours are organized around physical space.2 The primary help point is in the upstairs kitchen in Halligan, and it is equipped with these accessories:

When you want help, go to the primary help point. Add your name and your topic or question to the queue written on the board. Your TAs have been instructed to prioritize groups of students who want to talk about similar issues, or who have similar questions. These groups are called affinity groups. You can also get help as an individual, but you may have to wait longer than when you are part of an affinity group. (The TAs on duty will help you form affinity groups.)

The 105 help points can get crowded, and not all students thrive in crowds. You are always justified in telling a TA, “I would like to go somewhere quiet to talk about this.” Your TAs have been instructed to ask. (They have also been instructed to ask, politely, if other students can join the quiet discussion.)

When the kitchen gets crowded, the 105 TAs have been instructed to walk the second floor every 20 minutes, checking to see if there are students who want to talk about COMP 105.

What can I expect from teaching assistants?

In COMP 105, the TAs have been instructed to use a model that may be a little different from what you are accustomed to. The TAs are not there to help you debug your homework. They are there to help you learn. And the TAs who provide the best help and who help students learn the most are the ones who guide students with questions.

The questions that TAs ask are meant to be timeless and to apply to many problems. Eventually, you will be able to use the questions yourself, to help your own progress. Questions range from the technical (“what algebraic laws apply to this function”?) to the conceptual (“in your own words, what is meant by Γ ⊢ e : τ?”) to the procedural (“how much of your 105 time is spent working alone?”). Expect questions about your work, your understanding, and your study practices.

Here are some other things you can and cannot expect from TAs:

What if I need special support?

Tufts University values the diversity of our students, staff, and faculty; Tufts recognizes the important contribution each student makes to our unique community. Tufts is committed to providing equal access and support to all qualified students through the provision of reasonable accommodations so that each student may fully participate in the Tufts experience. If you have a disability that requires reasonable accommodations, please contact the Student Accessibility Services office at Accessibility@tufts.edu or call 617-627-4539 to make an appointment with a representative who will help determine appropriate accommodations.

Accommodations cannot be enacted retroactively; if you need an accommodation, you must ask for it in advance.

How must I support my own success?

Everyone on the course staff is committed to your success. But as we do our part, you must do your part. Take advantage of the resources we offer. Read the syllabus. Most important, do not allow yourself to become socially, emotionally, or intellectually isolated. To prevent isolation, I recommend that you join a study group, and that when you can, you work in Halligan. The informal support network in Halligan is strong; participating in Halligan culture is one of the unique advantages of getting your computer-science education at Tufts. Don’t miss out.

As you will see throughout this syllabus, there is more you can and should do:

105 is a 100-level course. What does that mean?

Unlike 11, 15, and 40, COMP 105 is numbered above 100. Formally, this means only that unlike 11, 15, and 40, 105 counts for graduate credit. But informally, a 100-level course carries additional expectations:

What will we learn?

COMP 105 is built around two sets of skills:

The programming skills contribute to your professional practice, getting you ready to code from scratch in a language you’ve never seen before. The math contributes to several outcomes:

Here are some of the detailed skills you will develop:

What topics will we study?

You will develop the skills above by studying these topics:

  1. Functions

    • Recursion revisited: design by algebraic laws
    • Abstract syntax & (big-step) operational semantics
    • First-class, higher-order functions
    • Functions as continuations

  2. Types

    • Core ML
    • Typing rules (monomorphic and polymorphic)
    • Type checking
    • Type inference

  3. Theory

    • Lambda calculus & small-step operational semantics
    • Recursion and fixed-point operators

  4. Data abstraction

    • Abstract data types, modules, and interfaces
    • Objects, classes, and protocols
    • Inheritance and the design of class hierarchies

How heavy is the workload?

The workload in 105 is heavy; it counts for 5 semester hours of credit. Expect a demanding homework assignment almost every week, plus two challenging examinations. Most students say 105 demands as much time and effort as 40.

What does the workload consist of?

The work is mostly programming assignments. These assignments are significantly more challenging than the assignments in COMP 15 and COMP 40, but most of them are also much smaller: many solutions take 10 to 40 lines of code. Many of the assignments use software that comes with the text by Ramsey.

The homework also has a significant theory component. You will prove theorems using existing theory, and you will also develop new theory of your own, which will describe how a language feature might work. Early assignments are either “mostly programming” or “mostly theory;” later assignments mix programming and theory; and some assignments ask you to apply theory to write code.

The course also has two exams: a midterm and a final.

How does my work affect my grades?

Your course grade is based on my judgment of the quality of your work and the degree of mastery you demonstrate. My judgment is influenced by your written work, by your class participation, and by your examination scores, but I give heavy consideration to written work, as indicated by this approximate system of weights:

Homework assignments 58%
Recitations 10%
Midterm exam 7%
Final exam 15%
Participation in other class activities 5%
Office-hour visit to the course instructor 5%

The weights may be adjusted at my discretion.

What do my homework grades mean?

Your homework grades are based on the course staff’s judgement of the quality of your work and your mastery of the material. Grades are assigned a coarse five-point scale:4

In a typical class, a consistent record of Very Good homework, together with commensurate examination grades, will lead to a course grade in the A range. If some work goes “above and beyond” and is rated Excellent, a grade of A+ is possible. Work rated Good corresponds to a wide range of passing grades centered roughly around B. Work rated Fair will lead to low but satisfactory course grades; if a significant fraction of your work is Poor, you can expect an unsatisfactory grade (D or F).

No Credit is a disaster. If 10% to 15% of your work is awarded No Credit, it is likely to cost you something like one full letter grade. Any grade, even Poor, is dramatically better then No Credit. Why? Because the worst thing you can do is to skip problems. Every problem you attempt will teach you something; when you skip a problem, you learn nothing.

What is a “minor deduction”?

Sometimes there is a fault in your code that needs to be corrected, but that does not warrant dragging a grade down from Very Good to Good or from Good to Fair. That sort of fault typically receives a “minor deduction.” Here’s the prototypical example:

It is never correct to write if P then true else false. Clean code always says just P.

A minor deduction is the rough equivalent of a “point off” out of 100 points.

What about final letter grades?

Final course grades are meant to reflect a consistent standard, consistently applied. The standard is an absolute standard; COMP 105 is not graded on a curve. Anyone who achieves strong results can earn an A.

Here are some details about the standard:

The standard is a guideline, not a decision procedure. To the degree possible, I adjust the border between letter grades so that different grades reflect significant differences in students’ performance. For example, in any given semester, the line between B and B-minus will be near a 100% Good record, but in a place where there is a meaningful gap in students’ achievement. This place might be above or below 100% Good. Where no meaningful gaps in achievement can be found, the line is drawn to minimize pluses and minuses; for example, many students earn A grades, but relatively few earn A-minus or A-plus.

What if my homework is graded incorrectly?

If we make a mistake in grading your homework assignment, you have seven days after the return of the assignment to call the mistake to our attention. File a request using the form at https://www.cs.tufts.edu/comp/105/regrade. We reserve the right to reassess your entire assignment and assign a new grade. The new grade may be higher or lower than the original grade.

What should I expect from exams?

To understand your exam grades, you must understand what I believe an exam is for. An examination should test not only your mastery of familiar material but also your ability to apply your knowledge to unfamiliar situations. To do well on my exams, you must

When you take one of my exams, expect not to know all the answers.

Each exam consists of multiple problems; some problems will ask you to read and write code. Each problem is worth a certain number of points; the number depends on how hard I think the problem is and how long it takes to complete the problem. Most problems are divided into multiple parts of varying difficulty:

It is very rare for an answer to earn all points available on a problem.

Every exam is unique, but typical raw scores are much lower than you may be accustomed to. For example, it is almost unheard of for a student to earn 90% of the available points on a COMP 105 exam. Typically, if you earn two-thirds of the available points, your grade will probably be Good or Very Good. And if I botch the exam by making it more difficult than I intend, it’s possible that earning only 50% of the points will still result in a high grade.

How are the exams administered?

The final exam is administered during final-examination period as part of the usual Tufts system of two-hour final exams. It is a closed-book exam, but you may take with you one standard US letter page of notes written on both sides. I strongly encourage you to create such page and to write your notes by hand; preparing the notes is a very effective way to study.

The administration of the midterm examination is more complicated. The midterm is designed as a 75-minute in-class exam. But because classes are held two days a week, there is no good time to schedule the exam—our regularly scheduled lectures always fall within one day of a homework deadline. To create flexibility in scheduling, the midterm exam is administered over a period of about 48 hours:

How am I graded in recitation?

COMP 105 requires you to learn many new ideas and techniques. Before you can make progress on the homework, you need to understand the ideas and techniques. Recitation helps; each week, you get a third look at ideas and techniques, and you get practice working relevant exercises. Each recitation is graded on a three-point scale:

We drop the two lowest recitation grades, so if you have one or two bad days, it won’t affect your final course grades. This policy also enables you to miss up to two recitations without penalty. If you need to miss more than two recitations, explain the situation to your academic dean, and have your dean make contact with me.

How is my participation graded?

A portion of your grade is based on your participation in the class. This phrase encompasses a variety of activities that demonstrate you are engaged actively in managing your own learning, developing new skills, and understanding new ways of programming and problem-solving. To earn high grades for class participation, you must show that you are so engaged. You can show this engagement in a variety of ways:

Nobody has to do all of these things; you can earn top grades for class participation by doing just a few things well. In particular, nobody is required to speak in class—but everybody should be prepared to answer questions if called upon. 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.

How should I interact with people?

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.

How much interaction is too much?

Interactions and discussions with classmates must take place in human language, at a high level. You must not discuss code, and you must not exchange human language, pseudocode, or other information that is expressed at the level of code. If you start communicating in code or at the level of code, including algebraic laws, you’re breaking the rules.

Suspected violations will be reported to the University’s Director of Community Standards, who will investigate, decide if a violation has taken place, and if so, recommend an appropriate penalty. Be careful! As described in the university’s academic-integrity policy, 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!

So can I post my code on github?

Code in a github repository is visible to other students. So no, you may not post your code to a github repository—unless you are very careful to make the repository private. It is certainly convenient to use github for backup and to share your work with potential employers. But it must be private. It is against course policy for you to put your homework in a public github repository—and because a public github repository can facilitate misbehavior by others, it is considered a violation of academic integrity.

How do pair-programming interactions work?

In pair programming, you work with a partner under the following constraints:

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

What if pair programming doesn’t work for me?

In COMP 105, you are never required to pair program. About 20% of students routinely opt not to pair program.

If you try pair programming and find it is not working, or if your programming partner disappears in mid-project, proceed as follows:

How does the course staff monitor pair programming?

To try to ensure a good pair-programming experience for everyone, the course staff will choose a random sample of students to ask these questions:

The course staff will use this information to try to improve students’ pair-programming experience and to try to prevent disappointing experiences from getting worse.

Do I have a right to pair program?

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 revoke your pair-programming privileges and you believe I have done so unfairly, you may appeal to the department chair.

What is expected of my homework?

In this class, you will learn most of the material 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 are based on the text by Ramsey. There are also some larger programming assignments. And there is some theory homework, involving more proving and less programming.

As in most classes, 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 big 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 recitation 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.

How should my homework be submitted?

Homework for each assignment is submitted using a course-specific submit script, with a name like submit105-impcore. The submit script checks to be sure you have files with the right names, and so on.6 On most assignments, there are some additional checks:

And the submit script may ask for other information:

Before running a submit script, cd to the directory in which you have placed your solutions. If the submission script complains, fix the problems and resubmit. You may submit and resubmit the same assignment as many times as you like. I 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 submit script is expecting.

How do I get access to the submit scripts?

We provide a submission script for each assignment. To get access to those scripts, you need to execute

     use comp105

to ensure that these scripts are on your execution path. This use command should also give you access to interpreters for impcore, uscheme, and so on.

It is very convenient to put the use 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-impcore.

How should my homework be formatted?

Whether it is digital or analog, your written work must bear your name, and it must be neat and well organized. 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

How should my code be written?

Your code should conform to our coding-style guidelines, which are online. Pay special attention to the offside rule. These guidelines will help your solution be understood and modified by others. Your code is graded its conformance to these guidelines, on your explanation of what you are doing, and on your code’s functional correctness.

You will notice that the code from the book does not conform to all of the guidelines in the handout—especially the guidelines on layout. That’s because the book code is written as a literate program. If you wish to submit your own code as a literate program, you may. And you may choose whether you wish to work with the bare or the commented versions of the code in the book.

How will the structure of my code be evaluated?

The structure and organization of your code is evaluated according to our general coding rubric, which is online.

How will the correctness of my code be evaluated?

Submitted code is typically evaluated by automated testing. Our test scripts aim to explain why you got the grade you did, and if you made a mistake, what it was. On most assignments, you can expected grades to be assigned according to the following criteria:

In summary, Very Good code is expected to be faultless. Faulty code normally earns a Fair grade, but if the faults are very minor, it might earn a Good grade, and if the faults are grave, it might earn a Poor grade.

Code that writes to standard output or standard error, unless such output is called for in the problem specification, is at risk of earning No Credit. Use print and println at your peril!

Should I use LaTeX to write theory homework?

No. LaTeX and the mathpartir package do make it possible to typeset clear, legible inference rules, derivations, and proofs. That makes it easy for the course staff to read your work. But unless you already have experience using LaTeX to typeset mathematics, I recommend against using it. LaTeX is a power tool, but it’s hard to learn, and it provides terrible error messages. In COMP 105, you will be learning plenty of other power tools; learn LaTeX some other time.

If, however, you already know LaTeX, you may benefit by emulating our LaTeX source code for a simple proof system or Sam Guyer’s LaTex source code for typesetting operational semantics.

Then how should theory homework be written?

Use pencil and paper. (Microsoft Word, Open Office, and that ilk are even worse choices than LaTeX—they aren’t set up to handle even simple math, let alone inference rules.) Of course, you need to submit PDF. Here are two ways to get it:

Any PDFs you submit will be emailed back to you automatically. Use the automated email to confirm that the PDF was correctly transferred to the homework server, that it opens, and that it displays your work as you expect.

How may I use 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. But using the library is never required; everything you need to know can be found in lecture, in recitation, on the course web site, or in one of the books.

Some students rely heavily on the library. Although this behavior is permissible, 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!

If you do use the library, the Internet, or other outside sources, your homework must acknowledge the use of these sources, even if you find little or nothing useful.

So how may I use code downloaded from the Internet?

Any code that is posted to the official Tufts COMP 105 web site is permissible for you to use. You must not download any other code from the Internet. You certainly may not submit it as part of a homework assignment.

May I use code from the book?

Absolutely! Any code from either of the books is fair game for you to use. Most of this code is provided in machine-readable form in /comp/105/build-prove-compare. Help yourself!

Several of the later homework assignments—especially around type systems—are feasible only with the support of code from the book.

How should I use Wikipedia?

Don’t. 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. You don’t yet have enough experience to identify bad information, so don’t use Wikipedia for 105.

What does an extra-credit problem mean?

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 significant extra-credit work. I will also mention extra credit if I write you a letter of recommendation. Extra credit is just that: extra. You can earn an A or A+ without doing any extra credit.

What if I can’t get my homework in on time?

Homework is typically due at 11:59 PM on a Tuesday. We will grant an automatic extension of fifteen minutes at no cost to you. If you plan on submitting your work at midnight, you will have fourteen minutes for last-minute changes.

We expect your homework to be submitted on time. But we recognize that the exigencies of college life occasionally interfere. If you have difficulty, you have several options:

After the 24-hour extension deadline has passed, model solutions will be available on the Web or distributed as hard copy in class.

What if my partner is out of extension tokens?

If you are pair programming with another student, and you need to submit work a day late, both partners are charged an extension token. If your partner is out of extension tokens, your only choices are to submit on time or to get a “no-fault divorce” and submit separately. After the divorce, both students have equal rights to all common work, but only the student who still has tokens can submit late. At submission time, both submissions must be identified as individual work (list nobody as the programming partner). Submitting as a partnership is likely to harm one or both grades. The true situation should be explained in the README file.

What if I can’t finish all the problems?

If you can’t finish every problem, act tactically to maximize your grade:

105 is very cumulative, so if you can’t finish every problem, you’ll also want to act strategically to maximize the chances that you can do better on the next assignment. Your best strategic choice depends on the details of the assignment, so ask the course staff.

What is expected in lecture?

In lecture, I expect you to maximize your own learning and to eliminate distractions that might interfere with other students’ learning. Attendance at lecture is a privilege, not a right or an obligation. If the course staff thinks your activities might be distracting other students, that privilege will be revoked.

Should I take notes? How?

To maximize your own learning, I recommend that you take notes, sketches, and diagrams by hand. Paper is good, with a pen or pencil. If you have a large touch screen and can take notes with a stylus, that works, too. I recommend against using a keyboard with a standard laptop or word-processing software:

You never need to copy the instructor’s notes or slides; they are available online. Use your own notes to make connections and to highlight points that you find difficult or that you want to remember.

What distractions must I avoid?

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.

The ultimate distraction machine is the laptop computer. Please refrain from any computer-based activity that is visible from a nearby seat and that might distract another student. Such activities include, but are not limited to

If you cannot resist such activities, put your computer away at the start of class.

What is expected in recitation?

Recitation helps deepen your knowledge of the course material, and it helps you learn to work in a way that promotes insight and defends you against overwork and exhaustion. Recitation is structured around practice on problems related to current homework assignments.

Recitation is mandatory, and your participation is graded.

Which recitation do I attend?

You should have received a recitation assignment by email. This email should authorize you to adjust your record in SIS so that you are duly signed up for the recitation you have been assigned. If you signed up for a different recitation using SIS, your SIS sign-up may not be honored. To get access to a recitation, you must have an email from the department, which will authorize you for your recitation.

(In order to create a small-group learning environment, we cap the enrollment of each recitation section. We use software to place each student into a recitation section that works for them, maximizing the number of students who get a top preference. Unfortunately, the registrar is not able to do this work for us or to enter your assignment into SIS on your behalf.)

If you did not receive an email authorizing you for a recitation, or if you need to change recitations, please post immediately to Piazza.

What logistics and policies affect my homework?

Here is a summary of relevant information that is distributed throughout this syllabus:

I’m not required to take 105. Should I take it anyway?

COMP 105 is required for Computer Science majors. If you’re not a Computer Science major, find the paragraph that applies to you below.

If you’re getting a Computer Science minor, or if you’re just interested in computing, you should take 105 if you want an intense experience that will broaden and deepen your programming skills. (Unless you have a professional or recreational interest in mathematics or logic, some of the theory parts of the course may be less interesting to you.)

If you’re a postbac student or a master’s student, you also should take 105 if you want an intense experience that will broaden and deepen your programming skills. Many of our postbac students, in particular, report that 105 was a highlight of their certificate program. Postbac students and master’s students do need to be aware that as part of Tufts’s commitment to residential learning, the course is designed to serve undergraduate students who are on campus during the day.

If you’re a doctoral student or MS/PhD student, the value of 105 depends on what you are trying to accomplish.

What skills must I have already?

COMP 105 is the final course in our required programming sequence, and it calls on a broad and deep array of skills you are expected to have developed in earlier courses.

What basic skills do I need?

You must grasp basic algorithms, data structures, and good programming practice.

What Unix skills do I need?

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. You can learn about such things from Kernighan and Pike.

What file-transfer skills do I need?

If, as we recommend, you do your theory homework on paper, you need to know how to convert it to PDF and to get the PDF onto a departmental Linux machine.

What theory skills do I need?

You must be comfortable with basic discrete mathematics. You must be able to prove theorems, especially by induction.

You must have taken Discrete Math (Math 61 or COMP 61). If you have not, you must produce some other evidence that you can reason precisely about computational objects.

You must be able to write an informal mathematical proof. For example, you should be able to prove that a sort function returns the same set of elements that it was passed.

You must be comfortable using basic mathematical formulas with “forall” (∀) and “exists” (∃) quantifiers, i.e., the propositional and predicate calculi.

You must know basic set theory, e.g., the mathematical definition of functions as sets of ordered pairs.

You must be comfortable reading and writing formal mathematical notation, or at least be able to look at it without running screaming from the room.

What programming skills do I need?

You must have substantial programming experience. If you don’t, you will have difficulty keeping up with the homework.

A few homework assignments require some proficiency in C. If you have a strong background in C++, some details will be different, but your background should be sufficient.

Your programming experience should include work with dynamically allocated data structures and with recursive functions. You must be comfortable writing recursive functions in the language of your choice, as well as proving that such functions terminate.

You must 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.

What other programming skills might help?

This course uses unusual programming paradigms, and it really helps to have some facility with systematic software design. Our recommended nine-step design process is a solid starting point, but if you have practice with additional design methods, you will prosper. Many of the most effective design methods are grounded in formal reasoning about programs, including the following intellectual tools:

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.

What is the most important skill of all?

The most valuable skill you can have for COMP 105 is the skill of managing yourself. To do well in 105 or in any other course that involves programming, develop these habits:

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

What books do I need?

You absolutely, positively have to have the book Programming Languages: Build, Prove, and Compare by Norman Ramsey. You can buy the book in the Computer Science office in Halligan. When you buy the book, nobody profits: the intellectual property is donated; the copies are printed by the University printing office; and the department sells the book for a sum just sufficient to cover the cost of printing.

The short booklet Seven Lessons in Program Design is available online, and hard copy is distributed on the first day of class.

The book Elements of ML Programming by Jeff Ullman is very useful, but just for a few assignments. If need be, you can get by without it; we have assembled an extensive ML learning guide that uses entirely free resources. We recommend Ullman’s book anyway, because we think that spending the extra money will save you enough time to be a good tradeoff. If you do buy the book, be sure you get the ML’97 edition. It is available in the University bookstore, but you can probably get it more cheaply elsewhere.

What computers can I use?

The class is set up to run on Red Hat Enterprise 64-bit Linux, as installed on the departmental homework server and in the laboratories in Halligan 116, 118, and 120. For remote access use homework.cs.tufts.edu. The software from the book will be installed on these machines, but you can also grab the software and compile it on your own computer; try git clone homework.cs.tufts.edu:/comp/105/build-prove-compare.

If you need an account for CS machines, please send email to staff@cs.tufts.edu. I recommend that you ask for bash or fish as your login shell.

What software can smooth my path?

I recommend a wonderful program called ledit, 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. The ledit program is already installed on the departmental servers, and it can also be downloaded from INRIA and installed on your own machine.

I also recommend using a “programmer’s editor” such as vim or emacs. A most valuable feature of such editors is the ability to jump directly to the source location of an error. For vim you will need to learn the :make command, and you will probably need to set makeprg. For emacs you will need to learn the M-x compile command.

How about Emacs tricks?

If you do use emacs, you will find your code much easier to manage if you enable paren-mode, which you can do by placing these lines in your .emacs file:

  (require 'paren)
  (show-paren-mode)
  (setq show-paren-style 'expression)

I also recommend using the M-x customize-face command with face show-paren-match to set the screen to bright yellow on parenthesis match.

You can use the Emacs TRAMP facility to edit files directly on the remote server, by using file names like /nr@homework.cs.tufts.edu:/comp/105/www/syllabus.md. This allows you to edit on your own local machine, but every time you save the file, it is automatically sent to the homework server, where you can compile or run it.

What if campus closes unexpectedly?

At least every other year, there is a snowstorm so disruptive that we cannot hold classes on campus. In these cases, following guidelines developed for the School of Arts, Sciences, and Engineering, we will conduct class or recitation electronically. Educational Technologies has a web page explaining what to do when campus is closed. We will announce details on Piazza.

Office hours present a greater challenge. When we can do so safely, we’ll try to have boots on the ground in Halligan. But also, we will pay extra attention to Piazza, and some TAs may hold office hours electronically.

What may I do with solutions?

I provide solutions to all homework and exam questions. Being able to examine master solutions helps you learn. But I provide solutions for your private use only. Please do not share them with other students, and please make sure they do not find their way into public places, archives, and so on.

Copying solutions, whether from me or from another student, is a serious violation of academic integrity. Providing solutions to be copied is equally serious. For either violation, the usual penalty is a year’s suspension.

What if I am repeating the course?

If you are repeating the course, we expect you to abide by the following policies.

What else do I need to know about academic integrity?

The course operates under the university’s academic-integrity policy, which you must know. In addition, you must know that in COMP 105, seeing another student’s code is an integrity violation, and so is allowing another student to see your code. I am mandated to report even the suspicion of an integrity violation.

I’m different. Am I really welcome here?

Yes! We strive to create a learning environment that welcomes students of all backgrounds. If you feel unwelcome for any reason, please let us know so we can work to make things better. Talk to anyone on the teaching staff, or if that feels uncomfortable, try your academic advisor, our department chair, or your dean.

COMP 105 can be especially difficult for first-generation college students and for members of underrepresented groups, who may not have the family or social support that helps them develop their skills in “how to be a college student.” If you are a first-generation college student or a member of an underrepresented group, I encourage you to have your “five minutes with the professor” visit early in the term, and we can talk about your support system.

Acknowledgments

For help with this syllabus I owe thanks to Kathleen Fisher, Jared Chandler, and Alex King. For help with syllabi in general, I thank Annie Soisson.

  1. Lisa Feldman Barrett, “How to Become a ‘Superager’”, New York Times, Dec. 31, 2016↩

  2. We’ve learned that Halligan Helper leads to unacceptable wait times and unhappy students, so we no longer use it.↩

  3. “On your own” means “with the help of your classmates and your teaching assistants.”↩

  4. It is the same scale used by the National Science Foundation and by Consumer Reports.↩

  5. By definition, it is not possible for the entire class to excel. The normal top grade is Very Good, and students who consistently produce Very Good work earn A’s. Grades of Excellent are awarded only in cases of true distinction. This means, for example, that if everyone in the class turns in a perfect solution, all those perfect solutions are judged Very Good.↩

  6. We hope one day to get provide to take care of these checks for us, but we’re not there yet. Please don’t submit homework using provide.↩

  7. 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 to both.↩