Suppose we are given a graph G = (V,E) and we want to color each vertex...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Suppose we are given a graph G = (V,E) and we want to color each vertex with one of three colors, say red,green, blue. Given a coloring of the vertices in V, we say that an edge e = {u, v} is satisfied if the colors assigned to u and u are different. For this question, we used the term coloring to mean a coloring of the vertices of V. Consider the following randomized algorithm for coloring the vertices of V for an input graph G = (V,E). Algorithm 1: Algorithm for Question 1 Input Graph G = (V,E) Output: A coloring of the vertices of V 1 foreach vЄ V do 2 3 4 end Select a color c uniformly at random from the set red, green, blue Color vertex v with the color c 5 return The computed coloring of V Basically, the algorithm uniformly at random assigns one of three colors to each vertex independently and returns that coloring. Recall that uniformly at random means that each color is picked with probability 1/3. Answer the following questions: a. Compute the probability that an arbitrary edge e = {u, v} = E is satisfied by a coloring computed by the randomized algorithm. That is, what is the probability that u, v are assigned different colors by the algorithm? b. Compute the expected number of edges satisfied by a coloring returned by the algorithm. That is, if X is a random variable representing the number of edges satisfied by a coloring returned by the algorithm, compute E[X], the expectation of X. c. For the graph given in Figure 1 below, is it possible to color the vertices using colors red, green, blue so that every edge is satisfied by the coloring? If yes, give one such coloring. If no, explain why not. 2 ст 5 1 4 3 6 Suppose we are given a graph G = (V,E) and we want to color each vertex with one of three colors, say red,green, blue. Given a coloring of the vertices in V, we say that an edge e = {u, v} is satisfied if the colors assigned to u and u are different. For this question, we used the term coloring to mean a coloring of the vertices of V. Consider the following randomized algorithm for coloring the vertices of V for an input graph G = (V,E). Algorithm 1: Algorithm for Question 1 Input Graph G = (V,E) Output: A coloring of the vertices of V 1 foreach vЄ V do 2 3 4 end Select a color c uniformly at random from the set red, green, blue Color vertex v with the color c 5 return The computed coloring of V Basically, the algorithm uniformly at random assigns one of three colors to each vertex independently and returns that coloring. Recall that uniformly at random means that each color is picked with probability 1/3. Answer the following questions: a. Compute the probability that an arbitrary edge e = {u, v} = E is satisfied by a coloring computed by the randomized algorithm. That is, what is the probability that u, v are assigned different colors by the algorithm? b. Compute the expected number of edges satisfied by a coloring returned by the algorithm. That is, if X is a random variable representing the number of edges satisfied by a coloring returned by the algorithm, compute E[X], the expectation of X. c. For the graph given in Figure 1 below, is it possible to color the vertices using colors red, green, blue so that every edge is satisfied by the coloring? If yes, give one such coloring. If no, explain why not. 2 ст 5 1 4 3 6
Expert Answer:
Posted Date:
Students also viewed these accounting questions
-
7) The second financial statement to prepare is the statement of retained eamings. To determine the ending balance of retained earnings you need to start with the opening balance as reported in the...
-
5. A population is known to be normally distributed with a mean u = 11.4 and a variance =3. If a random sample of size 16 is taken, find the probability that this sample will: a) have a sample mean...
-
(i) A submit button, using the tag, which should be labeled ReadMessage (ii) A JavaScript function identified as: readMessages. This function should be activated/triggered when the administrator...
-
In Canada, Canadian teachers and bosses and HIGH AUTHORITY FIGURES are not FEARED but RESPECTED. In CANADA TEACHERS, bosses and AUTHORITY FIGURES encourage feedback, OPINIONS and ENGAGE in discuss....
-
Suppose that the yield curve on Eurodollars is sharply upward- sloping. a. Will premiums on interest rate floors on three- month LIBOR be high or low? Explain. b. Will premiums on interest rate caps...
-
1. Now, assume Top-A1's sales in the subsequent year increase by 15 percent. If all the other relationships remain the same, what will be the pro forma net earnings in two years? 2. Again, assume...
-
Using the bid spot currency quotes shown in question 2 above, answer the following: a. What is the current cross spot rate of Mexican pesos/pounds sterling? b. What is the current cross spot rate of...
-
Family Supermarkets (FS) has a kaizen (continuous improvement) approach to budgeting monthly activity costs for each month of 2011. Each successive month, the budgeted cost-driver rate decreases by...
-
9 Chapter Waren Sports Supply PART-QUESTIONS Q-9-1. Accrued Interest Payable Required Interest accruals are calculated using a 365-day year with the day after the note was made counting as the first...
-
In a simple pendulum of length 1 the bob is pulled aside from its equilibrium position through an angle 0 and then released. The bob passes through the equilibrium position with speed (a) 2gl(1 +...
-
Some progressive hair dyes marketed to men, such as GrecianFormula 16, contain lead acetate, Pb(CH3CO2)2. As the dye solutionis rubbed on the hair, the Pb2+ ions react with the sulfur atoms inhair...
-
Comparison of Apple inc. horizontal analysis based on the balance sheet of the company years 2020-2021 and 2021-2022
-
If you decide to revise your essay for a better grade, I expect you to make radical revisions to your essay. (e.g. A major change to a paragraph, idea, thesis, example, etc. 2. AND highlight the...
-
Assignment Details This list contains costs that various organizations incur; they fall into three categories: direct materials (DM), direct labor (DL), or overhead (OH). Classify each of these items...
-
Another example : int shsort(int s[], int n){ /* Shell Sort */ int i, j,d; d=n/2; while(d>=1){ } for(i=d+1;i 0)&&(s[0]
-
Item A is one of the products manufactured at ABC Manufacturing. Each order for producing the product has a cost of $100/order, regardless of the number of units ordered. The lead time for placing...
-
You have just begun your summer internship at Omni Instruments. The company supplies sterilized surgical instruments for physicians. To expand sales, Omni is considering paying a commission to its...
-
Jon Alden is puzzled. His company had a profit margin of 10% in 2002. He feels that this is an indication that the company is doing well. Anna Weis, his accountant, says that more information is...
-
(a) If Nick Flach Company had net income of \($540,000\) in 2001 and it experienced a 24.5% in- crease in net income for 2002, what is its net in- come for 2002? (b) If six cents of every dollar of...
-
Brian Tanaka Company, a retail store, has a receivables turnover ratio of 4.5 times. The industry aver- age is 12.5 times. Does Tanaka have a collection problem with its receivables?
Study smarter with the SolutionInn App