BU CLA CS 530: Analysis of Algorithms

Spring 1995

Problem Set 6 (due Thursday 95.03.02)


This is meant to be an easy assignment: The first two exercises are about graph algorithms, requiring a review of a few notions about "disjoint-set data structures", "heaps", and "sorting". The third exercise will give you more practice with probabilities.
  1. Exercise 24.2-4 in [CLR], page 510.

  2. Exercise 24.2-5 in [CLR], page 510.

  3. A certain professor gives exams that contain an infinite number of problems. In order to solve each problem, the student must have solved all of the preceding problems perfectly, since the professor stops grading an exam as soon as he finds a mistake. Each student has probability p of getting any particular problem right, independently of the other students, and independently of the problem number. The professor gives an A+ to the student who solves the most problems, provided that only one student has the maximum score. Otherwise, nobody in the class gets A+.

    Write down an expression for the probability that an A+ is given when n students take the exam. Justify briefly. (Your expression can be left in the form of a summation, as there appears no "closed form" for the probability in question.)


Assaf Kfoury
Created: 95.02.22