Official Course description
Representation, analysis, techniques, and principles for manipulation of basic combinatorial 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 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.
Info
The class will be taught by Professor Tsourakakis.
Instructor: Prof. Babis Tsourakakis
Piazza: Piazza Web Page CS 131
Semester: Fall 2019
Lecture A1: Tues and Thurs 2 – 3:15 PM, CAS B12.
Lecture B1: Tues and Thurs 3:30 – 4:45 PM , CAS B12.
Teaching Fellows
There will be three teaching fellows for CS131. The TFs will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures through problem-solving, and to provide some clarifications and guidance on the homework assignments.
- Arsenii Mustafin (aam@bu.edu)
- Hassan Saadi (hsaadi13@bu.edu)
- Anatoliy (Tolik) Zinovyev (tolik@bu.edu)
Office Hours
The purpose of the office hours of the Instructor and Teaching Fellows 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 re-explain entire topics. Office hours are scheduled at times to provide the most help to students who start the homework before the last minute.
Instructor: Prof. Babis Tsourakakis
When: T 9:00-10:00, R 8:30-9:30 (by appointment, email me at babis@seas.harvard.edu) and R 9:30-10:30
Where: MCS building, office # 102
TF: Arsenii Mustafin
When (where): M 9:30-11:00 am (PSY B53F), F 9:30-11:00am (PHO 201)
TF: Tolik Zinovyev
When (where): W 17:35 – 18:35 ( EMA302 ), F 13:30 – 15:30 (PSY B33)
TF: Hassan Saadi
When: T 17:15 – 18:15, R 17:15 – 19:15
Where: EMA302
Discussion Labs
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.
Homework Assignments
Assignments and all other handouts can be found on our Piazza page, under the Resources tab.
Announcements
- First day of class is Tuesday, September 3rd. See you all there!
Prerequisites
Basic (high school level) calculus and algebra.
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 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 write-ups) 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.
Grading
The course grade will break down as follows:
- Problem sets: 25%
- Two midterms: 40% (20%+20%)
- Final exam: 30%
- Lab attendance and participation in {lab, lecture, Piazza}: 5%
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, October 10 and Thursday, November 11. The final will take place at the end of the class, and will be held during the normal two-hour final exam slot. Please make your end-of-semester travel plans accordingly!
Homework Assignments, Submission, and Late Policy: Assignments will typically be due Fridays at 5PM sharp. We will be using gradescope.
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. This is done via gradescope. 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. On occasion, some material covered in lecture and lab will not be covered by our textbook. We ask that you please 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.
Textbook
Discrete Mathematics and Its Applications, Kenneth H. Rosen, 8th Edition.
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/fall2019/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.
Slides
Schedule
Remark: Homework due date is on Fridays 5pm, i.e., the next day after Thursday lecture.
Lecture | Topic | Readings from | Homework Due Dates | |
9/3 (T) | Introduction to propositional logic | Chapter 1 | ||
9/5 (R) | Propositional logic | Chapter 1 | ||
9/10 (T) | Predicate logic | Chapter 1 | ||
9/12 (R) | Predicate logic (cont.) | Chapter 1 | HW 1 | |
9/17 (T) | Rules of inference and Proofs (cont.) | Chapters 1,2 | ||
9/19 (R) | Proofs (cont.) | Chapter 1 | HW 2 | |
9/24 (T) | Proofs (cont.) | Chapter 1 | ||
9/26 (R) | Sets | Chapter 2 | HW 3 | |
10/1 (T) | Sets (cont.), sequences | Chapter 2 | ||
10/3 (R) | Induction | Chapter 5 | HW 4 | |
10/8 (T) | Induction | Chapter 5 | ||
10/10 (R) | Midterm 1, covers lectures up to 10/3 | |||
10/15 (T) | No class (Columbus day) | |||
10/17 (R) | Problem solving session | HW 5 | ||
10/22 (T) | Recurrences, Big-O,Θ,Ω notation | Chapters 3.2. 8.3.2, 3.1 | ||
10/24 (R) | Recursive algorithms | Chapter 3,5,8 | HW 6 | |
10/29 (T) | Recursive algorithms, Integer representation | Chapter 3,5,8, 4.2.2 | ||
10/31 (R) | Number theory | Chapter 4 | HW 7 | |
11/5 (T) | Number theory | Chapter 4 | ||
11/7 (R) | Midterm 2 (covers all lectures up to 10/31) |
|||
11/12 (T) | Number theory | Chapter 4 | ||
11/14 (R) | Number theory | Chapter 4 | HW 8 | |
11/19 (T) | Counting | Chapters 6,8 | ||
11/21 (R) | Counting | Chapters 6 | HW 9 | |
11/26 (T) | Counting and intro to graphs | Chapters 6, 10 | ||
11/28 (R) | No Class (Happy Thanksgiving!) |
|||
12/3 (T) | Graphs and trees | Chapters 10,11 | ||
12/5 (R) | Graphs and trees | Chapters 10,11 | HW 10 | |
12/10 (T) | Counting and Graphs | Chapters 6, 10,11 |