Exam (elaborations)

CS 573: Algorithms, Fall 2013

0 purchase

Course
Nursing (CS573)

Institution
Thompson River University (TRU )

1. Greedy algorithm do not work. (40 pts.) Anaturalalgorithm, GreedyIndep, forcomputingmaximumindependentsetinagraph, istorepeatedly remove the vertex of lowest degree in the graph, and add it to the independent set, and remove all its neighbors. (A) (5 pts.) Show an example, where this algorithm...

[Show more]

Preview 2 out of 5 pages

View example

Uploaded on January 27, 2021
Number of pages 5
Written in 2020/2021
Type Exam (elaborations)
Contains Questions & answers

algorithms

Welch1 Member since 6 year 61 documents sold

CA$15.50

Add to cart

Add to wishlist

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

CS 573: Algorithms, Fall 2013
Homework 2 solution Version 1.0

1. Greedy algorithm do not work. (40 pts.)
A natural algorithm, GreedyIndep, for computing maximum independent set in a graph, is to repeatedly
remove the vertex of lowest degree in the graph, and add it to the independent set, and remove all its
neighbors.
(A) (5 pts.) Show an example, where this algorithm fails to output the optimal solution.

Solution:
Consider the example depicted below. The algorithm would choose the vertex 1 and one vertex out of
4, 5, 6, or 7. Namely, generating an independent set of size two. However, the maximal independent
set has size three; namely, {2, 3, 7}.
2 5

m
er as
4

co
eH w
1 7

o.
rs e
ou urc
3 6

(B) (5 pts.) Let G be a (k, k + 1)-uniform graph (this is a graph where every vertex has degree either k
o

or k + 1). Show that the above algorithm outputs an independent set of size Ω(n/k), where n is the
aC s

number of vertices in G.
vi y re

Solution:
Since G is (k, k + 1)-uniform, at most k + 2 vertices are removed from the graph on each iteration of
n
the algorithm. Therefore, it takes at least k+2 to all vertices to be removed from the graph. This
ed d

means that the algorithm outputs an independent set of size Ω(n/k).
ar stu

This argument implies a more general result. If the maximum degree in the graph G is ∆, then there
is an independent set in G of size |V(G)| /(∆ + 1).
(C) (5 pts.) Let G be a graph with average degree δ (i.e., δ = 2 |E(G)| / |V (G)|). Prove that the above
sh is

algorithm outputs an independent set of size Ω(n/δ).
Th

Solution:
Form a new graph G′ by removing all vertices in G that have degree greater than 10δ. Let U be the
number of vertices in G that are of degree larger than 10δ. Clearly, 10δ · U ≤ 2|E(G)| ≤ nδ, which
implies that U ≤ n/10. Thus, at most n/10 vertices are removed from G when creating G′ .
Now, an independent set in G′ will be an independent set in G. Since all vertices in G′ have degree
at most 10δ, the same argument as in part (B) can be used to show that our algorithm outputs an
independent set for G′ of size
( ) ( ) ( )
|V (G′ )| 0.9n n
Ω =Ω =Ω .
10δ 10δ δ
Since this independent set is an independent set for G, we are done.

1
https://www.coursehero.com/file/10913885/HW2Solutions/

, (D) (5 pts.) For any integer k, present an example of a graph Gk , such that GreedyIndep outputs an
independent set of size ≤ |OP T (Gk )| /k, where OP T (Gk ) is the largest independent set in Gk . How
many vertices and edges does Gk has? What it the average degree of Gk ?
Solution:
Consider the following graph G:
1

2

K2k+1
0

2k

m
Our algorithm would choose vertex 0, removing vertices 1 through 2k. Then, only the clique K2k+2

er as
will remain. Then, a vertex from this clique will be chosen, deleting the entire graph. This yields an

co
independent set of size 2. However the maximal independent set actually has size 2k and contains

eH w
the vertices 1 through 2k. Therefore, the greedy algorithm outputs an independent set of size 2,

o.
k = |Opt(G)|/k.
which is ≤ 2k

rs e
(E) (20 pts.) Coloring. Let G be a graph deﬁned over n vertices, and let the vertices be ordered: v1 , . . . , vn .
ou urc
Let Gi be the induced subgraph of G on v1 , . . . , vi . Formally, Gi = (Vi , Ei ), where Vi = {v1 , . . . , vi }
and { }
Ei = uv ∈ E u, v ∈ Vi and uv ∈ E(G) .
o
aC s

The greedy coloring algorithm, colors the vertices, one by one, according to their ordering. Let ki
vi y re

denote the number of colors the algorithm uses to color the ﬁrst i vertices.
In the ith iteration, the algorithm considers vi in the graph Gi . If all the neighbors of vi in Gi are
using all the ki−1 colors used to color Gi−1 , the algorithm introduces a new color (i.e., ki = ki−1 + 1)
and assigns it to vi . Otherwise, it assign vi one of the colors 1, . . . , ki−1 (i.e., ki = ki−1 ).
ed d

Give an example of a graph G with n vertices, and an ordering of its vertices, such that even if G can
ar stu

be colored using O(1) (in fact, it is possible to do this with two) colors, the greedy algorithm would
color it with Ω(n) colors. (Hint: consider an ordering where the ﬁrst two vertices are not connected.)
Solution:
sh is

x1 1 1 y1
Consider the bipartite graph G ={(X, Y, E), where } X = {x1 , . . . , xn },
Th

Y = {y1 , . . . , yn }, and E = (xi , yj ) i ̸= j and the ordering
x2 2 2 y2
x1 , y1 , x2 , y2 , . . . , xn , yn . Then, using our greedy algorithm, the ver- x3 3 3 y3
tices x1 , . . . , xn will be colored using n distinct colors. Thus, using a
total Θ(n) colors. But it is possible to color the graph using only 2 x4 4 4 y4
colors, since it is a bipartite graph. See ﬁgure on the right.
x5 5 5 y5

2
https://www.coursehero.com/file/10913885/HW2Solutions/

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Welch1. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for CA$15.50. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

62774 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling

Seller

Exam (elaborations) ·

Exam (elaborations)

CS 573: Algorithms, Fall 2013

Document information

Subjects

Written for