The Probabilistic Method

Course Goals

By the end of this course, you will:
  • learn the basics of discrete and finite probability, including random variables, expectation and variance, and the main tail bound inequalities (Markov, Chebyshev, Chernoff)
  • learn and understand the Probabilistic Method.
  • apply the Probabilistic Method to prove several results in combinatorics and theoretical computer science.
  • be able to identify computational problems that are intractable and argue why they might be hard to solve efficiently.
  • understand how randomization is used to design and implement efficient algorithms for a variety of problems.

Student Responsibilities

  • Attend class and lab sessions.
    The primary introduction to course material is through class instruction. Attending class is essential for understanding the subject. Lab sessions provide additional time to work on solutions. Lab sessions will also be used for exams. Lab attendance is mandatory.
  • Participate actively in the learning process.
    The best way to learn this material is through constant effort. During class we will often derive solutions collaboratively. Labs provide additional time to experiment with solutions and analysis. There is a very strong correlation between students that ask questions and students that do well in this class.
  • Start the lab assignments early.
    CS49/Math59 is not a coding course, and it is extremely difficult to bang out solutions at the last minute. I understand that it is not always possible to put serious time into an assignment early. However, even 30-60 minutes will be helpful, to ensure that you understand what the problems ask of you and you start thinking about how to solve them early.
  • Seek help early.
    It is essential in this class that you not fall behind. If you find yourself falling behind, or if you're having trouble grasping a concept, come to office hours. Ask (and answer!) questions on Piazza. Set up an appointment to talk with me. Or just stop by my office when my door is open.

Academic Integrity

Note: in the following paragraphs, "code" refers to all homework solutions, including written programs but also proofs, analysis, written reports, etc.

Academic honesty is required in all your work. Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Please contact me if you have any questions about what is permissible in this course.