## Interview Question

- -1of 3 votes

AnswerLet "output" denote the cut output by Karger's min cut algorithm on a given connected graph with n vertices, and let p=1/(n "up" 2). Which of the following statements are true? For hints on this question, you might want to watch the short optional video on "Counting Minimum Cuts".

- mohammad.n.aabed July 24, 2013 in United States

For every graph G with n nodes and every min cut (A,B) of G,

Pr[out=(A,B)]≥p.

For every graph G with n nodes, there exists a min cut (A,B) such that

Pr[out=(A,B)]≤p.

For every graph G with n nodes and every min cut (A,B),

Pr[out=(A,B)]≤p.

There exists a graph G with n nodes and a min cut (A,B) of G such that

Pr[out=(A,B)]≤p.

For every graph G with n nodes, there exists a min cut (A,B) of G such that

Pr[out=(A,B)]≥p.| Report Duplicate | Flag | PURGE

Email me when people comment.

Email me when people comment.

Loading...

An error occurred in subscribing you.

**Country:**United States

Email me when people comment.

Email me when people comment.

Loading...

An error occurred in subscribing you.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Buhwahahahaha.. Very funny. This is a question from coursera's algorithm course. The answer to this mulitple question is: A,D,E.

- Anonymous July 25, 2013>> For hints on (AND ANSWERS TO) this question, you might want to watch the short optional video on "Counting Minimum Cuts".

LOLLLLLLLLLL