Algorithms & Data Structures (Winter 2022) Extras – Randomization and Probabilistic Analysis
• AmortizedAnalysis.
• Randomized algorithms. • ProbabilisticAnalysis.
Copyright By PowCoder代写 加微信 powcoder
• Review Final Exam.
Randomization
Principle: Allow flip a fair coin in unit time.
Why? Can lead to simplest, fastest, or only known
algorithm for a particular problem.
• Quicksort
• Graph Algorithms
• Monte-Carlo integration • Distributed systems
• Cryptography
Global Min Cut
Definition: Given a connected, undirected graph G=(V,E), find a cut with minimum cardinality.
• A cut partitions the nodes of G into two nonempty subsets.
• The size of the cut is the number of crossing edges, which have one endpoint in each subset.
• A minimum cut in G is a cut with the smallest number of crossing edges
• The same graph may have several minimum cuts.
Global Min Cut
Definition: Given a connected, undirected graph G=(V,E), find a cut with minimum cardinality.
Network solution:
• Replace every edge (u,v) with 2 antiparallel edges (u,v) & (v,u)
• Pick some vertex s, and compute min s-v cut for each other vertex v.
• This is n − 1 directed minimum-cut computations
• Fastest deterministic algorithm run in O(n3) and it is complex.
False Intuition: Global min-cut is harder that min s-t cut!
Contraction Algorithm
• The Contraction Algorithm works with a connected multigraph. • This is an undirected graph that is allowed to have multiple “parallel”
edges between the same pair of nodes.
• Uses a primitive operation called edge contraction. • Requires O(n) time
Contraction Algorithm
• The Contraction Algorithm works with a connected multigraph. • This is an undirected graph that is allowed to have multiple “parallel”
edges between the same pair of nodes.
• Uses a primitive operation called edge contraction. • Requires O(n) time
Contraction Algorithm
Contraction Algorithm
Contraction Algorithm
Contraction(V,E):
While 𝑉 >2do
Choose 𝑒 ∈ 𝐸 uniformly at random 𝐺 ←𝐺 − 𝑒 //contractG
return { the only cut in G }
Randomization
• The algorithm is making random choices,
• There is some probability that it will succeed in finding a global min-cut
and some probability that it won’t.
• There are exponentially many possible cuts of G.
• One might imagine that the probability of success is exponentially small. • what’s favoring the minimum cut in the process?
Contraction Algorithm
Contraction(V,E):
While 𝑉 >2do
Choose 𝑒 ∈ 𝐸 uniformly at random 𝐺 ←𝐺 − 𝑒 //contractG
Randomization • The algorithm is making random choices,
• There is some probability that it will succeed in finding a global min-cut and some probability that it won’t.
• There are exponentially many possible cuts of G.
• One might imagine that the probability of success is exponentially small.
return { the only cut in G }
• what’s favoring the minimum cut in the process?
Contraction Algorithm
Contraction Algorithm
Contraction Algorithm
Contraction Algorithm
Contraction Algorithm
Where𝑚= 𝐸.Overallcomplexity𝑂(𝑛!𝑚log𝑛)
• We can increase the number of iterations, but it is usually overkill.
• We’re facing a tradeoff between the speed of the algorithm and its probability of
Improvement:
• As the graph shrinks, the probability of contracting an edge in the minimum cut increases. In other words, early iterations are less risky than later ones.
• At first the probability is quite small, only 2/n, but near the end of execution, when the graph has only three vertices, we have a 2/3 chance of screwing up!
• To group the first several random contractions a “safe” phase, so that the
cumulative probability of screwing up is relatively small and a “dangerous”
phase, which is much more likely to screw up.
• To get around the danger of the dangerous phase, we use amplification: we run
the dangerous phase four times and keep the best of the four answers.
• O(n2log3n)
• Best known O(mlog3n)
• AmortizedAnalysis.
• Randomized algorithms. • ProbabilisticAnalysis.
• Review Final Exam.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com