CAS CS 131, Combinatoric Structures

Fall 2012

Course Description

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

You can fined the full syllabus here.


Basic (high school level) algebra, set theory and calculus.

Course News and Homework

Here is the most recent CS 131 Course News .

Here is the current homework: HW 6.

Here is the list of previous homeworks: HW 0, HW 1, HW 2, HW 3, HW 4, HW 5.

Here are answers to some of the problems in : HW 1, HW 2, HW 3, HW 6.

Here are some extra problems on induction and recurrences for the final, and answers to some (1/2) of them are here.


Tues-Thur 3:30-5:00 am, CAS 313.

I expect you to come to lectures (on time!) and I encourage you to participate. There is no perfect textbook for the class, and lectures are your important source of information. Be sure to take good notes.

Discussion Sections - all on Wednesday

Discussion sections begin the second week of class.

Lab: MCS B23, Wed, 11:00am-12:00pm
Lab: MCS B23, Wed, 1:00pm-2:00pm
Lab: MCS B23, Wed, 2:00pm-3:00pm

Web page for the labs


Steve Homer,
Office Hours: Tuesday 2:00 - 3:00 and Thursday 1:00 - 2:00 or by appointment.
Office: MCS281

Teaching Assistant

Maryam Ghasemi
Office Hours: Monday, 3:00 - 5:00 in PSY 223, and Wednesday 5-6 in the undergard lab at 730 Comm. Ave.

Maryam ’s office: PSY 223

The Teaching Fellow will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures, introduce some additional material and answer questions (or provide clarifications) regarding the homework assignments.

The purpose of the office hours of the Instructor and Teaching Fellow 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 explain entire topics. Please come to class and to your discussion session.


There is no perfect textbook that covers all the material of this course from a CS perspective. The main textbook is, "How to Prove It," by Dan Velleman, published by Cambridge Press. We will often make use of the following online notes. Do not print anything yet! The notes are 339 pages long, so you might consider printing them out in chapters as we get to them rather than all at once. We won’t cover all chapters anyway.

Notes for MIT’s CS 6.042 course (PDF format), by Eric Lehman and Tom Leighton, 2004.

Together with the textbook and your lecture notes, these notes should be quite sufficient, but if for some reason you want to do additional reading, you might consider some discrete mathematics book, e.g., Discrete Mathematics and Its Applications, by Kenneth H. Rosen, McGraw Hill. However, be warned: each discrete math book has its weaknesses and the books can be quite expensive!

Mailing List

Collaboration/Academic Honesty

I encourage you to discuss course material and even problem sets with other students in the class (e.g. on the class mailing list), subject to the following rules:

I expect you to follow these rules as well as the academic conduct code of CAS/GRS. If you have any questions or are not sure what is appropriate, consult me before taking steps that you are afraid may violate the rules.

If you violate the academic conduct code, you will be reported to the Academic Conduct Committee.