CSCI2244-Randomness and Computation

Spring, 2018





General Course Information Course Content Required Background Software
Textbooks Required Work Grading Detailed Course Schedule

General Course Information


Instructor


Howard Straubing
Computer Science Department
St. Mary's South 251
tel.: 617-552-3977
e-mail: straubin@cs.bc.edu
Office hours: Monday and Wednesday, 2-4

Teaching Assistants


Linda Chen
Ned Cramer
chenavx@bc.edu
cramered@bc.edu
OH: Tuesday 10PM-midight
OH: Thursday 2:45-4:15

TA office hours are in Fulton 160

Meeting Times


The course meets Tuesdays and Thursdays, 12:00-1:15, in Fulton 250. There is no class on March 6, 8, and 29.


Course Content

Methods from probability and statistics are used throughout Computer Science, in the design and analysis of algorithms, artificial intelligence, machine learning, data mining, natural language processing, cryptography,.... This is a course on the mathematical fundamentals of probability and their applications in Computer Science.


Required Background

The official prerequisites for CSCI2244 are Computer Science I (CS101) and calculus. In particular, it is assumed that students taking CSCI2244 are comfortable with fundamental programming techniques, as well as with basic concepts of differential and integral calculus.

I intend to make all the programming assignments in Python, supplemented with the matplotlib library which enables, among other things, the drawing of nice plots.  If you have not programmed in Python before, you will find it reasonably easy to pick up, particularly since we don't use any of the really fancy stuff (just basics of functions, branching and looping, manipulation of one-dimensional lists).

Since we use the basic language of sets and functions throughout the course, it is also helpful to have taken CSCI2243 before CSCI2244.  However, it is understood that some students are taking this sequence in the reverse order, so I will provide supplemental materials to help these students bridge whatever gaps are present in their preparation.

Software

All of our programming demos and assignments will be in Python 2.7, supplemented by the matplotlib library. Instructions for installing the software can be found here.  I strongly recommend that you do the installation right away, and inform me of any problems that arise.


Textbooks


The official textbook for this course is Randomness and Computation, by Prof. Sergio Alvarez.  This book, which is available for free in electronic form, was prepared specifically for this course, and is posted on the Canvas site.  In the detailed course syllabus below, you will find references to the relevant sections of this book.

You might also want to have a look at  Introduction to Probability, 2nd Revised Edition, by Charles M. Grinstead and J. Laurie Snell.  This book,  along with a lot of supplemental material, is available for free on line. The associated code samples are in different programming languages from the one we are using, but it is the text itself that I am most interested in. If you would like to have a paper-and-ink copy of this book, you can buy one from the online bookstore of the American Mathematical Society for $60, a very reasonable price compared to most textbooks.


The core mathematical material in this course is quite standard, and covered in a variety of sources, including printed textbooks, online lecture notes from courses at other universities, even lectures on YouTube.  Feel free to explore, and please let me know if you run across anything that you find particularly useful, and that ought to be shared with the class. You should be aware that different books may use slightly different terminology, and that there is considerable variability in the order in which topics are presented.

Required Work

  There will be approximately 10 problem assignments during the semester.  Typically, every assignment  will involve some coding, and some written work. The assignments are not meant to be completed in a single late-night session, and I strongly advise you to start every assignment within a day or two of receiving it, so that you will be able to find out where the troublesome parts are and ask meaningful questions in class or in office hours.   This does not mean that assignments will necessarily require many hours to complete, but rather that questions are likely to arise during the work, and you may need some answers before you can proceed further.

Assignments will be posted on this web site.  I will try to post solutions to assignments in a timely fashion.  For this reason (and others) late homework assignments will not be accepted. Assignments will be submitted through the Canvas site for the class.  There is a required format for assignment submissions, described in detail in the first row of the course grid below.

There will be a number (probably four) of brief quizzes, two in-class midterm exams, at dates to be announced. There will be a common final exam for all three sections of CSCI2244 on Friday, May 11, at 4PM.

While I do not take regular attendance, students are nonetheless expected to attend class, notify me of any absence, and inform themselves about any material or announcements they miss in the event of an absence.


Eyes Front!

My colleague Bob Muller calls this policy the 'laptop-free classroom'. (For 'laptop', read 'laptop and smartphone'.)

A successful class requires your attention, engagement, and participation.  You need to be prepared to ask and answer questions during the lectures, and to attend to the questions and answers of your fellow students and of the instructor.  That screen open to your e-mail or Facebook page distracts not only you, but the students sitting behind you. For this reason, open laptops are not permitted in the classroom, unless they are part of some planned activity for which your computer is required.

You say you're taking notes on that laptop instead of shopping on Amazon? You should be aware that (a) it is very difficult to take notes for this class on a computer, given the large number of mathematical symbols, formulas and diagrams that we use; and (b) taking notes by hand is better for you.  It is acceptable to take notes on a tablet computer with a stylus.

Exceptions to this rule will be made for the rare instances of in-class activities that require students to use their computers. There will be one such activity on the first day of class.

Academic Integrity

While I encourage you to discuss problem assignments both among yourselves and with me, when it is time  to finally sit down and prepare the completed assignment, you are required to work alone.  Thus it is acceptable to learn from another student the general idea for writing program code to perform a particular task, but unacceptable to  take an extended piece of code written by another person and incorporate it into your submitted assignment as your own work.  Similarly, you may get ideas from additional reading that you do both in books and on the Web, but you may not incorporate it verbatim into what you submit and claim that it is your own work. If you have any uncertainty about the application of this policy, please check with me.

It should go without saying that during quizzes and exams there is to be no communication between students, and no use of outside materials except those explicitly authorized in advance.

Failure to comply with these guidelines will be considered a violation of the University policies on academic integrity. Please make sure that you are familiar with these policies, which are posted at http://www.bc.edu/offices/stserv/academic/integrity.html.

Services for Students with Disabilities

If you are a student with a documented disability seeking reasonable accommodations in this course, please contact Kathy Duggan, (617) 552-8093, dugganka@bc.edu, at the Connors Family Learning Center regarding learning disabilities and ADHD, or Rory Stein, (617) 552-3470, steinr@bc.edu, in the Disability Services Office regarding all other types of disabilities, including temporary disabilities. Advance notice and appropriate documentation are required for accommodations.

Grading

To be eligible for  a passing grade in this course, you must complete at least 60% of the assignments in a satisfactory manner. Once this criterion is met, your grade will be computed from the various course components, with the problem assignments, quizzes and midterms, and final exam each weighted approximately equally. I do not have a fixed scale, made in advance, for translating raw scores into letter grades, but instead consider the difficulty of the work and class performance as a whole.  In a large required course such as this one, the median grade is typically B.


Detailed Course Schedule

Take this with a grain of salt.  The list of topics is largely accurate, but now and again I will decide to eliminate or add a topic, or change the order in which I present them.  The dates are almost surely inaccurate. Expect  this section of the website to grow and change as the semester progresses. The numbers next to each topic are the corresponding sections of the course textbook.

Date
Topic
Handouts and Lecture Notes
Assignments           
Week 1
January 16-18
A coin-tossing experiment.

Simulations in Python and matplotlib.
The in-class exercise for the first day

Installing and using the software

Coin-tossing experiments (heavily commented Python code to demonstrate the plotting and numerical tools)

How to prepare the homework (a mockup homework assignment).

The 'hot hands' paper by Gilovich, Vallone and Tversky

Non-required reading:  Is there such a thing as an unfair coin?

No, say these Statistics professors

Yes, claims this guy (along with disturbing photographic instructions for how to make such a coin).

Maybe they're all unfair.
Assignment 1, due January 24.
Week 2
January 23-25
Discrete probability spaces, Independent events (2.1,2.2)



Assignment 2, due January 31.
Week 3
January 30-February 2
Counting (2.3)
Graphical solution to the birthday problem.
Assignment 3, due February 8.

The birth date data for 2000-2003.
Week 4
February 6-February 8
Discrete random variables. (Chapter 3)
Assignment 4, due February 24.
Week 5
February 13-February 15
More discrete random variables. Geometric distribution. Poisson distribution. Python code using cumulative distribution function to simulate roll of two dice.
Week 6
February 20-February 22
 Expected value.



Week 7
February 28-March 2
First midterm.

Conditional probability and Bayes's Theorem.
The midterm with solutions.


Spring break



Week 8
March 14-March 16
Continuous sample spaces and continuous random variables.
Simulation of Buffon Needle problem
Assignment 5. Part 1 is due March 20, Part 2 March 27.

(The supporting files are on the Canvas site.)
Week 9
Variance, Markov's and Chebyshev's inequalities
Simulation of exponential- and Poisson-distributed random variables
Assignment 6, due Monday April 2.
Week 10
(just one class:)
Normal distribution, Law of Large Numbers and Central Limit  Theorem Central Limit Theorem demo, showing convergence of binomial and sums of exponential random variables to standard normal density.

Polling demo, graphical display of confidence intervals in repeated simulations of poll.
Assignment 7, due Tuesday, April 10
Week 11
More on Central Limit Theorem (Chapter 5)

Week 12
Second midterm


heights.py demonstrates normal distribution of real-world data
probplots.py demonstrates probability plots

The second midterm, with solutions.
Assignment 8, due April 26


Week 13
Markov Chains (Chapter 9)

Simulating a Markov chain (with one line of code!)


Assignment 9, due May 3
Week 14
Markov Chains


Week 15
Review