CAS CS 131  Fall 2017  Combinatoric Structures
Syllabus
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.)
What this means in reality: we will train you in the mathematical foundations of CS so
that you can make convincing logical arguments (proofs) that programs you write and algorithms you
design are correct and run efficiently. The term "combinatorics" is centered on combinations
of objects belonging to a finite set  we will see applications in counting and probability
theory. For example, we will teach you things like how to compute the probability of randomly
guessing an alphanumeric password, or (similarly) how many Bitcoins you can expect to
mine with a given amount of computation.
Instructors and Teaching Fellows
Prof. John W. Byers
Homepage: http:// www.cs.bu.edu/fac/byers
Email: byers @ cs . bu . edu [preferred]
Office Hours: Tues 10:3012:30 AM (open) and Wed 1011 AM (by prior appointment), in MCS 295B.
During office hours, if it's not too busy, I'll answer my phone at 6173538925.
Other times, I generally let phone calls go to voicemail. Please send email instead.
Prof. Charalampos Tsourakakis
Homepage: https://tsourakakis.com
Email: tsourolampis @ gmail . com [preferred]
Office Hours: Tues 56:30 and Fri 910:30AM in MCS 292.
Teaching Fellows: Wonyl Choi, Konstantinos Sotiropoulos
Learning Assistants: Ben Lawson, Johnson Lam
Email: {wonyl, ksotirop, balawson, jlam17} @ bu . edu
Office Hours, held in EMA 302 (or 303) unless otherwise noted:

Tuesday: 122 [Johnson]

Wednesday: 1011:30 [Wonyl] in MCS B24

Thursday: 12 [Johnson], 57 [Ben], 57 [Konstantinos, when homeworks are due the next day], 11  1 [Konstantinos, all other weeks]

Friday: 1011 [Konstantinos], 1:303 [Wonyl], 34 [Ben]
The class will be cotaught by Professors Byers and Tsourakakis. On any given lecture date, one of the two
instructors will deliver the lecture for both the A1 and B1 sections. A twoperson team from the TFs and LAs
will lead each of the discussion sessions. The objective is to reinforce the concepts covered in the lectures through
problemsolving, and to provide some clarifications and guidance on the homework assignments.
The purpose of the office hours of the Instructors, the Teaching Fellows and the Learning Assistants
is to answer specific questions or clarify specific issues. Your fastest route to get an answer to
most questions is via Piazza. Office hours are not to be used to fill you in on a class you skipped or to
reexplain entire topics. Office hours are scheduled at times to provide help to students on the homework.
Office hours earlier in the week are invariably much less crowded.
Lectures
Lecture A1: Tues/Thurs 3:30  4:45 PM, CAS B12.
Lecture B1: Tues/Thurs 2  3:15 PM, CAS B12.
We expect students to come to class, and come on time.
While the class is large, class participation and questions will be encouraged.
Also, while our textbook will be very helpful, it is an imperfect substitute
for inclass 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 9:05  9:55AM, MCS B25
Lab A3: Wed 3:35  4:25PM MCS B25
Lab A4: Wed 4:40  5:30PM EPC 206
Lab B2: Wed 12:20  1:10PM, MCS B33
Lab B3: Wed 1:25  2:15PM, MCS B23
Lab B4: Wed 2:30  3:20PM, MCS B23
Labs will be an invaluable part of the course typically involving interactive
problemsolving sessions and further guidance on homework questions.
Attendance is mandatory and will be taken.
There will be no lab on Wed, 9/6. The first lab will be on Wed, 9/13.
Textbook
Discrete Mathematics and Its Applications, Kenneth H. Rosen, 7th Edition. ISBN 9780073383095.
Communications:
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 the instructors.
Please do not email questions to the teaching staff  post your questions on Piazza instead.
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:
https://piazza.com/bu/fall2017/cs131/home.
Please go there to sign up today.
We will also use Piazza to post announcements and all handouts, including homework assignments and solutions.
Grading and Attendance
The course grade will break down as follows:
 Problem sets: 30%
 Midterms: 35%
 Final exam: 30%
 Lab attendance and participation in {lab, lecture, Piazza}: 5%
Last day to drop without a W: Oct 10. With a W: November 10. Our midterms are scheduled with these dates in mind.
Incompletes for this class will not be granted.
Exams:
There will be two inclass midterms held during the
middle of the semester, tentatively Thursday, October 5 and
Thursday, November 9.
The cumulative final will be held during the normal
twohour final exam slot: Saturday, Dec 16, 35PM for students in the 2PM lecture
and Tuesday, Dec 19, 35PM for students in the 3:30PM lecture. All exams will be in MCS B12.
Please make your endofsemester travel plans accordingly!
Homework Assignments, Submission, and Late Policy:
Assignments will typically be due Fridays at 5PM.
You must submit a *stapled* 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.
Plan on assignments being due every week, except right after a midterm,
tentatively Sep 15, Sep 22, Sep 29, Oct 13, Oct 20, Oct 27, Nov 3,
Nov 17, Dec 1, Dec 8.
We will collect assignments and post solutions at 5PM sharp, so
homework assignments will not be accepted late. Therefore, do NOT cut it close!!
To compute your homework grade, we will automatically drop the one
lowest score from the 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 one of
the Professors in lecture. 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. Attendance will be taken in labs.
Often, some material covered in lecture and lab will not be covered by
our textbook. We ask that you please arrive to all classes on time,
since it is disruptive to have students flowing in throughout the class
period. When students are at a borderline between grades, we will
factor in attendance and participation before making a final determination.
Tentative Schedule
 Lecture  Topic  Readings  Homework Due Dates 
 9/5  Introduction to Proofs and Logic  Chapter 1.7, 1.1  
 9/7  Propositional Logic  Chapter 1.11.2  
 9/12  Logic circuits and satisfiability  Chapter 1.3  
 9/14  Predicates and quantifiers  Chapter 1.4  HW 1 due 9/15 
 9/19  Nested quantifiers  Chapter 1.5 (& skim 1.6)  
 9/21  Proof methods and techniques  Chapter 1.7  1.8  HW 2 due 9/22 
 9/26  Basic Structures: espec. Sequences, Sets, Sums  Chapter 2.1 (review) and 2.4  
 9/28  Intro to Induction  Chapter 5.1  HW 3 due 9/29 
 10/3  Induction proofs   
 10/5  Midterm 1, covers lectures through 9/28   
 10/10  No class (Columbus day turns Tuesday into a Monday)   
 10/12  Strong Induction  Chapter 5.2  HW 4 due 10/13 
 10/17  Number Theory Basics  Chapter 4.1  4.2  
 10/19  Number Theory: prime factorization and GCDs  Chapter 4.3  HW 5 due 10/20 
 10/24  Number Theory  Congruences and applications  Chapter 4.4  4.5  
 10/26  Number theory  crypto and coding  Chapter 4.54.6  HW 6 due 10/27 
 10/31  Algorithms, bigO notation  Chapter 3.2  3.3  
 11/2  Recursive algorithms  Chapter 5.4  HW 7 due 11/3 
 11/7  Recursion and recurrence relations  Chapter 8.1  
 11/9  Midterm 2, covers lectures through 11/2   
 11/14  Divide and conquer algorithms, master method  Chapter 8.3  
 11/16  Counting  Chapter 6.1  HW 8 due 11/17 
 11/21  Counting  Chapter 6.2  

 11/23  No Class (Happy Thanksgiving!)   
 11/28  Counting  Chapter 6.3  
 11/30  Counting  Chapter 6.4  HW 9 due 12/1 
 12/5  Probability  Chapter 7  
 12/7  Probability  Chapter 7  HW 10 due 12/8 
 12/12  Probability  Chapter 7 

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.
 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:
 Before discussing each homework problem with anyone
else, you must give it an honest halfhour of serious thought.
 You may discuss ideas and approaches with other students in the class, but not share any
written solutions. In other words, the writeups you submit must be entirely your own work.
You must also acknowledge clearly in the appropriate portion of your solutions
(e.g., at the top of your writeups) people with whom you discussed ideas for that portion.
 You may get help from TFs and undergrad assistants for the class for specific problems.
Don't expect them to do it for you, however.
 You may not work with people outside this class (but come and talk to us if you
have a tutor), seek online solutions, get someone else to do it for you, etc.
 You are not permitted to collaborate on exams.
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.