CS 231 Module 4: Greedy Approach

Greedy Algorithm

An algorithm that builds up a solution step by step, often uses an ordering to make a decision

Greedy Algorithm Sketch

Process Data

Loop to build up solution step by step

Use information to make a decision

Make updates to information

Greedy Algorithm Checklist

Process for preprocessing data

Definition of steps needed to build a solution

Definition of info to be used for a decision

Definition of criteria for a decision

Process for making updates to information

Arbitary

A method that chooses any 1 option from a set of options, without providing details of what the method is

Random

Using randomization (e.g. throwing dice, flipping coins) to make a choice

How to break ties?

We can add a second, third, fourth criterion based on our first criterion

predicate

an expression that refers to at least one variable

Existential Statement

A statement that says something exists;

there exist a x in the set S such that P(x) is true

Universal Statement

a claim that a predicate is universally true,

for every x in set S, P(x) is true

How to use universal and existential statements for algorithm proof?

Use universal statement for correct proofs,

use existential statement for incorrect proofs

Negations

The opposite meaning of the original statement

How to negate an existential statement

for every x in set S, P(x) is false

How to negate a universal statement

there exist a x in the set S such that P(x) is false

Implication

A implies B = If A is true, then B is true

How to negate implications?

A is true and B is false

Converse

Swapping implication statements relationship

e.g. A implies B -> B implies A

Contrapositive

not B implies not A

always equivalent with implication (both false and both true)

How to proof a statement is true?

Showing that its negation is false

How to proof a statement is false?

Showing that its negation is true

Modus ponens

If statements "A", and "A implies B" are true,

statement "B" is true

Contradiction

if we can show a statement is false

Proof by contradiction recipe

Suppose that X (which we wish to prove) is false.

Choose a statement Y that we know to be true.

Use the assumption that X is false to show that is Y false.

Since Y being both true and false is a contradiction, we know that X is true.

Recipe for proving a universal statement using a generic element

Identify properties of a generic x in S.

Show that P(x) is true.

Recipe for proving an existential statement

Choose an x.

Show that is x in S.

Show that is P(x) true.

Recipe for proving an algorithm is not correct

Choose an instance x.

Show that x is an instance of the problem the algorithm is supposed to solve.

Show that the algorithm produces y.

Show that the correct solution to the problem on x is z, where z is better than y.

Counterexample

an example that proves that a statement is false

How to create counterexamples?

Start with something small and simple;

If your counterexample fails, learn from how to fails to determine how to modify it.

What is a spanning tree?

A tree connecting all vertices in a connected graph, formed of a subset of the edges in the graph.

What is a minimum spanning tree?

A spanning tree such that the sum of the weights of the edges is minimized.

Kruskal's Algorithm

Start with an empty set of edges;

add the lowest weight edge that doesn't form a cycle

Prim's Algorithm

Start with one vertex as the tree,

adds the lowest weight edge that joins a vertex outside of the tree

What is the worst-case running time for Kruskal's Algorithm?

Θ(mlogm)

m = # of edges

What is the worst-case running time for Prim's Algorithm?

Θ(mlogn)

m = # of edges

n = # of vertices

Special Path (Dijkstra's Algorithm)

Given K is a set of vertices where the cheapest paths from origin vertex s is known,

special path only uses vertices in K as intermediate vertices

Dijkstra's Algorithm

Finds the shortest paths between vertices by repeatedly choosing the cheapest special path to a vertex in U, and adding that vertex to K

K = set of vertices where cheapest path from origin vertex s is know

U = set of vertices that doesn't belong in K

What are the 2 properties to prove correctness of a greedy algorithm?

Optimal Substructure Property and Greedy Choice Property

Optimal Substructure Property

A problem satisfies this property when the optimal solution to an instance of a problem can be formed from optimal solutions to one or more smaller instances formed from the original instance.

Greedy Choice Property

A greedy algorithm satisfies this property when there is an optimal solution consistent with each greedy choice made by the algorithm.