1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nana76 [90]
3 years ago
11

• karger's min cut algorithm in the class has probability at least 2/n2 of returning a min-cut. how many times do you have to re

run this algorithm to get the probability of an error to be at most 1/n?
Mathematics
1 answer:
MrRissso [65]3 years ago
4 0
The Karger's algorithm relates to graph theory where G=(V,E)  is an undirected graph with |E| edges and |V| vertices.  The objective is to find the minimum number of cuts in edges in order to separate G into two disjoint graphs.  The algorithm is randomized and will, in some cases, give the minimum number of cuts.  The more number of trials, the higher probability that the minimum number of cuts will be obtained.

The Karger's algorithm will succeed in finding the minimum cut if every edge contraction does not involve any of the edge set C of the minimum cut.

The probability of success, i.e. obtaining the minimum cut, can be shown to be ≥ 2/(n(n-1))=1/C(n,2),  which roughly equals 2/n^2 given in the question.Given: EACH randomized trial using the Karger's algorithm has a success rate of P(success,1) ≥ 2/n^2.

This means that the probability of failure is P(F,1) ≤ (1-2/n^2) for each single trial.

We need to estimate the number of trials, t, such that the probability that all t trials fail is less than 1/n.

Using the multiplication rule in probability theory, this can be expressed as
P(F,t)= (1-2/n^2)^t < 1/n 

We will use a tool derived from calculus that 
Lim (1-1/x)^x as x->infinity = 1/e, and
(1-1/x)^x < 1/e   for x finite.  

Setting t=(1/2)n^2 trials, we have
P(F,n^2) = (1-2/n^2)^((1/2)n^2) < 1/e

Finally, if we set t=(1/2)n^2*log(n), [log(n) is log_e(n)]

P(F,(1/2)n^2*log(n))
= (P(F,(1/2)n^2))^log(n) 
< (1/e)^log(n)
= 1/(e^log(n))
= 1/n

Therefore, the minimum number of trials, t, such that P(F,t)< 1/n is t=(1/2)(n^2)*log(n)    [note: log(n) is natural log]
You might be interested in
Select the correct answer.
lakkis [162]
Answer B …… if im not wrong
5 0
2 years ago
Read 2 more answers
The linear function f i with values f(-1) = 10 and f(5) = -1 is f(x)
zhenek [66]
Answer:

Use the two points to compute the slope, m, then use one of the points in the form <span>y=m<span>(x)</span>+b</span> to find the value of b.

Explanation:

The equation for the slope, m, of a line is:

<span>m=<span><span><span>y1</span>−<span>y0</span></span><span><span>x1</span>−<span>x0</span></span></span> [1]</span>

The equation <span><span>f<span>(2)</span></span>=−1</span> tells us that <span><span>x0</span>=2and<span>y0</span>=−1</span>; substitute this into equation [1]:

<span>m=<span><span><span>y1</span>−−1</span><span><span>x1</span>−2</span></span> [2]</span>

The equation <span><span>f<span>(5)</span></span>=4</span> tells us that <span><span>x1</span>=5and<span>y1</span>=4</span>; substitute this into equation [2]:

<span>m=<span><span>4−−1</span><span>5−2</span></span> [3]</span>

<span>m=<span>53</span></span>

Substitute <span>53</span> for m into the equation <span>y=m<span>(x)</span>+b</span>

<span>y=<span>53</span>x+b [4]</span>

Substitute 2 for x and -1 for y and the solve for b:

<span>−1=<span>53</span><span>(2)</span>+b</span>

<span>b=−<span>133</span></span>

Substitute <span>−<span>133</span></span> for b in equation [4]:

<span>y=<span>53</span>x−<span>133</span> [5]</span>

Check:

<span>−1=<span>53</span><span>(2)</span>−<span>133</span></span>
<span>4=<span>53</span><span>(5)</span>−<span>133</span></span>

<span>−1=−1</span>
<span>4=<span>4</span></span>

<span><span>
</span></span>

<span><span>Hope this helps </span></span>

3 0
3 years ago
The wholesale price for a desk is $199. A certain furniture store marks up the wholesale price by 24%. Find the price of the des
eduard

Answer:

246.76$

Step-by-step explanation:

199 x .24 =

47.76

199 + 47.76 =

246.76

5 0
2 years ago
2+4(x+1)-x<br>2+4x+-x<br>6+4x-x<br>6+3x​
Nat2105 [25]

Answer:

What is your question

Step-by-step explanation:

5 0
2 years ago
Now, that you have the new wheel circumference, what will happen to the number of rotations if the circumference of the tires we
butalik [34]

The number of rotations for the new wheel will be  1,056 rotations

<h3>How to calculate the circumference of a wheel?</h3>

Let the initial circumference be 50 rotations  (assumed)

If the number of rotations of the circumference of the tires were increased by 20%, then the new circumference will be:

Ne circumference = 1.2 * 50 = 60

number of rotations for the new wheel = 63360/60
number of rotations for the new wheel = 1,056 rotations

Hence the number of rotations for the new wheel will be  1,056 rotations

Learn more on circumference here: brainly.com/question/20489969

7 0
2 years ago
Other questions:
  • Darcy baked 8 muffins. She put blueberries in 5/8 of the muffins. She put raspberries in 3/8 of the muffins. Did more muffins ha
    13·1 answer
  • How many tickets must be sold on Saturday to make the median and the mode the same?
    12·1 answer
  • Ming made a triangular picture frame out of cardboard. The sides of the frame are 6.75 in., 6.75 in., and 8.375 in. Ming uses th
    12·2 answers
  • Two angles are supplementary if their sum is​ 180°. the larger angle measures five degrees more than four times the measure of a
    8·1 answer
  • -256÷457.6 a -16 b -1.6c 1.6 d 16
    13·2 answers
  • The amount y (in grams) of the radioactive isotope fermium-253 remaining after t hours is y=a(0.5)t/72, where a is the initial a
    14·1 answer
  • I'll put this as random but you can answer it... <br> ill give yall 10 points if yall do it!
    10·2 answers
  • Maria and victor each play a video game. The ratio of the number of points Maria scores to the number of points victor scores is
    15·1 answer
  • What is the value of x? <br> Will brainlist first correct answer
    7·2 answers
  • Please I need help Asap!
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!