Steve Homer (homer@cs)
Office: 281 MCS
Phone: 353-8927
Office Hours: Tuesday and Thursday 2-3, Wednesday 10:30-11:30 (except on days when there are faculty meetings at 11)
-------------------------------------------------------------------------------------------------------------------------------------
Required Text: Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
(See http://us.cambridge.org/titles/catalogue.asp?isbn=0521474655 for a list of corrections or to report any.)
Recommended Text: Randomized Algorithms by Motwani and Raghavan Cambridge Press
The purpose of this course is to learn about modern techniques of randomized algorithms to solve problems more efficiently. We will concentrate on four or five algorithmic methods and and a few of their most important applications. The actual choices will depend on the interests of the participants.
Graduate students and some others will be expected to lecture once or twice on some of the algorithms they choose to study.
Some of the currently active topics in the field will be discussed as they relate to various aspects of programming.
Students who lecture will be expected to produce a set of lecture notes together with other notes on their topics. Those not lecturing will be expected to produce a detailed paper paper on one specific topic by the end of the semester. This paper will be on one algorithm or on a few algorithms which solve one problem. The paper will either be experimental, that is report on experiments done with an algorithm, or a survey, that is report on the difficulty of solving a problem and on the complexity and usefulness of various probabilistic algorithms which solve the problem.
There will be no final. There will be one midterm (or 2/3-term) exam. There will be periodic homework only some of which will be graded.
The final grade will be made up from the midterm exam - 25%, the lecture and the lecture write-up and/or the project paper - 40%, homework - 20% and class participation - 15%.
Read the BU CAS Academic Conduct Code (http://www.bu.edu/academics/cas/policies/academic-conduct/) and follow it. Do not misrepresent your work or aid others in doing so. and do not share your homework write-up with your classmates. 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 homework, 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 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. This 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 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.