CS 131 Fall 2015: Combinatoric Structures

This is not the current version of the class. The current (Spring 2017) offering is here

Instructor: Prof. Lorenzo Orecchia, MCS 135D. Office hours: TBA
TA: Zhenyu Liao, MCS 135B. Office hours: Monday 4pm-5.30pm.

Lectures: Tue,Thu 3.30pm-5pm in CAS 522.
Labs: all labs meet in MCS B23,

A2: Wed 11am-12pm,

A3: Wed 1pm-2pm,

A4: Wed 2pm-3pm,

A5: Wed 3pm-4pm.

Syllabus: see the tentative course schedule here.

Official Course Description

Representation, analysis, techniques, and principles for manipulation of basic combinatoric structures used in computer science. Rigorous reasoning is emphasized. The course is a required class for CS concentrators.

Prerequisites: high school mathematics.


We will use Piazza for class discussion. Our class page is located at: https://piazza.com/bu/fall2015/cs131/home. Please sign up for access here. We will also use Piazza to post announcements, homework assignments, handouts and other communications.

The system is highly catered to getting you answers to your questions fast and efficiently from classmates, the TF, and the instructor. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. We also encourage you to post answers to student questions there (but obviously, not answers to problems on the problem sets!). Your activity on Piazza may be taken into account as part of the participation component of your grade.


We will use two primary sources for this course. At the beginning of the term, we will learn the basics of logic, set notation, and elementary proof techniques. To do so, we will cover material from the first few chapters from the following textbook, which we'll refer to as “HTPI”:How To Prove It: A Structured Approach, by Daniel Velleman, 2006. Available on Amazon and at the campus bookstore.

At that point, we will switch over to our other primary reference, the following set of online notes used for MIT's CS 6.042 course, Mathematics for Computer Science (PDF format) , by Eric Lehman, Tom Leighton, and Albert Meyer, 557 pages. There are lots of different editions out there; note that we'll be using the September 8, 2010 revision. We recommend that you print the material we cover as we go, since we will cover only about half of these notes.


There will be two in-class midterms held during the middle of the semester, tentatively Thursday October 1 and Thursday November 5. The cumulative final will be held during the normal two-hour final exam slot for classes in our time block: CORRECTION: Friday, December 18(and NOT Thursday, December 17) from 3:00-5:00PM. Please make your end-of-semester travel plans accordingly!

Homework Assignments

Assignments will typically be due Tuesday at 12PM noon. You must submit a hardcopy no later than 12PM noon in the drop box on the first floor of the MCS building, near the CS department office. From the CS office, walk toward the shorter end of the hallway, and turn right. Drop box is immediately on your right. Assignments must go in the box, not on the shelves above, which is where we will return assignments. Plan on assignments being due every week, except right after a midterm.

We will post solutions shortly after the noon deadline, so homework assignments will not be accepted late. To compute your homework grade, we will automatically drop the lowest score from the 9 assignments, so one bad homework grade is not the end of the world. However, we strongly recommend putting forth your best effort on all assignments, as they provide the best preparation for the exams.

Grading and Attendance

The course grade will break down as follows:

Problem sets: 30%

Midterms: 30%

Final exam: 35%

Attendance and participation: 5%

Last day to drop without a W: October 7. With a W: November 6. Our midterms are scheduled with these dates in mind.

Course Policies

Regrading Procedure: If, after reviewing the posted solutions, you still believe a portion of your homework was graded in error, you may request a regrade. Please write, on a PostIt, the problem number and a brief description of the incorrect deduction, stick it on your homework, and give it to the instructor or the TA for a regrade. Note that when we regrade a problem, your score may go up or down.

Attendance: It is expected that you will attend lecture and the laboratory section for this course and we will take attendance at the beginning of lecture and lab on occasion. Some material covered in lecture and lab will not be covered by our textbooks.

Collaboration Policy: You are encouraged to collaborate with one another in studying the textbook and lecture material. As long as it satisfies the following conditions, collaboration on the homework assignments is permitted and will not reduce your grade: