CAS CS 131 - Fall 2018

CAS CS 131 - Fall 2018 - 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 practice: 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.

Our Piazza page (includes all handouts)

Lecture Topics Page

Prerequisites: Basic (high school level) calculus and algebra.

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 12:30 - 1:30PM (by prior appointment) and Thurs 10-12 AM (open), in MCS 295B.
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.

Prof. Charalampos (Babis) Tsourakakis
Homepage: https://tsourakakis.com
Email:    tsourolampis @ gmail . com [preferred]
Office Hours: Thurs 5-6PM and Fri 10-12AM in MCS 292.

Teaching Fellows: Konstantinos Ameranis, Anatoliy (Tolik) Zinovyev

Email:    {ameranis, tolik} @ bu . edu

Office Hours, held in EMA 302 (or 303):

Konstantinos: Thurs 5 - 6PM, Friday 1 - 3PM.
Tolik: Wed 5:30 - 6:30PM, Friday 11AM-1PM.

The class will be co-taught 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. One of the two TFs will lead each of 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. The purpose of the office hours of the Instructors and the 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 help to students on the homework. Office hours earlier in the week are invariably much less crowded.

Lectures

Lecture A1: Tues/Thurs 2 - 3:15 PM, CGS 129.
Lecture B1: Tues/Thurs 3:30 - 5 PM, CGS 129.

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 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 9:05 - 9:55AM, MCS B33
Lab A3: Wed 10:10 - 11AM, KCB 104
Lab A4: Wed 11:15 - 12:05PM, CAS B06B
Lab A5: Wed 12:20 - 1:10PM, MCS B23
Lab B2: Wed 1:25 - 2:15PM, CAS 235
Lab B3: Wed 2:30 - 3:20PM, WED 406
Lab B4: Wed 3:35 - 4:25PM MCS B23
Lab B5: Wed 4:40 - 5:30PM CAS 228

Labs will be an invaluable part of the course typically involving interactive problem-solving sessions and further guidance on homework questions. It is fine to sign up for A lecture and a B lab, or vice versa, as space permits. Attendance is mandatory and will be taken.

Labs will not be held on Wed, September 5. The first section of lab will be held on Wed, September 12th.

Textbook

Discrete Mathematics and Its Applications, Kenneth H. Rosen, 8th Edition. ISBN 978-1-259-67651-2
If you have access to another recent edition, that should be fine, although page numbers and exercises will vary. It will be your responsibility to adjust accordingly.

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 TFs, 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/fall2018/cs131/home. If you recently registered for the class, 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 9. With a W: November 9. 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, October 4 and Thursday, November 8. The cumulative final will be held during the normal two-hour final exam slot. All exams will be in our regular lecture room, CGS 129. The final exam matrix is *now finalized*, the same as the tentative times listed previously: Tuesday, Dec 18, 3-5PM for students in the 2PM lecture and Wednesday, Dec 19, 3-5PM for students in the 3:30PM lecture. Please make your end-of-semester travel plans accordingly!

Homework Assignments, Submission, and Late Policy: Assignments will typically be due Fridays at 5PM. You must submit electronically via Gradescope. If you registered for the class after September 4, you will need to create a Gradescope account and use entry code 9BB7ER to add CS131. Plan on assignments being due every week, except right after a midterm, tentatively Sep 14, Sep 21, Sep 28, Oct 12, Oct 19, Oct 26, Nov 2, Nov 16, Nov 30, Dec 7.

Solutions will be posted at 5PM and homework assignments will NOT be accepted late. Therefore, do NOT cut it close!! You may freely resubmit up to the deadline, so we recommend you submit a preliminary version by 4PM. 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 online 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. 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 (UPDATED LAST ON 11/27, probably the final update)

Lecture	Topic	Readings	Homework Due Dates
9/4	Introduction to Proofs and Deductive Reasoning	Chapter 1.7
9/6	Propositional Logic	Chapter 1.1-1.2
9/11	Laws, logic circuits and satisfiability	Chapter 1.2 - 1.33
9/13	Predicates and quantifiers	Chapter 1.4	HW 1 due 9/14
9/18	Nested quantifiers	Chapter 1.5 (& skim 1.6)
9/20	Proof methods and techniques	Chapter 1.7 - 1.8	HW 2 due 9/21
9/25	More examples of proof techniques, sets	Chapter 2.1 (review)
9/27	Logic in Robotics. Sequences, Sets, Sums	Chapter 2.2 (review) and 2.4	HW 3 due 9/28
9/27	Intro to Induction	Chapter 5.1
10/4	Midterm 1, covers lectures through 9/28
10/9	No class (Columbus day turns Tuesday into a Monday)
10/11	Induction proofs	Chapter 5.1	HW 4 due 10/12
10/16	Strong induction	Chapter 5.2
10/18	Recurrences, recursive sets, structural induction	Chapter 5.3	HW 5 due 10/19
10/23	Recursive algorithms + division and GCD	Chapter 5.4, 4.3
10/25	Divisibility, numerical representations	Chapter 4.1, 4.2	HW 6 due 10/26
10/30	Extended GCD, solving congruences	Chapter 4.3 - 4.5
11/1	Primality, applications to crypto	Chapter 4.3 - 4.5	HW 7 due 11/2
11/6	Big-O notation, algorithm runtime analysis	Chapter 3.2 - 3.3
11/8	Midterm 2, covers lectures through 11/1
11/13	Limits and big-O, analyzing recursive algorithms.	Chapter 3.3, 5.4
11/15	Divide and conquer algorithms, master theorem.	Chapter 8.3	HW 8 due 11/16
11/20	Counting	Chapter 6.1, 6.2
11/22	No Class (Happy Thanksgiving!)
11/27	Counting	Chapter 6.2 (and 2.3.5), 6.3
11/29	Counting	Chapter 6.4	HW 9 due 11/30
12/4	Probability	Chapter 7.1-7.2
12/6	Probability	Chapter 7.2	HW 10 due 12/7
12/11	Probability	Chapter 7.3

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:
1. Before discussing each homework problem with anyone else, you must give it an honest half-hour of serious thought.
2. 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.
3. You may get help from TFs for the class for specific problems in lab and at office hours.
4. 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.