CAS CS 131 - Spring 2015 - Combinatoric Structures


Official Course Description

Representation, analysis, techniques, and principles for manipulation of basic combinatoric data structures used in computer science. Rigorous reasoning is emphasized. (Counts as a Background Course for the CS concentration.)

Prerequisites: Basic (high school level) calculus and algebra.

Course Handouts Page

Our Piazza page (includes lab handouts)


Lecture A1: Tues/Thurs 11 - 12:30 PM, CAS 224.

I expect students to come to class, and come on time. Attendance is mandatory. While the class is large, class participation and questions will be encouraged. Also, while our textbooks will be very helpful, they are an imperfect substitute for in-class learning, which is the fastest (and easiest) way to learn the material. If you miss a class, please get the notes and work through the material from a fellow student.

Discussion Labs

Lab A2: Wed 11-12AM, SCI 115
Lab A3: Wed 1-2PM, MCS B23
Lab A4: Wed 2-3PM, MCS B21
Lab A5: Wed 3-4PM, COM 213

Labs will be an invaluable part of the course involving interactive problem-solving sessions, tips on homework questions, and supplemental material not covered in lecture. Attendance is mandatory and will be taken. There will be no lab on Wed Jan 21 -- labs will start on Wed Jan 28.


Prof. John W. Byers
Homepage: http://
Email: byers @ cs . bu . edu [preferred]

Office Hours (in MCS 270):  Tues 1:30 - 3, Fri 10 - 11:30.
For technical questions beyond what Piazza can answer (see below), or when you are really stuck on a problem.
During office hours, if it's not too busy, I'll answer my phone at 617-353-8925.
Other times, I generally let phone calls go to voicemail. Please send email instead.

"Coffee Hours" (at Pavement Coffeehouse, 736 Comm Ave):  Fri, 9:30 - 10:00
Right before regular office hours. For casual questions, or just to say hi.

Everyone is required to stop by Coffee Hours or come to Office Hours at least once during the semester. Earlier in the semester is better!

Teaching Fellows

TF: Matthew Danish
Email: md @ cs . bu . edu
Office Hours: Thurs 2:30 - 5:30 in the undergrad lab, EMA 302.
He also has tutoring hours TBD in EMA 302, but those might be more crowded.

Matthew will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures through problem-solving, and provide clarifications regarding the homework assignments. The purpose of the office hours of the Instructor and Teaching Fellows is to answer specific questions or clarify specific issues. Office hours are not to be used to fill you in on a class you skipped or to re-explain entire topics. Please come to class and to your discussion session.


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 I'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 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.

Together with your lecture notes, the above material will be more than sufficient, but there are many other discrete mathematics books out there that some CS 131 students have found helpful in years past, for example Discrete Mathematics and Its Applications, by Kenneth H. Rosen, and Discrete Mathematics, by Richard Johnsonbaugh. There are also tons of extra practice problems online, just a Google search away.


This term we will be using Piazza for class discussion. The system is highly catered to getting you answers to your questions fast and efficiently from classmates, the TF, and myself. 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!). Our class page is located at: Please go there to sign up today. We will also use Piazza to post announcements, homework assignments, etc.

Grading and Attendance

The course grade will break down as follows: Last day to drop without a W: Feb 24. With a W: April 3. Our midterms are scheduled with these dates in mind.
Incompletes for this class will not be granted.

Exams:     There will be two in-class midterms held during the middle of the semester, tentatively Thursday, Feb 18 and Thursday April 2. The cumulative final will be held during the normal two-hour final exam slot for classes in our time block: Fri, May 8 from 12:30-2:30PM. Please make your end-of-semester travel plans accordingly!

Homework Assignments, Submission, and Late Policy: Assignments will typically be due Fridays at 5PM. You must submit a hardcopy no later than 5PM 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, tentatively Jan 30, Feb 6, Feb 13, Feb 27, Mar 20, Mar 27, Apr 10, Apr 17, May 1.

We will post solutions at the 5PM 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. As you likely already know, assignments requiring substantial creativity can take more time than you expect, so plan to finish a day early.

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 Prof. Byers 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 I will take attendance at the beginning of lecture on occasion. Some material covered in lecture and lab will not be covered by our textbooks. I also ask that you arrive in class on time, since it is disruptive to have students flowing in throughout the class period. Moreover, when students are at a borderline between grades, I will factor in attendance before making a final determination.

(Tentative) Schedule

Jan 20, 22 Introduction to Logic HTPI and MIT notes, Chapter 1
Jan 27*, 29 Quantificational Logic Chapters 1 and 2 from HTPI
Feb 3, 5 Proofs HTPI and Ch. 2 from MIT notes
Feb 10*, 12 Proof Strategies Chapter 2, MIT notes (also in HTPI)
Feb 17 No class -- Monday schedule
Feb 19 In-class Midterm I
Feb 24, 26 Induction Chapter 3, MIT notes
Mar 3, 5 More induction Chapter 3, MIT notes
Mar 10, 12 No class -- Spring Break
Mar 17 Number theory: GCD, unique factorization, Turing code.Selections from Chapter 4
Mar 19 Basic Sums and Products Chapter 9.1 from MIT notes
SATURDAY Mar 21 Asymptotic Notation Chapter 9.7 from MIT notes
Mar 24, 26Asymptotics and Recurrences Chapter 10 from MIT notes
Mar 31 Recurrences 10.1, 10.2, start of 10.3
Apr 2 In-class Midterm 2
Apr 7 Master theorem. Counting 10.4.4, Ch. 11 from MIT notes
Apr 9 Counting Chapter 11 from MIT notes
Apr 14, 16 Counting and probability Chapter 14.1-14.3 from MIT notes
Apr 21 Conditional probability Chapter 15.1-15.4 from MIT notes
Apr 22 No Lab (Monday schedule)
Apr 23 Class cancelled (John traveling)
Apr 28 Conditioning and independence Chapter 16.1 from MIT notes
Apr 30 Wrap up independence. Review
Fri May 8 Final Exam, 12:30-2:30PM
* = Snowed out. We plan to make up one of these on our scheduled makeup day: Saturday, Mar 21.

Academic Conduct

Academic standards and the code of academic conduct are taken very seriously by our university, by the College of Arts and Sciences, and by the Department of Computer Science. Course participants must adhere to the CAS Academic Conduct Code -- please take the time to review this document if you are unfamiliar with its contents.

Collaboration Policy

The collaboration policy for this class is as follows. The last point is particularly important: if you don't make an honest effort on the homework but always get ideas from others, your exam scores (accounting for the majority of your grade) will reflect it.