Welcome to COMP 105! 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.
COMP 105 introduces you—through extensive practice—to programming-language ideas and techniques that are found everywhere in today’s programming languages. These ideas and techniques will continue to be found among 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.
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 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.
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.
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.
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,
COMP 105 presents more intellectual challenges.
COMP 105 gives you many more opportunities to make a satisfying breakthrough, often by an “aha moment.”
In COMP 105, you spend much more time feeling lost.
But even though 105 is quite different from 40, there are lots of skills that transfer. If you have taken COMP 40, then
You know how to read a long assignment and how to work away at it gradually.
You have practice building modules with specifications, and you have practice testing against specifications.
You have some experience translating some challenging concepts into code.
But you must also be aware that some of not all of your habits in COMP 40 will necessarily transfer to COMP 105:
COMP 40 may fool you into believing that every hour spent the keyboard represents progress toward your goals. In 105, it is all too easy to spend hours going nowhere. You must learn to pause, step back, and think about where you are going.
In COMP 40, you can succeed without having much insight into algorithms, linked data structures (think lists and trees), or recursion. In COMP 105, you will need insight into all of those things.
COMP 40 may fool you into believing that you can complete any difficult course if you just grind away doggedly. In 40, this approach works: it may not be much fun, but you’ll finish. And grinding away constantly has another benefit: when you’re grinding, you don’t feel bad and you don’t feel lost.
In 105, this approach works badly or not at all. If you are always grinding, you will never have that quiet moment that gives you the insight you need to solve a problem. In 105, you should deliberately break up your work sessions with frequent pauses. Such pauses will help you a lot. Stop, get up and move, and let problems percolate in your brain. You will probably feel lost or uncomfortable for a short time, but in the longer run, you’ll finish faster, and then you’ll feel great.
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 a much wider world.
The most important way in which 11, 15, and 40 are narrow is that their programming model is just a thin veneer over the machine model. These courses don’t rely heavily on functions or types, and 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.
When a successful student suddenly feels lost and confused, it’s discouraging. To keep up your courage, I recommend two steps:
First, recognize that unpleasant feelings are a normal part of a learning process. Our job as professors is to set you problems that are more challenging than you think you can handle… and to support you as learn you can handle them. This learning process requires hard work, attention to detail, and a leap of faith. But if you persist, your unpleasant feelings of confusion will be replaced by satisfying feelings of mastery.
Second, ask questions. “Is it normal that I’m confused here?” “Are you confused here?” “If I’m confused but I still want to make progress, what skill do I need, or what technique should I practice?” “If you’re not confused, what skill are you using? What technique are you applying?”
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.
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.
To help you navigate the learning process successfully, we have built a variety of support structures into COMP 105.
Early in the course, homework is structured as a large collection of small problems. When the going is most difficult, this structure makes your progress visible, even when progress is incremental.
Every homework begins with some comprehension questions about the reading. These questions guide you toward reading those parts of the book that are most valuable for completing the homework. The comprehension questions focus your attention on the most relevant parts of the very long book.
Comprehension questions are short, and if you understand the reading, you should be able to answer all the questions in just a few minutes. To achieve that understanding, however, substantial reading may be required.
Weekly recitation sections give you supervised practice working on problems that resemble the homework problems. Most recitations are scheduled when a new homework is just starting, so you can get off early, on the right foot. Recitations are small, which makes recitation an ideal place to ask questions, including the questions above. If you have a question, others in your recitation probably have a similar question. Recitations are mandatory, and they count toward your course grade.
Face-to-face interactions are invaluable. COMP 105 provides extensive office hours, conducted primarily by students who know the course and who know how to succeed. We spend a significant fraction of the course budget providing face-to-face office hours, so take advantage of this resource!
Office hours with the instructor are also available. Every student is expected to go to the instructor’s office hours at least once, for at least five minutes.
This syllabus contains a heavy helping of advice.
On the first day of class, we provide tips from the instructor, and we also provide advice from successful students.
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.
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:
Go to lecture. Using a pen, pencil, or stylus, take notes.
Go to recitation. Read the homework first.
Don’t try to swallow the textbook. To guide your reading, use the comprehension questions and other recommendations on the homework.
Look at the homework problems as soon as they come out. Think about them a little bit every day.
Talk about the homework problems with your friends and classmates. Some classmates may become new friends.
Join a study group.
Don’t work alone in your room. When you can, work in Halligan.
Take advantage of office hours.
If the going gets tough, have another look at this syllabus.
Read the handouts that describe experiences of top students in past classes and the instructor’s tips.
Build a “105-free zone” into your weekly schedule. Honor the zone even if you get behind, so that at least once a week you are sure to get a break from 105. (Because a homework is due every week, there are no structural breaks built into the course.)
Again, finally, and most important, do not allow yourself to become socially, emotionally, or intellectually isolated.
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:
It’s not just code; it’s math. All required 100-level CS courses have both code and math; the combination of code and math is the essence of the field. 105 is mostly code, but it still has lost of math; 160 is less code and more math; and 170 is almost all math.
You are responsible for your own learning. You can’t learn everything you need to know just by showing up at lecture. Lecture will give you the keys to the hard parts, but you need to tackle the book, and you need to fill in gaps on your own.2
Junior standing is recommended. 105 requires a degree of maturity that is not usually expected of freshmen and sophomores. Many students do take 105 as second-semester sophomores, but unless they are also strong in math, these students often struggle. It’s reasonable to postpone 105 until your junior year.
COMP 105 is built around two sets of skills:
Programming skills that exploit the best of the best programming-language features
Mathematical reasoning about code
The programming skills contribute to your professional practice, and the math contributes to several outcomes:
Math helps you communicate clearly about languages, language design, and language features.
Math is an ideal way to specify what programs do: it’s clearer and more precise than informal English, and it’s cleaner and more streamlined than a reference implementation.
Experience with programming-language math will help you evaluate future claims about languages (for example, claims about security).
Here are some of the detailed skills you will develop:
Read and write precise specifications of how languages work
Understand how it is possible to prove universal truths that apply to any program written in a given language
Write and reason about recursive functions
Capture common patterns of recursion in higher-order functions
Recognize and exploit common higher-order list-processing functions
Program with first-class functions as data
Prove correctness of code-improving transformations
Express rich control structures using functions as continuations
Design and implement polymorphic functions, methods, and data structures
Understand the merits of polymorphism in programming
Use types to guide the construction of code
Understand in detail what are the merits of type checking and how type checking works, including polymorphic type checking
Understand in detail what are the merits of type inference and how type inference works, including polymorphic type inference
Describe computations using the lambda calculus
Hide information using abstract data types, modules, and interfaces
Hide information using objects and protocols
Reuse code using inheritance
You will develop the skills above by studying these topics:
Functions
Types
Theory
Data abstraction
The workload in 105 is very heavy; under the new system, it will count 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.
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 assignments some ask you to apply theory to write code.
The course also has two exams: a midterm and a final.
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% how-is-my-participation-gradedParticipation in other class activities 5% Office-hour visit to the course instructor 5%
The weights may be adjusted at my discretion.
When determining final course grades, I consider the total picture, including not only all of your work but also any tendencies I have observed during the term. My final course grades should reflect a consistent standard, consistently applied.
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:3
Excellent work is outstanding in all respects. To be ranked excellent, the work must truly excel; that is, it must exceed expectations in some way.4
Excellent documentation addresses exactly the key issues, and degree of detail is exactly appropriate.
Excellent code is very well thought out and implemented. Excellent code shows mastery of new language features and idioms. On the rare larger assignments, Excellent code shows evidence of thorough attention to abstraction and modularity. Excellent code is so simple that it obviously has no faults. Instructors will see no obvious ways to make excellent code shorter or simpler. Excellent code is laid out consistently and uses scarce vertical space well. Excellent code is of such high quality that the course staff would be happy to maintain it.
Very Good work is of high quality in nearly all respects. An assignment that does everything asked for, and does it well, earns a grade of Very Good.
Very good documentation addresses most key issues, with a good amount of detail.
Very Good code shows correct, idiomatic use of new language features. On the rare larger assignments, Very Good code shows that some attention has been paid to abstraction and modularity, although one or two opportunities may have been overlooked. Very Good code contains well-chosen names for functions and their parameters, so that it is easy to guess what functions do. Instructors may see one or two ways to make Very Good code shorter or simpler. Layout is consistent and uses scarce vertical space well. Small errors may be evident from reading the code.
Good work demonstrates quality and significant learning.
Good documentation covers some key issues, but significant issues may have been overlooked or may be covered with insufficient detail. Vague generalities may appear where precise specifics are expected.
In Good code, individual functions are well organized and readable. Most names are well chosen, but there may be some exceptions. On the rare larger assignments, opportunities for abstraction and modularity probably have been overlooked. Good code gets the job done, but possibly in a way that could be shorter or simpler. Layout may be inconsistent in a few places. Errors may be evident from reading the code, but instructors will believe that code could be made correct with only modest changes.
Fair work is lacking in one or more aspects; key issues need to be addressed. “Fair” is the lowest satisfactory grade.
Fair documentation shows evidence of effort, but the degree of coverage and detail is significantly short of what the course staff believe is needed to foster success.
Fair code contains significant faults. Instructors may not be able to figure out what all functions do. Layout may be inconsistent or waste scarce vertical space (e.g., every other line may be blank). Fair code may show evidence of a ‘clone and modify’ approach to program construction. Names may be poorly chosen. Possibly a Fair program could be replaced by code half its size. Given Fair code, instructors may believe major changes would be required to make the code correct, or instructors may be unable to understand why the code might be correct.
Poor work shows little evidence of effort or has other serious deficiencies. “Poor” is an unsatisfactory grade.
Poor documentation may fail to address key issues or may address them perfunctorily.
Poor code may be undocumented or inappropriately documented (e.g., overcommented). Poor code is often lengthy, out of proportion to the problem being solved. Poor code may be laid out on the page in a way that is hard to read. Poor code often shows evidence of its history: extra copies of functions, unused logic left lying around, old code commented out, and so on. Poor code may be so complex that it has no obvious faults.
No Credit is received for work not turned in, for parts that are incomplete, or for work that is non-functional or appears to bear no relation to the problems assigned.
No Credit is received for work that is deemed to be plagiarized. Code submitted for Comp 105 may be examined for potential plagiarism using automated heuristics. Plagiarism is a form of academic fraud, which is unacceptable at Tufts. If academic fraud is suspected, appropriate steps will be taken. Submitting someone else’s work as your own is likely to lead to suspension or expulsion. It has happened to others. No Credit is received for work that you cannot explain.
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.
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. You will fill out a web form; the URL will be included with our report of your grade. We will reassess your entire assignment and assign a new grade. The new grade may be higher or lower than the original grade.
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.
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:
You can pick up the exam at any time during the availability period, but you must return it within two hours. This gives you 45 additional minutes: ample time to collect the exam, get to a quiet place, unpack, pack up, get back to Halligan, and turn in your exam.
If you have an accommodation that allows extra time on exams, the extra time applies only to the 75-minute portion, not to the administrative time. So for example if you are accommodated by having time and a half on exams, you will have 113 minutes for the exam itself and 45 minutes of administrative time. You will have to return the exam two hours and 38 minutes after you pick it up.
Pickup and dropoff are available only during business hours. We will try to make it possible for you to drop off your exam as late as 6:00 PM.
The exam will be available at the start of business on a Wednesday and will be due at 1:00 PM the following Friday. To guarantee that you have an available window of time to complete the exam, there will be no lecture on that Wednesday.
You must complete your midterm by yourself. You may not consult with others, and you may not consult sources on the Internet. You may, if you wish, consult the textbook or the lecture notes. But I encourage you to prepare for the midterm as you would prepare for the final, with one page of your own notes.
Once the midterm is available, you must not discuss it with any student who has not yet turned it in. This restriction applies even if you have not seen the exam yet.
If you have turned your midterm in, you may discuss it with other students who have also turned their midterms in. But such discussion must take place in private, where there is no possibility that someone else might overhear you.
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:
Very Good recitation participation means you contributed a question, answer, idea, or solution, and also engaged your classmates to help them contribute. Your recitation leader will model for you what this means. Very Good recitation participation also requires that you come to recitation having looked at the homework and that you are prepared to talk about the reading-comprehension questions.
Good recitation participation means you contributed, but you did not engage your classmates. Perhaps you spoke too much and didn’t leave room for others to contribute, or perhaps you simply behaved as if others weren’t there. Perhaps you had little idea of what was actually on the homework or you couldn’t say anything about the reading.
Fair recitation participation means only that you showed up.
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 him or her make contact with me.
A portion of your grade is based on your participation in 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.
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.
Discussions with classmates. Programming is a creative process. To help you think creatively, understand what the homework problems are asking, and discover paths to solutions, I encourage you to discuss the questions 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.
Once you reach the coding stage, however, discussions are no longer appropriate. Each program, unless explicitly assigned as a pair problem or a recitation problem, must be entirely your own work.
Practice work with classmates. Recitation will give you practice working out problems with the help of your classmates, under the supervision of a recitation leader. Your recitation leader will model and identify appropriate ways of talking about problems.
Deep work with one classmate. Much of the programming in 105 is about your individual understanding of new language features and new ideas, and to develop this understanding, you will tackle most programming problems on your own. In the real world, however, substantial artifacts are seldom built by individuals working alone. COMP 105 will therefore provide you with some opportunities to to build something substantial by working deeply with one classmate, not just on the ideas, but on the code itself. This is pair programming (more at Wikipedia).
In COMP 105, pair programming is always an opportunity, never an obligation. You are not required to work in pairs. If you do choose to work in a pair—which I recommend—know that no single pair may work together on more than three assignments. If you need help finding a partner, advertise on Piazza.
Interaction with faculty during lecture. 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?”
Interaction with faculty outside of lecture. One of your jobs 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 before Spring break. While you may find it helpful to talk about homework, class, engineering, or Tufts overall, any mutually agreeable topic of conversation is acceptable.
Office-hour visits after Spring break still count toward your course grade, but not for the full five percent.
Interaction online. At any time of day or night, you can post a comment or question to Piazza. If your question contains any of your code, you must send it in email instead. Questions on Piazza should be suitable for public consumption. Please make your question visible to everyone, so you get participation credit for asking it, and your classmates have a chance to help you by answering it. (By helping to answer your question, your classmates improve their own grades for class participation. Similarly, you can improve your grades by answering other people’s questions—but your answers must not contain any code you have developed for the assignment. Do as you would be done by, and everyone wins.)
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.
We make every effort to answer posted questions in a timely fashion. But if you have posted a question to Piazza and have 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, which are online.
Questions that include code you are working on (or code you have written) are not suitable for Piazza. Please send such questions to comp105-grades@cs.tufts.edu
. Please never send a question directly to the course staff using their personal email addresses. In rare cases, you may have an issue that is not appropriate for the whole course staff to see. In such cases, please do send email to my personal account.
Interaction with course staff in real life. The course staff are here to enhance your learning; it is part of their job. Please interact with course staff using the same professional manners and standards you would use in any workplace. Please also recognize that COMP 105 is only part of anyone’s job: a member of the course staff may be present but not actually available to talk about 105.
Interactions and discussions with classmates must take place in English, at a high level. You must not discuss code, and you must not exchange English, pseudocode, or other information that is expressed at the level of code. If you start communicating in code or at the level of code, you’re breaking the rules.
While I encourage shared work at the whiteboard or in notebooks, if your shared work is so detailed or low-level that there is only one reasonable translation into code, you are collaborating too closely.
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 violates the University’s academic regulations.
Do not, under any circumstances, post a question to Piazza that contains any part of your code. Such questions should be emailed to the course staff.
Suspected violations will be reported to the University’s Judicial Officer for investigation and adjudication. 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!
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. If your homework appears on a public github repository, I am mandated to report it as a violation of academic integrity (facilitating misbehavior by others).
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.
If you are in the middle of a pair-programming project and your partner has to travel for a day or two, it is permissible for you to continue working together using a tool like TeamViewer, provided that you also maintain a real-time audio connection. (TeamViewer allows two programmers to work on one computer by enabling one computer to “control” another.)
You submit a single program under both your names. That work gets one grade, which you both receive.
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:
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.
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.
In COMP 105, you are never required 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:
Notify your partner that you wish to discontinue the pairing. You needn’t explain yourself; a simple wish to stop is reason enough.
Submit the work done in partnership at that point, even if it is incomplete or broken. That work is “community property” and both students may submit it.
If you wish, follow up with an additional submission of whatever you complete on your own.
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.
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.5 On most assignments, there are some additional checks:
Code you submit must be accepted by the appropriate compiler or interpreter without any warning or error messages.
Unit tests submitted as part of your solution must pass, and the entire file must load, including testing, in at most 500 CPU milliseconds. If you have created long-running test cases, place them in a separate file.
Normally you should change to the directory in which you have placed your solutions and run the script. 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 course staff are expecting.
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
.
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
Identify you by name (and on the first assignment, please tell us how to pronounce your name; for example, the instructor’s name might be pronounced “kaeth-LEEN FIH-shur” or “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.
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.
The structure and organization of your code is evaluated according to our general coding rubric, which is online.
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.
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 three ways to get it:
The big copier in the CS office has a document feeder and a Scan button. The scan is formulated as PDF and is sent to an email address you designate.
If you have a smartphone with a decent camera, there are many scanning apps. I recommend Scanbot, which is free for both Android and iOS.
If you have no other alternative, there is a scanner attached to a Windows machine in Halligan 122. Instructions are online.
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.
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.
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. You can earn an A or A+ without doing any extra credit.
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:
For ordinary difficulties, each student is automatically issued seven “extension tokens.” By expending an extension token, you get a 24-hour extension on all deadlines associated with a single assignment. It happens automatically; when you turn in any piece of work more than fifteen minutes late, the course software charges you one extension token.
Expenditure of extension tokens is governed by these rules:
If a serious illness affects your ability to complete homework on time, your first step is to report the illness using SIS. This step alerts us about your illness. We will then make suitable arrangements.
If you experience extraordinary difficulties, such as bereavement, family emergencies, or similarly unpleasant events, please begin by making contact with your associate dean for undergraduate education. Please 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.
After the 24-hour extension deadline has passed, solutions to homeworks will be available on the Web or distributed as hard copy in class.
If you can’t finish every problem, act tactically to maximize your grade:
Start every problem. Turn in, if you can, a partial solution, or at least an analysis. Incomplete work might still earn a grade of Poor, or possibly even Fair.
If you turn in nothing for a problem, you get nothing for it. “No Credit” means zero. That’s very bad for your grade. If you have to choose between two problems of equal weight, it is slightly better to get two Poor grades than to get one No Credit and one Very Good. You can’t just scribble down anything and expect to receive a Poor grade—the course staff have to be able to find some substance. But if you document some progress, the outcome will be good for you.
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.
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.
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:
The neuroscience is quite clear that note-taking with pen or pencil activates most of the brain. Note-taking using a keyboard activates a much smaller region.
Word-processing software is terrible for note-taking. Your notes should be about highlights and connections: good notes connect more recent material with material from earlier in the lecture; good notes contain diagrams; good notes contain arrows and boxes. Good notes are highly non-linear. A word processor is designed to produced polished final documents, not to take notes. Use the superior tool: pencil and paper.
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.
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.
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.
Before your recitation, you are expected to have looked at the current homework assignment, and you are expected to have read enough to talk about the comprehension questions on the homework.
During recitation, you will discuss and tackle problems. You are expected to contribute, to engage your classmates, and to make sure your classmates have room to contribute.
Recitation is mandatory, and your participation is graded.
Attend the recitation you signed up for on SIS when you registered for COMP 105. In order to create a small-group learning environment, we cap the enrollment of each recitation section. This cap is strictly enforced.
If your recitation section has been cancelled, or if there is another reason you need to change recitations, please email comp105-grades@cs.tufts.edu
, and please
Here is a summary of relevant information that is distributed throughout this syllabus:
Homework must be submitted using a submit script.
You can get one automatic 24-hour extension by expending one “extension token.” You have a total of seven such tokens. On any given assignment, you can expend at most one token.
Code must compile or load with no errors or warnings, and it must do so within 250 CPU milliseconds.
Except when you are pair programming, another student must never see your code.
Any homework question can be posted publically to Piazza, unless that homework question contains code, an inference rule, or another part of the solution. Any question that discloses your work must be emailed to comp105-grades@cs.tufts.edu
.
If needed, you have 7 days to request a regrade, which you do via a Web form.
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.
If your research is going to depend on your ability to design, write, and evolve good software, take 105.
If you’re curious about programming languages as a potential area of research, consider taking 105. Just keep in mind that 105 is designed to be required of all undergraduate students. That makes it light on research and heavy on practice.
If you know you’re interested in programming languages and you want to study core programming-language topics at a graduate level, 105 is going to disappoint you—it’s not operating at the right level. 105 is a first course in the field. As such, it just touches on the rudiments of theory, and it omits many other interesting topics, including logical relations, denotational semantics, garbage collection, and logic programming.
If what you want is to meet the proficiency requirement for the PhD qualifying examination (“functional programming and object-oriented programming with inheritance”), 105 is one of several options. The proficiency requirement is minimal, and 105 presents a broad and deep view of programming languages that goes beyond minimal proficiency. If that’s what you’re looking for, great! But it’s an intense experience that may take time away from your research. If you’re looking to do the minimum needed to meet the requirements for the PhD qualifying exam, you have other alternatives. Come to my office hours, and I’ll be happy to talk about them.
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.
You must grasp basic algorithms, data structures, and good programming practice.
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.
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.
If you use the copier in the CS office, you will be emailed a PDF attachment.
If you use the Scanbot app on a smartphone, you can get Scanbot to upload to a service like Google Drive, from which you can then download to the servers.
If you use some other means of creating the PDF, getting it to the servers is up to you. Various students report good results with Swift File Transfer from Android devices and scp
(from the OpenSSH suite) from computers.
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.
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.
This course uses unusual programming paradigms, and it really helps to have some facility with systematic software design. Although this material is not required, you will be prosper 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 functions6
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. And Ramsey’s Chapter 8 presents several examples of representation invariants and abstraction functions.
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:
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.
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.
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 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; you can try a free online book by Robert Harper or various other ML resources. If you do buy Ullman’s book, be sure you get the ML’97 edition. It is available in the University bookstore.
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 linux.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
as your login shell.
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.
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 using Webex. 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, again using Webex.
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.
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.
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.
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.
Lisa Feldman Barrett, “How to Become a ‘Superager’”, New York Times, Dec. 31, 2016↩
“On your own” means “with the help of your classmates and your teaching assistants.”↩
It is the same scale used by the National Science Foundation and by Consumer Reports.↩
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.↩
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
.↩
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.↩