Data Structure and Algorithm Design II

Sections

• Probability in Computing

• Randomized Algorithms

Probability in Computer Science

Overview

• Definition: Probability quantifies the likelihood of an event or outcome occurring. It’s a measure of uncertainty of the occurrence of an event.

• Applications:

  • Algorithm Efficiency

  • Data Analysis and Predictive Modeling

  • System Reliability

Types of Probability

• Classical Probability

  Defined for situations where outcomes are equally likely. This method is deterministic in nature. This method is related to combinatorics.

• Empirical (or Experimental) Probability (FYI)

  Based on observations, experiments, or historical data rather than theoretical calculation.

• Subjective Probability (FYI)

  Derived from personal judgment, intuition, or belief, rather than any objective or empirical evidence. It’s less formal and more based on individual perspectives.

Basic Rules and Principles of Probability

• Probability of an Event

  • \(0 \leq P(A) \leq 1\) for any event \(A\).

• Sample Space and Events

  • Tossing a coin: Sample space = {Heads, Tails}.

• The Additive Rule (mutually exclusive events)

  • \(P(A \cup B) = P(A) + P(B)\) for mutually exclusive events \(A\) and \(B\).

• Complementary Events

  • \(P(A') = 1 - P(A)\), where \(A'\) is the complement of \(A\).

• Multiplicative Rule (independent events)

  • \(P(A \cap B) = P(A) \times P(B)\) for independent events \(A\) and \(B\).

• Conditional Probability (FYI)

  • \(P(A|B) = \frac{P(A \cap B)}{P(B)}\), provided \(P(B) \neq 0\).

Bayes’ Theorem (FYI)

Based on your initial belief about the probability of an event, Bayes’ theorem allows you to update that belief based on new evidence.

Where:

• \(P(A|B)\) is the posterior probability: the probability of hypothesis \(A\) given data \(B\).

• \(P(B|A)\) is the likelihood: the probability of data \(B\) given hypothesis \(A\).

• \(P(A)\) is the prior probability: the probability of hypothesis \(A\) before seeing the data.

• \(P(B)\) is the marginal likelihood: the total probability of observing data \(B\).

Combinatorics in Classic Probability

• Card games

• Dice games

• Lottery drawings

• Arranging books on a shelf

• Drawing colored balls from a bag

• …

Card Games (Poker Hands)

Question: What is the probability of getting a royal flush in poker when dealt 5 cards from a standard 52-card deck?

Solution:

• Combinatorial Approach: There are \(C^{52}_{5}\) ways to choose 5 cards from 52, and only 4 ways to get a royal flush (one for each suit).

• Probability: \(P(\text{Royal Flush}) = \frac{4}{C^{52}_{5}}\)

Dice Games (Yahtzee)

Question: What is the probability of rolling a Yahtzee (five dice showing the same number) in one roll?

Solution:

• Combinatorial Approach: There are \(6^5\) possible outcomes when rolling 5 dice, and 6 possible Yahtzees (one for each number 1-6).

• Probability: \(P(\text{Yahtzee}) = \frac{6}{6^5}\)

Lottery Drawings

Question: What is the probability of winning a lottery where you must correctly pick 6 numbers out of 49?

Solution:

• Combinatorial Approach: There are \(C^{49}_{6}\) ways to choose 6 numbers from 49.

• Probability: \(P(\text{Winning}) = \frac{1}{C^{49}_{6}}\)

Arranging Books on a Shelf

Question: If you have 10 different books and want to place 2 specific books next to each other, what’s the probability this happens at random?

Solution:

• Combinatorial Approach: Consider the 2 specific books as one item. There are 9! ways to arrange these 9 items, and 2! ways to arrange the 2 books among themselves. There are 10! ways to arrange all books without any restrictions.

• Probability: \(P(\text{2 Books Together}) = \frac{9! \times 2!}{10!}\)

Drawing Colored Balls from a Bag

Question: In a bag with 5 red, 4 blue, and 6 green balls, what’s the probability of drawing 2 red balls consecutively without replacement?

Solution:

• Combinatorial Approach: There are \(C^{5}_{2}\) ways to choose 2 red balls and \(C^{15}_{2}\) ways to choose any 2 balls from 15.

• Probability: \(P(\text{2 Red Balls}) = \frac{C^{5}_{2}}{C^{15}_{2}}\)

Randomized Algorithms

Overview

• A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

• A special paradigm that focus on techniques used in the design of algorithms

• Combined with other paradigms to produce efficient algorithms

• Not the leading paradigm in algorithm design

• Characteristics

  • nondeterministic

  • probabilistic

Core Concepts

Randomized Algorithms

• Genetic algorithms

  • Random initial population

  • Tournament selection/roulette wheel selection

  • Random mutation

  • Random crossover

  • Random replacement

• Monte Carlo algorithms

  • Approximate solutions to hard problems

  • Employs statistics of random samples to estimate metrics of interest like probability, mean, variance, integral, etc.

  • Examples

    • Approximate the value of pi

    • Approximate the value of an integral

• Las Vegas algorithms

  • Always produce correct results

  • Randomness is used to improve efficiency

  • Examples

    • Quicksort with random pivot selection

Monte Carlo: Estimation of Pi

• Problem: Estimate the value of pi

• Solution: Randomly sample points in a square and count the number of points that fall in a circle

• The ratio of the number of points in the circle to the total number of points is the ration of the area of the circle to the area of the square

• Thus, \(\pi = 4 \times ratio\)