CAS CS 237 - Spring 2018 - Probability in Computing

Syllabus


Official Course Description

Introduction to basic probabilistic concepts and methods used in computer science. Develops an understanding of the crucial role played by randomness in computing, both as a powerful tool and as a challenge to confront and analyze. Emphasis on rigorous reasoning, analysis, and algorithmic thinking. (Counts as a Group B course for the CS major, and a background course for the CS minor.)

More specifically, we focus on basic probability theory and applications and uses of probability theory in computer science. This includes using probability to analyze data sets, algorithms and data structures, and well as to prove the correctness of algorithms.

Prerequisites: CS 131 and MA 123 (or other elementary calculus class). We assume good working knowledge of elementary set theory and counting, and elementary calculus (i.e., integration and differentiation).


Piazza Page (includes all handouts)

Gradescope for submitting homeworks. Sign up using the entry code 94PRNZ.

Course Calendar


Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Tuesdays 5pm - 6:30pm, Thursdays 1pm - 2:30pm, in MCS 291.

Teaching Fellow: Kai Bernardini
Email: kaidb @ bu . edu
Office Hours: Wednesdays, 6-7:30pm, in the undergraduate lab

Learning Assistants: Katie Quirk, Sam Harrison, Zirui Liu {kquirk, ironsam,liuzirui} @ bu . edu
Office Hours: Thursdays, 6-7:30pm, in the undergraduate lab


Lectures

Lecture A1: Tues/Thurs 11am - 12:15pm, PHO 206.

Discussion Labs

Lab A2: Fri 11:15am - 12:05pm, MCS B33.
Lab A3: Fri 12:20pm - 1:10pm, MCS B23.
Lab A4: Fri 1:25pm - 2:15pm, MCS B23.
Lab A5: Fri 2:30pm - 3:20pm, MCS B23.

Labs will be an invaluable part of the course typically involving interactive problem-solving sessions and further guidance on homework questions. Attendance is mandatory and will be taken.

Textbooks

There is no required textbook for this course. Lecture notes will be posted for all lectures and you are only responsible for the material in the lecture notes. The following textbooks provide a very good (but not perfect) coverage of the material and they are a very good resource.


Communications

We will use Piazza for class discussion and questions. The system is highly catered to getting you answers to your questions fast and efficiently from classmates and the course staff. Please do not email questions to the course 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 current homework). Our class page is located at: https://piazza.com/bu/spring2018/cascs237/home. 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:

Last day to drop without a W: Feb 22. With a W: Mar 30. Incompletes will not be granted for this class.

Exams: There will be a midterm exam and a final exam. The midterm exam will be held in class on Thursday, March 1st. The cumulative final will be held during the normal two-hour final exam slot.

Homework Assignments, Submission, and Late Policy: Assignments will typically be due on Fridays at 5pm. All assignments will be submitted electronically via Gradescope as a PDF. Please sign up for the class on Gradescope using the entry code 94PRNZ. Assignments will involve both analytic (math) problems and programming in Python. You can either type your homework using LaTex (we will provide a template for each homework and there are some pointers on LaTex below) or scan your work. Plan on assignments being due every week, except right after the midterm, tentatively: Jan 26; Feb 2, 9, 16, 23; Mar 16, 23, 30; Apr 6, 13, 20, 27.

We will not accept late submissions and we will not grant extensions. To offset this policy, when computing your homework grade, we will automatically drop the lowest 2 homework scores. However, we strongly recommend putting your best effort in every homework, 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. Please submit your regrade request on Gradescope within one week. 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. 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.


Topics


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.

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.


LaTeX

We strongly recommend that you prepare your homework solutions using LaTeX, and submit PDFs to Gradescope. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. Great editors exist on most platforms, such as TexShop for Mac and TeXstudio for several platforms. An alternative to setting up LaTex on your machine is to use Overleaf.

The not so short introduction to Latex is a good reference to get you started.


Python

In this course we will be using Python for some of the homework exercies. Python is available in the undergraduate lab. If you want to use it on your own computer you will need to install it. Start here to download Python (use Python 3.x and not 2.x). Your next step is to choose a development environment, this is left up to you. You can do some research on your own or use PyDev for Eclipse, an easy to install plugin. It can be found here. Configure it to use standard Python (sometimes called CPython) and not JPython or IronPython. Emacs and VI both have features for Python. Next, take a look at:

Remember, Python is similar to Java in its basic functionality - usually the only difference is syntax. If you have trouble with specific syntax there are hundreds of free, available resources - try looking it up! We highly recommend that you run through a basic tutorial and write some basic "Hello, World"-esque programs. One point to notice about Python is its type engine. It is dynamically typed, meaning you don’t need to declare the type of most variables. Another thing to notice is that while Python is not always interpreted (it can be compiled or interpreted), it follows many of the conventions of an interpreted langauges. This means that Python scripts run from top to bottom. Unlike Java you can have trouble if you call a function above where it is defined.