CSCI 570 - HW 10
Graded Problems
1. Given a graph G = (V, E). We want to color each node with one of three colors so that no
two adjacent nodes have the same color. We say that an edge (u, v) is satisfied if the colors
assigned to u and v are different. Consider the algorithm that picks a color for each vertex
uniformly and independently at random. Compute the expected number of satisfied edges.
2. An IPod holds a collection of 1000 songs. The collection consists of 100 artists each of whom
sang 10 songs. The 1000 songs played in a random order. What is the expected number of
times that that three songs sung by the same artist are played in a row?
3. Five hundred seventy airline passengers are boarding a plane with 570 seats. Each
passenger has a ticket with an assigned seat. Unfortunately, the first person lost his boarding
pass, so he picks a seat at random. After that, each person entering the plane either sits in their
assigned seat, if it is available, or, if not, chooses an unoccupied seat randomly. What is the
probability that the last person to board the plane will sit in the originally assigned seat?
4. Consider a random binary array of an infinite size in which exactly half elements are 0s and
half are 1s. Your task is to find an index of any 1. Design a randomized algorithm to find such an
index. What is the expected number of trials before success?
Practice Problems
1. You are in a Cartesian coordinate system. Every step you will go up, down, left, or right, with
the equal probabilities (1/4), and the length of every step is 1. What is the expected distance R
from the origin to your location, after n steps? Hint: compute R
2
.
