CS131 - Combinatoric Structures

Instructor: Prof. Lorenzo Orecchia.
Office hours: M 12n-1p, F 1p-2p, in MCS 135D.

Teaching Fellow: Hannah Flynn (hmflynn at bu.edu)
Office hours: T 2-3.30pm, W 5-6.30pm in the Undegraduate Lab.

Undergraduate Assistants:
Jiadong Chen (chenjd at bu.edu)
Tutoring hours: T6-7.30 in the Undergraduate Lab
Sarah M’Saad (sarms at bu.edu)
Tutoring hours: W5-6.30 in the Undergraduate Lab

Lectures: Tue,Thu 3.30pm-4.45pm in KCB-101.
Labs:
A2: Wed 11.15am-12.05pm, in MCS B33
A3: Wed 1.25pm-2.15pm, in MCS B25
A4: Wed 2.30pm-3.20pm, in MCS B21
A5: Wed 3.35pm-4.25pm, in BRB 122

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.

Class Websites

This webpage will not update during the course. All communications and course administration will be managed through the two following websites:

• We will use Piazza for class discussion. Our class page is located at: https://piazza.com/bu/spring2017/cs131/home. Please sign up for access here. We will also use Piazza to post announcements,homework assignments, handouts and other communications. We 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 the Blackboard website for CS131 for its gradesheet capability and for some self-assessment tasks.

Clickers

During lecture, we will be using clickers as an audience response system. All students should set up a clicker (or use the equivalent smartphone app) and register it for CS 131 by following the instructions here.

Textbooks

The main textbook for this class will be Discrete Mathematics and Its Applications by Kenneth Rosen. The book is also available at the campus bookstore.

At the beginning of the term, we will learn the basics of logic, set notation, and elementary proof techniques. If you are unfamiliar with devising and writing proofs, you may consider the textbook How To Prove It: A Structured Approach by Daniel Velleman. Available on Amazon and at the campus bookstore.

Exams

There will be two in-class midterms:

• Thursday, February 16. Info for midterm 1
• Thursday, March 23 Tuesday, March 28. Info for midterm 2

There will also be a final at the end of the semester.

Homework Assignments

Assignments will typically be due Thursday 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 marked CS131, not on the shelves above. 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 10 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 score will be broken down as follows:

• Problem sets: 20%
• Midterms: 40%
• Final exam: 35%
• Attendance and participation: 5%

The process of turning scores into grades will be mostly based on the relative score compared to the class as a whole, with a smaller component depending on the absolute value of the score. We will strive to provide the students with predicted letter grades after each midterm.

Last day to drop without a W: February 23. With a W: March 31. 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:
• Before discussing each homework problem with anyone else, you must give it an honest half-hour 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 on-line 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.