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).

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

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.

- [LLM]:
**Mathematics for Computer Science**by Lehman, Leighton, and Meyer. We will cover much of the material in the Probability part of the book. You can download a free pdf copy here. - [MU]:
**Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis**by Mitzenmacher and Upfal (2nd edition). This is a great resource for the randomized algorithms part of this course. - [BT]:
**Introduction to Probability**by Bertsekas and Tsitsiklis (2nd edition). This is a great resource for the continuous probability part of this course.

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.

The course grade will break down as follows:

- Homeworks: 35% (the lowest 2 homework scores will be dropped)
- Midterm exam: 25%
- Final exam: 35% (cumulative)
- Attendance and participation in lecture, lab, and Piazza: 5%

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.

- Basic probability: probability spaces, set theory and probability.
- Conditional probability.
- Independence.
- Discrete and continuous random variables and distributions.
- Expectation and variance.
- Concentration inequalities: Markov, Chebyshev, Chernoff.
- Randomized algorithms and data structures.

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.

The collaboration policy for this class is as follows.

- You are encouraged to collaborate with one another in studying the 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 one-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 write-ups 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 the course staff (instructor, TF, undergraduate assistants) 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.

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.

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.