Greedy Algorithms

Question 1

What are some cons of greedy algorithms?

Answer 1

Local “correct” steps might not mean global correctness.
Often does not lead to optimal solutions.

Question 2

PROBLEM: Vertex Cover

Answer 2

Given an undirected graph G = (V, E) on n vertices, find a set X of minimum size such that each edge of G has at least one-endpoint in X.

Question 3

What is the definition of a spanning tree?

Answer 3

A subgraph T = (V’ , E’) of G is said to be a spanning tree of G if

• spanning: V’ = V
• tree: |E’ | = n - 1

Question 4

PROBLEM: MST

Answer 4

Given an undirected, connected graph G = (V, E) with edge-costs given by cost : E -> R+ , find a spanning tree T = (V, E’) such that the sum of edge costs is minimized.

Question 5

THEOREM: MST

Answer 5

For any S c V , let e be the edge of minimum cost having one end-point in S an other end-point in V \ S.
Then, every MST contains the edge e.

Question 6

PROBLEM: Interval Scheduling

Answer 6

Select a set C ⊆ R of requests such that |C| is maximized and no two requests from C conflict.