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, or by appointment.
The course meets Tuesdays and Thursdays, 12:00-1:15, in
Fulton 250. There is no class on March 5 and 7, or on April
18. I will be away at a conference on March 26 and 28.
Prof. Alvarez will teach the class on March 26. March 28
is up in the air, but I will provide recorded material if
there is no one to cover the class.
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, theory of
computation.... 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 (CSCI1101) 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 strongly recommended that
you take 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 3, supplemented by the
matplotlib library. Instructions for installing the software
can be found by following the links in the grid below.
I recommend that you do the installation right away, and
inform me of any problems that arise. If you have
already installed Python, but only have Python 2, you will
need to install Python 3. This won't overwrite your
installation of Python 2, so you will still be able to use
that in any other work that you need it for. But the work in
this course has to be in 3; while the differences between
the two versions are slight, they are not compatible.
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.
I will also post lecture notes. These focus on just what
we cover in class, and are less detailed than the material in
the books.
The core mathematical material in this course is
quite standard, and is also 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. It goes without saying that there is a huge
variation in quality of YouTube offerings.
Required Work
There will be approximately nine 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, and
two in-class midterm exams, at dates to be announced. (The
dates for the midterms that appear in the grid below are
estimates.) There will be a common final exam for all
three sections of CSCI2244 on Thursday, May 9, at 4PM.
This does not mean that you will be taking exactly the same
exam as the other sections, it just secures a common time.
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.
More than you ever wanted to know about
flipping coins:
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).
And maybe, say these other statistics professors, they're
all unfair.
Conditional Probability and Bayes's theorem
(Chapter 6, but note that the textbook does
conditional probability after continuous probability
spaces, so the material here about continuous
conditional probability can be skipped for now.)