Computer Science 789 Randomized Algorithms

Fall 2004

Assignments

This page will be updated frequently. Most recent update: December 13, 2004.

Background. I will assume basic knowledge of both algorithms and probability. Appendix B and Appendix C in your textbook (pp 433 - 446) should be helpful.
Tuesday August 31, 2004.
Today we will briefly discuss the course in overview, and then the material in subsections 2.2.1 and 2.2.2 of your textbook, pages 31-35.
If time permits, we will then jump to Part Two of your textbook, Applications, which starts on page 197. The reason for this is that we will emphasize applications of randomized algorithms in the course.
Thursday September 2, 2004.
We'll start Section Two today. We will begin with an analysis of randomized sorting, basically a randomized version of quicksort.
Tuesday September 7, 2004.
Assignment 1 is due in class today. The exercises must be hand written, not typed or printed from a computer file. Answers.
I now have the proof that was missing last Thursday. Of course, it's ``obvious," as I though it was. Explaining why it's obvious may not be so easy. The difficultly lies in the ``backwards analysis" nature of the proof, which is so typical in the subject of randomized algorithms.
Today I will lecture on treaps. A treap has the properties of both a search structure and a priority queue, namely it has the operators find, insert, delete (any item) and delete min (i.e., delete the item of greatest priority).
For example, imagine a data set where each item has a key value (to be used for searching) and a priority. Assume that the keys and priorities are unique. It is a theorem that there is exactly one binary search tree for these data which has the heap property, namely that an item always has lower priority than its parent. (You actually learned this taking CSC 269, although you probably were unaware that you were learning it. But I know you learned it, because it always appeared on an exam, despite the fact that the word "treap" was never used.)
A random treap is a search structure where the keys are what we really care about, but the priorities are chosen at random. In a random treap, we do not worry about the operator delete min, since priority is random and hence irrelevant. But the randomness of the priorities and the heap property on those priorities guarantees that the expected time of any operation is O(log n). That is, a random treap is, is a randomized sense, a balanced binary search tree.
Here are 100 random numbers generated by the built-in function "random." I do not know how they're generated, but it appears that they are uniformly distributed real numbers in the range from 0 to 1.
Input file 1. Input file 2. Output file, using input file 1 and a binary search tree. Output file, using input file 2 and a binary search tree. Output file, using input file 1 and a random treap. Output file, using input file 2 and a random treap. In the latter two cases, the random number generator assigned a priority for each item as it was inserted.
I just logged into student and the function "random" works there, too. From outside our local system, you would call it student.egr.unlv.edu
Thursday September 9, 2004.
The main points of today's lecture will be backwards analysis and duality. Duality is a concept that is really independent of randomization, but it is necessary to understand it for many problems in computational geometry.
We will discuss algorithms for finding the convex hull of a finite set of points, as well as the the dual problem, namely finding the polytope of points which satisfy a finite set of linear constraints. (For example, in the plane, the set of point satisfying the linear constraints
  • x - 1 <= 0
  • x + y - 2 <= 0
  • - x - y - 1 <= 0
  • y - 1 <= 0
is a triangle with vertices at (1,1), (1,-2), and (-2,1).)

There is no randomized algorithm for this problem whose expected time complexity is asymptotically less than the best known deterministic algorithm, but randomization helps in other ways, as explained in the textbook.

We will also discuss an application which reduces, not to the convex hull problem, but to a variant of the convex hull problem that is so close that the same algorithms will work. This is not an untypical situation in practical applications, and shows you why "black box" packages for working standard problems have their limitations.

Tuesday September 14, 2004.
I figured out the confusing statement at the top of page 239. (In fact, I figured it out Tuesday evening right after class.) I will explain it tonight.
Today I will attempt to present the algorithm given in Section 9.4 of your textbook, pages 241-245. Please read it before class, so that you can help me through it. The algorithm has expected time complexity of O(n log n) for finding the intersection of n halfspaces in 3-space.
Thursday September 16, 2004.
Today we will backtrack somewhat, and give some clues for Assignment 2. Everyone, please bring at LEAST two different color writing utensils to class today, for taking notes.
Print out this game tree for class.
I am still waiting for someone to get me a copy of "Las Vegas is better than determinism" by Mehlhorn and Schmidt.
What is commonly known as "Yao's Theorem" (but was known by lots of people such as von Neumann, and even me) before Yao ever published it, is very important in analysis of randomized algorithms. We will use it today.
Warning: just as the tunnel was closed at times during President Bush's visit on Tuesday, the tunnel will probably be closed at times during Senator Kerry's visit today. (He is speaking to the same group that Bush spoke to on Tuesday.) I would recommend staying far away from the airport and the road from the airport to the convention center. (In the 2000 election, these closures sometimes happened without warning, causing it to take me hours to get home one evening after class. At least, now, we are warned.)
Friday September 17, 2004.
Thanks to Miss Basu, for getting me a copy of the 1982 version of the paper by Mehlhorn and Schmidt. I couldn't find a reference to a later version, so it might not exist.
We did use Yao's theorem last night, although I didn't mention it by name.
We did three different analyses of the game in class last night. In all models, we assume that Black knows Red's algorithm (i.e., looks at the code) before making deciding its moves. Since corresponds to the "worst case" philosophy, which was justified to me by Nancy Lynch as follows: If you know you have a certain performance in the worst case, then you know you have at least that good performance in all cases.
  1. Black knows everything, including Red's random choices in advance. This corresponds to the deterministic model, as was proven some time ago, since randomization is worthless to Red if Black knows what the random choices will be. In this case, the value of the game (Red's cost) is 1.
  2. Both sides are oblivious, which is the classic von Neumann model going back to before I was born. In this case, the value of the game is 2/3. Although this model is not the emphasis in the course, it is absolutely necessary to understand it.
  3. Black is oblivious but Red is not, i.e., Red sees Black's choices, but Black does not see Red's choices. In this case, the value of our game is 1/2. Here is some further discussion of that model, which is, in this course, far more important than either of the others.
Tuesday September 21, 2004.
Assignment 2 is due in class today.
Thursday September 23, 2004.
I will make a serious effort to finish grading the homework by class tonight. It won't be easy.
To a very great extent, tonight's lecture will depend on what I discover while reading the homework. In particular, discussion with several students has convinced me that the basic concept that drives the standard "worst case" definition of the performance of randomized algorithms is not fully understood by all. Since this is absolutely central to the course, it is mandatory to understand it.
A couple of students have expressed interest in doing programming projects. I really never considered such a thing in a 700 level course, but I have not rejected the idea. One thing I do not want to do is give the same programming project to everybody ... they would be individually negotiated. One student has already completed such a project, although it was a "small" one. I am open to ideas for projects, of course, but what I am really interested in is someone doing a project that would aide serious research. Such a project could be very hard.
Tuesday September 28, 2004.
Due to medical emergency, there will be no office hour today.
Thursday September 30, 2004.
Let me remind everybody that, when you send me email, you must write CSC789 as the first thing in the subject field. (You can write other things after that in the subject field if you wish.) The reason is that the level of spam is so bad that I am forced to erase most messages without reading them.
I would like a list of everyone's email address.
Due to continuing medical situation, I will cancel my 7pm office hour tonight.
Tonight will be "catch-up" night. Only one student understood the basic definition of "worst case expected performance" of a randomized algorithm well enough to do the homework problem correctly. This is unacceptable, so we'll have to repeat the homework, i.e., do a different problem on the next homework where your answer will again reveal whether you understand that definition.
Tuesday October 5, 2004.
Today we will discuss hashing using randomization.
Thursday October 7, 2004.
Assignment 3 is due in class today.
Today we will continue the discussion of hashing using randomization.
We will also prove that a random binary search tree (and hence a treap) has expected height O(log n).
Tuesday October 12, 2004.
Today we will discuss the algorithm "Lazy Select" given in your textbook.
Think about the following question in preparation for today's lecture on lazy select. Suppose that there are 10000 voters in a particular city. Of those, k of them favor a certain proposition, while N-k oppose it. A random sample of 1000 voters is chosen. Of those, m favor the proposition, while 1000-m oppose it. Of course, the expected value of m is k/10, but because the sample is picked at random, m could be more or less than that value. What is the probability that m < k/10 - 100? What is the probability tht m > k/10 + 100? In both cases, very small, wouldn't you think?
Thursday October 14, 2004.
Today I will give an application of randomized algorithms to an online problem, namely paging.
Tuesday October 19, 2004.
Assignment 4 is due in class today.
Thursday October 21, 2004.
Tuesday October 26, 2004.
Thursday October 28, 2004.
Examination today: (These are newer versions from October 28.) postscript version. pdf version. Hint for last problem
Tuesday November 2, 2004.
Thursday November 4, 2004.
Hand back and discuss graded examination.
Tuesday November 9, 2004.
Today we will discuss a Monte Carlo algorithm for the min-cut problem.
Thursday November 11, 2004. Veterans' Day holiday. Originating as a holiday honoring the dead of the Great War (now called the First World War), today we honor all those who have served in the Armed Forces.
Tuesday November 16, 2004.
Today we will make another attempt to understand FastCut on page 293 of your textbook.
Thursday November 18, 2004.
Tuesday November 23, 2004.
Assignment 5 is due in class today.
Thursday November 25, 2004. Thanksgiving Day holiday.
Under John Hanson who was actually the first President of the United States, Congress, in 1782, urged the states to celebrate Thanksgiving Day on the fourth Thursday of each November.
(George Washington was the first President under our current constitution, and began his term in 1789. But Washington acknowledged that Hanson was the first President of the United States, and voted for him when he was elected unanimously by Congress in 1781.)
Tuesday November 30, 2004.
Thursday December 2, 2004.
Tuesday December 7, 2004.
Thursday December 9, 2004.
Final Examination. Our final examination is scheduled for 6:00 PM on Thursday, December 16. uncompleted final in pdf format. Here it is in postscript format.
Here are easy questions, html version to practice on. Plain text version
Here is the solution to that proof in postscript and in pdf

Back to Course Page