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 and algorithms and 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).
We will use the following textbook. Please be advised that not all lecture material is covered in the textbook.
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 here. We will also use Piazza to post announcements and handouts.
The course grade will break down as follows:
Last day to drop without a W: Feb 26. With a W: Apr 5. 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 21st. The cumulative final will be held during the normal two-hour final exam slot.
Homework Assignments, Submission, and Late Policy: Assignments will be due on Thursdays at midnight as indicated on the course schedule. All assignments will be submitted electronically via Gradescope as a PDF. Please sign up for the class on Gradescope using the entry code MGPBZK. Assignments will involve both analytic (math) problems and programming in Python.
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 homework score. 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 discussion section for this course. When students are at a borderline between grades, we will factor in attendance and participation before making a final determination.
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.
Please read carefully the collaboration and honesty policy for this course. Please sign and submit a signed copy of the policy with your first homework.
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 exercises. Python is available in the undergraduate lab. If you want to use it on your own computer you will need to install it. We recommend that you download a Python distribution such as Anaconda. Alternatively, you can download Python here (use Python 3.x and not 2.x). Some basic tutorials include: