CAS CS 131 - Fall 2014 - 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.)
Prerequisites: Basic (high school level) calculus and algebra.
Course Handouts Page
Our Piazza page (includes lab handouts)
Lectures
Lecture A1: Tues/Thurs 3:30 - 5PM, CAS 522.
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, MCS B23
Lab A3: Wed 1-2PM, MCS B23
Lab A4: Wed 2-3PM, MCS B25
Lab A5: Wed 3-4PM, GCB 208
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.
Instructor
Prof. John W. Byers
Homepage: http:// www.cs.bu.edu/fac/byers
Email: byers @ cs . bu . edu [preferred]
Office Hours (in MCS 270):
Tues 10:30 - 12:00, Fri 10 - 11:30 (updated 10/13/14).
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 (updated 10/13/14).
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
Full-time TF: Harshal Chaudhari
Homepage: cs-people.bu.edu/harshal/index.html
Email: harshal @ bu . edu
Office Hours: Mon 2-3, Tues 12-1, Thurs 12-1 in the undergrad lab, EMA 302.
He also has tutoring hours Mon 3-4 in EMA 302, but those might be more crowded.
Harshal will lead discussion sections A3, A4, A5.
Half-time TF: Hannah Flynn (she's also half-time on CS 330)
Email: hmflynn @ bu . edu
Office Hours: Wed 12-2 in the undergrad lab, EMA 302.
She also has tutoring hours Tues 1-2 in EMA 302, but those might be more crowded.
Hannah will lead discussion section A2.
The Teaching Fellows 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 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.
Textbooks
Our primary textbook will be 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
not cover the whole book.
Near the beginning of the term, we will dig in a little deeper to logic, and cover
material from the first few chapters from the following textbook:
How To Prove It: A Structured Approach, by Daniel Velleman, 2006. This text is
recommended, not required, but it is inexpensive as textbooks go.
Available on Amazon and at the campus bookstore.
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 131 students have found helpful in years past,
for example Discrete Mathematics and Its Applications, by Kenneth H. Rosen.
Communications:
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:
https://piazza.com/bu/fall2014/cs131/home.
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:
- Problem sets: 30%
- Midterms: 35%
- Final exam: 30%
- Attendance and participation: 5%
Last day to drop without a W: Oct 6. With a W: Nov 7.
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, Oct 2 and
Tuesday Nov 11 (updated, so as not to conflict with CS 210 midterm, on 10/13/14).
The cumulative final will be held during the normal
two-hour final exam slot, Thurs, Dec 18 from 3-5PM. Please make your
end-of-semester travel plans accordingly!
Homework Assignments, Submission, and Late Policy:
Assignments will typically be due Mondays 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 or
holiday, tentatively Sep 11 (Thurs), Sep 22, Sep 29, Oct 14, Oct 20, Oct 27, Nov 3,
Nov 17, Nov 24, Dec 8.
During the course, you will have three opportunities to turn
in an assignment up to 24 hours late with no penalty. You do not need to
notify anyone, we will track it.
As you likely already know, assignments requiring substantial creativity
can take more time than you expect, so plan to finish a day or two 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 your score may go up or down if we regrade a problem.
Attendance:
It is expected that you will attend lecture and the
laboratory section for this course and I will often take attendance at the beginning
of lecture. 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
| Sep 2, 4 | Introduction to Logic |
Chapter 1 from MIT notes |
| Sep 9, 11 | Quantificational Logic |
Chapters 1 and 2 from “How to prove it” |
| Sep 16, 18 | Proofs | HTPI and Ch. 2 from MIT notes |
| Sep 23, 25 | Proof Strategies | Chapter 3,
MIT notes (also in HTPI) |
| Sep 30 | Induction | Chapter 3, MIT notes |
| Oct 2 | In-class Midterm I | |
| Oct 7, 9 | More induction | Chapter 3, MIT notes |
| Oct 14 | No class -- Mon schedule | |
| Oct 16 | A taste of number theory | Chapter 4, MIT notes |
| Oct 21 | Basic Sums and Products | Chapter 9.1 from MIT notes |
| Oct 23, 28 | Asymptotic Notation | Chapter 9.7 from MIT notes |
| Oct 30, Nov 4 | Recurrences | Chapter 10 from MIT notes |
| Nov 6 | Intro to counting | Chapter 11 from MIT notes |
| Nov 11 | In-class Midterm 2 | |
| Nov 13, 20 | Counting | Chapter 11 from MIT notes |
| Nov 25 | Counting, probability | Chapter 14 from MIT notes |
| Nov 27 | No class -- Thanksgiving | |
| Dec 2, 4 | Probability, conditioning, independence | Chapter 14-16 from MIT notes |
| Dec 9 | Review | |
| Thurs Dec 18 | Final Exam, 3-5PM | |
|
|
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
BU 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 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.