Welcome to the MATH 100-COSC 49/149 Web Page

Math 100/COSC 149 and COSC 49

Topics in Probability:
Randomness and Randomized Algorithms

Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)

Abstract | Classes | Staff | Textbooks | Grading | News and current assignment | Past assignments | Exams | Honor Code


News

Classroom: Kemeny Hall 105

Abstract

What is randomness, and what is it good for? It was once thought by many that randomness is an invention of humans, needed to account for our limited ability to predict the future. Now it seems that randomness is the oldest concept in the universe, dating to the Big Bang.

For us mathematicians and computer scientists, randomness turns out to be a valuable commodity---providing in some cases the best, even the only, way to solve certain problems and perform certain computations. But it is elusive and hard to find in its pure form. Can we improve it? Can we measure it? Can we even define it? Once we have used it to help solve a problem, can we dispense with it?

In this course we will examine randomness, trying to find out how to best obtain it and best use it. Programming will not be required (but might be useful for some students in some special projects).

Prerequisites: Mathematical background of a senior mathematics major or a beginning graduate student in mathematics or theoretical computer science, including a course in probability (e.g., MATH 20 or Math 60). If in doubt, please see the instructor. Dist: QDS.

Here is a rough weekly syllabus:

1. What is randomness, and where can we find it?

2. Basic applications

3. The minimax principle for randomized algorithms

4. Tools from probability

5. The probabilistic method

6. Counting and estimation

7. Random complexity classes

8. Pseudorandomness and cryptography

9. Amplification and derandomization

Classes

Room: Kemeny Hall 105
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10:10 - 11:15.
X-hour: Thursdays (same room) 12:15 pm - 1:05 pm. Will be used only when so announced in class.

Staff

Instructor:
Peter Winkler -- Kemeny Hall 231
Office Hours: Tu 1:15 - 2:45; Th 10:15 - 11:45.

Textbook

Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms Cambridge 1995.
Available online at https://rajsain.files.wordpress.com/2013/11/randomized-algorithms-motwani-and-raghavan.pdf
Supplementary materials (including recent advances) will be supplied in class.

Grading

Your grade will be based on homework, class participation, two hour exams, and a final exam. Homework and grading might be slightly different for enrollees of MATH 100/COSC 149 and enrollees of the simultaneous undergraduate course, COSC 49. The hour exams will be given in class on Monday, Oct 2 and Monday, Oct 23; let me know immediately if you have any possible conflict. The final exam will be in the regular slot for MWF10 courses, namely, 8am on Tuesday morning, Nov 21.

Quizzes

There may be unannounced in-class quizzes, just to make sure everyone is keeping up.

Homework

Homework will be assigned at each class period, due at the beginning of the next class.

Assignments

Due Wednesday Sept 13: Read Chapter 1 of your text, and: (easy) compute the precise number of comparisons needed by Midsort to sort 255 records; (hard) compute the number of comparisons needed by Midsort to sort 2k - 1 records, as a function of k. In Midsort, you are miraculously provided at each stage with an element that has exactly half the remaining elements below it and half above. You still have to determine for each other element whether it is below or above. As a check, Midsorting 7 records takes 10 comparisons.

Due Friday Sept 15: In our ideal tennis tournament, 2n players are bracketed randomly and the outcome of each match is equally likely to be won by either player. As usual in an elimination tournament, all the players meet in pairs in Round 1, then the survivors meet in Round 2, etc., until one player is left. What is the probability that, at some point, Rafa plays Roger?

Due Monday Sept 18: Show that the min cut algorithm that contracts random pairs of vertices, instead of random edges, could (for some graphs) succeed with only exponentially small probability; that is, there are graphs on n vertices for which it works with probability less than cn, for some constant c. This is Exercise 1.2 in your text. Warning: this requires a bit more care than you might think.

Due Wednesday Sept 20: Given a coin whose probability of coming up heads is a positive number p other than 1/2, get an upper and lower bound for the minimum expected number of flips needed to make a fair binary decision. Von Neumann's trick already gives you an upper bound, namely 1/p(1-p) flips; can you do better? How could you go about getting a lower bound bigger than 2 flips?

Due Friday Sept 22: Derive a Huffman code for the Hawaiian alphabet, using the following letter frequencies: A 27%, O 13%, K 12%, H 9%, I 8%, E 7%, U 6%, L 5%, T 5%, P 4%, M 3%, W 1%. (You are encouraged to check Wikipedia or your favorite source to make sure you understand the Huffman code algorithm.) Then, compute your average code length (sum of code length times frequency).

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.