CAS CS 131, Combinatoric Structures Spring 2011

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 CS Background Course for the concentration.)

Prerequisites

Basic (high school level) calculus and algebra.

Lectures

Tues-Thur 2-3:30 pm, GCB 205.

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 Labs

Lab: MCS B29, Fri, 11:00am-12:00pm
Lab: MCS B33, Fri, 2:00pm-3:00pm
Lab: MCS B29, Mon, 1:00pm-2:00pm

Web page for the labs

Instructor

Evimaria Terzi, evimaria@cs.bu.edu
Office Hours: Tuesday 3:30 pm - 5:00 pm and Wed 9:30 am -11:00 am or by appointment.
Evimaria’s office: MCS280
www.cs.bu.edu/~evimaria

Teaching Assistant

Konstantin Voevodski, kvodski@bu.edu
http://cs-people.bu.edu/kvodski/
Office Hourse: Thursday 3:30pm - 5:00pm and Fri 12:30pm - 2:00pm.
Konstantin’s office: PSY223
http://cs-people.bu.edu/kvodski/

The Teaching Fellow will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures, 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.

Textbook

There is no perfect textbook that covers all the material of this course from a CS perspective. We will mostly 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 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 cons and they can be quite expensive!

Grading Policy

Incompletes will not be given.

Late assignments will not be accepted. The assignment grade will be the average over all assignments (the two lowest-grade assignments will be ignored).

Mailing List

cascs131-l@bu.edu

(Tentative) Schedule

Jan 18, 20 Introduction: Logic and Proofs Chapter 1
Jan 25 Problem Set 1; Deadline Feb. 1 download, solutions
Jan 25, 27 Proof by Induction I Chapter 2
Feb 1 Problem Set 2; Deadline Feb. 8 download,solutions
Feb 1, 3 Proofs by Induction II Chapter 3
Feb 8 Review Class review,solutions
Feb 10 Exam 1
Feb 15, 17 Sums and Approximations Chapters 10, 11
Feb 17 Problem Set 3; Deadline Feb 25 download,solutions
Feb 22 No Class; Monday Schedule
Feb 24 Recurrences Chapter 12
Mar 1 Problem Set 4; Deadline March 8download,solutions
Mar 1, 3 Recurrences Chapter 12
Mar 10 Problem Set 5; Deadline Mar 24download, solutions
Mar 8,10 Recurrences Chapter 12, 13
Mar 15,17 Spring Break
Mar 22 Review Class
Mar 24 Exam II
Mar 29 Problem Set 6; Deadline April 5download,solutions
Mar 29,31 Counting Chapters 14, 15, 16
April 5, 7 Counting Chapters 14, 15, 16
April 12 Problem Set 7; Deadline April 21 download,solutions
Apr 26,28 Probability Chapters 18, 19, 20
April 26 Problem Set 8; Deadline May 5 download,solutions
May 3 Probability
May 5 Review Review, Solutions

Collaborations and Academic Honesty

Course participants must adhere to the CAS Academic Conduct Code. All instances of academic dishonesty will be reported to the academic conduct committee. Collaboration/Academic Honesty

I encourage you to discuss course material and even problem sets with other students in the class (esp. 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.