CAS CS 237 - Fall 2007
Introduction to Probability in Computing
Syllabus
Course Description
Official Description:
Coreq: CAS MA 123 or equivalent experience, or CAS CS 113 and CS 235, or CAS MA 294, or consent of instructor.
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.
Elaboration:
We focus on applications and uses of probability theory in computation.
This includes using probability to construct and analyze
efficient algorithms and systems,
as well as to
prove the correctness or approximate correctness of algorithms.
We also expect this class to provide you with
useful techniques and skills (not the least of which is mathematical maturity).
The tentative schedule is as follows, at approximately one topic per week:
- Elementary set theory and basic counting techniques
- Sample spaces and events/basic axiomatic probability
- Conditional probability and independence
- Matrix multiplication and min-cut algorithms
- Random variables
- The coupon collector problem
- Bernoulli trials
- Binomial and normal distributions
- Poisson and geometric distribution
- Discrete and continuous random variables
- Expectation
- Markov and Chebyshev inequalities
- Computing the median
- Chernoff bounds
- Packet routing
- The birthday paradox
- Hashing and bloom filters
- The probabilistic method
- Central Limit theorem
Prerequisites and Related Courses
The class assumes working knowledge of CS 112 and either MA 293 and 294 or
CS 113 and 235.
If you encounter some math you
don't know, try looking in your favorite discrete math book.
If you don't find it there, ask the TF or the instructor.
Staff
The Professor is Steve Homer.
The teaching fellow is Sarah Zatko. Contact information follows.
-
Steve Homer,
homer@cs.bu.edu,
617-353-8927, MCS (111 Cummington St) 281. Office hours:
Tuesday 11:00-12:30, Thursday 2:00 - 3:30.
-
Sarah Zatko,
sarahzl@cs.bu.edu, 617-358-1121,
PSY (64 Cummington St) 225. Office Hours: Tuesday and Wednesday 2:30-4:00.
We encourage you to come to our office hours. If you need to talk to us but
can't make the office hours, please send one of us email. We check it a few
times on a weekday and at least once on a weekend.
Texts
Probability and Computing: Randomized Algorithms and Probabilistic Analysis,
by Michael Mitzenmacher and Eli Upfal, Cambridge University Press (January 31, 2005).
Meetings and Other Communication
Lectures are Tuesdays and Thursdays 12:30-2:00 in MCS B23 (111 Cummington).
Lecture attendance is required.
Students are responsible for all material covered in lecture.
Some lecture material may not appear in the text.
You should have also selected the lab when you registered (if not, add it
to your schedule!). Labs, which meet Wednesdays 11-12 in MCS B31 and are
headed by the TF,
are a required part of the course.
If you are unable to attend lab, you must send email
to Sarah beforehand.
The class has a home page:
http://www.cs.bu.edu/~homer/237/. Important news about the class will be posted there.
On occasion, we will send out email to the class list, so please log in
to csa and type csmail -a cs237.
"I didn't get your email" won't
ordinarily be an acceptable excuse.
Assignments and Tests
There will be about 8 homeworks (mainly problem-solving, no programming) (50%),
a midterm (20%) and a final (30%).
The midterm will be in class some time
in October (probably in the second half of October).
The final exam will be Tuesday, December 12 at 9:00 in our regular classroom.
Late Homeworks Policy
Late assignments will be penalized at a rate of 20% per day.
If you are going to be late, let me know. I will be generous, up to a point.
Important Dates
Last day to drop without a W grade: Tuesday, October 9
Academic Honesty
Plagiarism is any attempt to represent the work of another as one's own. Read
the BU CAS Academic Conduct Code and follow it. Do not misrepresent your work
or aid others in doing so. If you are sharing your homework write-up with
your classmate, you are, in my eyes, as culpable as your classmate.
Collaboration policy for this class is as follows.
- You are encouraged to
collaborate with one another in studying the textbook and lecture material.
- You are permitted limited collaboration on the homeworks, with
the following conditions: (1) before discussing each homework problem with anyone
else, you give it an honest half-hour of serious thought; (2)
you write-up solutions entirely on your own, without looking at others'
write-ups; (3) you acknowledge the people you worked with; (4) you do
not work with people outside this class (but come and talk to us if you have a tutor), do not seek on-line solutions,
etc.
- You are not permitted to collaborate on exams.
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 score will reflect
it.
If you violate this policy (e.g., by looking at another person's write-up
or finding a solution on-line), you can avoid being treated as a cheater
by acknowledging your violation in your write-up: you probably won't
get much credit for the problem,
but at least you won't have lied to me and violated BU policy on academic
honesty. Remember,
citing your sources properly is often the easiest way out of trouble.
Violations of academic honesty result in an automatic failing grade and are
reported to the Academic Conduct Committee (ACC). The ACC often
suspends or expels students deemed guilty of plagiarism or other forms of
cheating. We have seen it happen.
If you are uncertain as to whether or not a particular kind of interaction with
someone else constitutes illegal collaboration or academic dishonesty,
please ask us before taking any
action that might violate the rules.