*NURSING > QUESTIONS & ANSWERS > CS 573: Algorithms, Fall 2013 (All)

CS 573: Algorithms, Fall 2013

Document Content and Description Below

. 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 i... ndependent 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}. 1 2 3 4 5 6 7 (B) (5 pts.) Let G be a (k,k +1)-uniform graph (this is a graph where every vertex has degree either k or k +1). Show that the above algorithm outputs an independent set of size Ω(n/k), where n is the number of vertices in G. Solution: Since G is (k,k+1)-uniform, at most k+2 vertices are removed from the graph on each iteration of the algorithm. Therefore, it takes at least n k+2 to all vertices to be removed from the graph. This means that the algorithm outputs an independent set of size Ω(n/k). 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 algorithm outputs an independent set of size Ω(n/δ). 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′)| 10δ )=Ω(0.9n 10δ)=Ω(n δ) [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages

Reviews( 1 )

user-profile-pic


by Senpai · 2 years ago

Very helpful

Recommended For You

 Computer Science> QUESTIONS & ANSWERS > CS 573: Algorithms, Fall 2013 Homework 3: Solutions (All)

preview
CS 573: Algorithms, Fall 2013 Homework 3: Solutions

CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.0 1. Prove infeasibility. (25 pts.) You are trying to solve a circulation problem, but it is not feasible. The problem has demands, bu...

By Cheryshev , Uploaded: May 21, 2021

$8

 Business> QUESTIONS & ANSWERS > CLM 031 EXAM (All)

preview
CLM 031 EXAM

CLM 031 = 100% Question 1: 5b Select the statement that is correct concerning performance work statement (PWS) requirements: - All answers are correct. - PWS should describe requirements necessary...

By Book Worm, Certified , Uploaded: Nov 03, 2022

$5

 *NURSING> QUESTIONS & ANSWERS > PHIL 347 Week 6 Checkpoint Quiz. Score 100/100 (All)

preview
PHIL 347 Week 6 Checkpoint Quiz. Score 100/100

Question: What are the three fundamental reasoning strategies listed in the text? Question: What is comparative reasoning? On what skill is it based? Question: We learned four tests for evaluating...

By Amanda Rosales , Uploaded: Mar 24, 2021

$7

 Business> QUESTIONS & ANSWERS > BUSINESS 1007 (All)

preview
BUSINESS 1007

BUSINESS 1007 07 Key 1. (p. 178) Managers utilize organizational resources such as employees, information, and equipment to accomplish goals. 2. (p. 178) The main job of managers today is to w...

By Kirsch , Uploaded: Oct 19, 2019

$6

 Anthropology> QUESTIONS & ANSWERS > KOR 352 FA19 101 week 8 Quiz. Already Graded A (All)

preview
KOR 352 FA19 101 week 8 Quiz. Already Graded A

KOR 352 FA19 101: Week 8 Quiz Question 1 (0.25 points) Which of the following is not true of Kim and Finch’s observations during their field research in South Korea from 1997 to 2000? Question 1 o...

By Kirsch , Uploaded: Oct 17, 2019

$9

 E-Commerce> QUESTIONS & ANSWERS > ESOC 316 Digital Commerce - University Of Arizona. Midterm Quiz. 20 Q&A. 100% Score (All)

preview
ESOC 316 Digital Commerce - University Of Arizona. Midterm Quiz. 20 Q&A. 100% Score

ESOC 316 Digital Commerce - University Of Arizona. Midterm Quiz. 20 Q&A. 100% Score ESOC316 MIDTERM QUIZQuestion 6 (1 point) Saved Information has several properties that make information goods...

By Kirsch , Uploaded: Oct 15, 2019

$9.5

 Marketing> QUESTIONS & ANSWERS > Marketing Management Chapter 2 to Chapter 10 Q&A (All)

preview
Marketing Management Chapter 2 to Chapter 10 Q&A

Chapter 2 to Chapter 10 Chapter 2: Developing Marketing Strategies and Plans GENERAL CONCEPT QUESTIONS Multiple Choice 66 Chapter 1: Marketing: Managing Profitable Customer Relationships...

By Kirsch , Uploaded: Oct 14, 2019

$10

 Marketing> QUESTIONS & ANSWERS > MKT 530 Customer Relationship Management. 155 Questions and Answers (All)

preview
MKT 530 Customer Relationship Management. 155 Questions and Answers

MKT 530 All Questions and Answers MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question. 1) As the manager of an organization that is att...

By Kirsch , Uploaded: Oct 14, 2019

$10

 Art> QUESTIONS & ANSWERS > MAS 337 Exam 1. Graded A (All)

preview
MAS 337 Exam 1. Graded A

MAS 337 Exam 1 Match the son with its corresponding region. 1.Oaxaca 2.Veracruz 3.Michoacan 4.Jalisco 5.Hidalgo 1. Son istemeno 2. Son Jarocho 3. Son Abajeno 4. Son Jalisciense 5. Son Huast...

By Kirsch , Uploaded: Oct 14, 2019

$6

 Art> QUESTIONS & ANSWERS > MUS 337 Final Exam Graded 100%. (All)

preview
MUS 337 Final Exam Graded 100%.

MUS 337 Final Daisy Moreno-Cota Fri Dec 11 12:59:42 PST 2015 Tone or aural color Volume and articulation of sounds Frequency of the tone Phonic structure or relationships between the sounds Dura...

By Kirsch , Uploaded: Oct 12, 2019

$9

$10.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
84
1

Document information


Connected school, study & course



About the document


Uploaded On

Jan 27, 2021

Number of pages

5

Written in

Seller


seller-icon
Senpai

Member since 4 years

12 Documents Sold


Additional information

This document has been written for:

Uploaded

Jan 27, 2021

Downloads

 1

Views

 84

Document Keyword Tags

THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

custom preview

Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

custom preview

Get the best grades

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

custom preview

Earn from your notes

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.


$10.00

WHAT STUDENTS SAY ABOUT US


What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·