SUNY Geneseo Department of Computer Science

Problem Set 14—Probability and Expected Value

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Friday, May 3

Purpose

This exercise reinforces your ability to use probabilities and expected values in reasoning about algorithms.

Background

Our textbook discusses probability in appendix C.2, and expected value in C.3. It illustrates some applications of these concepts to chained hash tables in section 11.2. We discussed this material in class on April 25 and April 30.

Exercise

Solve each of the following problems.

Problem 1

Exercise C.2-1 in our textbook.

Problem 2

Exercise C.3-1 in our textbook.

Problem 3

Exercise C.3-2 in our textbook.

Problem 4

A hash table containing m table slots has n keys in it. Assuming simple uniform hashing, what is the expected number of slots with empty chains?

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Meetings should take about 15 minutes. Sign up either on the paper schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure to have your grading appointment before the end of the day on the due date above.