Algorithms Design

Algorithms Design

• 1.
  RANDOMIZED ALGORITHMS Moiz Mehmood AbdullahRamzan Wajahat Ali
• 2.
  History An important lineof research in randomized algorithms in number theory can be traced back to Pocklington's theorem from 1917, which finds square root modulo prime numbers. The study of randomized algorithms in number theory was spurred by the 1977 discovery of a randomized primality test (i.e., determining the primality of a number) by Robert M. Solovay and Volker Strassen. Soon afterwards Michael O. Rabin demonstrated that the 1976 miller primality test can be turned into a randomized algorithm. At that time, no practical deterministic test for primality was known.
• 3.
  Deterministic Algorithm Input AlgorithmOutput A deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.
• 4.
  PROBLEM IN DETERMINISTICALGORITHM • If the size of n becomes extremely large, then even deterministic algorithm takes a lot of time to solve. • These types of problem can be solved by randomized algorithm
• 5.
  RANDOMIZED ALGORITHMS • An algorithmthat uses random number to decide what to do next any where in is logic called randomized algorithm. • This algorithm is used to reduce space and complexity
• 6.
  RANDOMIZED ALGORITHMS Working Mechanism Input Randomized AlgorithmOutput
• 7.
  Advantage of Randomized algorithms Randomizedalgorithm for a problem is usually simpler and more efficient than Its deterministic counter part
• 8.
  TYPES OF RANDOMIZED ALGORITHMS LasVegas algorithms Monte-Carlo algorithms
• 9.
  LAS VEGAS ALGORITHM Output isalways correct Running time is a random variable
• 10.
  MINTO-CARLO ALGORITHM Output may beincorrect Running time is deterministic
• 11.
  APPLICATION OF RANDOMIZED ALGORITHMS Min-cut isminimum number of edges that we need To remove so that the connected graph is divided into Two disjoint sets RANDOM-MIN-CUT • Repeat 2 to 4 until only 2 vertices are left • Pick an edge E (u,v) at random • Merge u and v • Remove self loop from E • RETURN |E|
• 12.
  Example A D B E F C
• 13.
  • Check |v|=6>2yes • Pick an edge at random (b,d) • merge b&d • now we have new vertex bd • v={a ,bd, c,e,f} Example A BD C E F
• 14.
  • Check |v|=6>2If true, • Check |V|=5>2 • If true, Pick an edge at random (E,F) • V={A,BD,C,EF} Example A C E BD F A BD EF C Remove self loop
• 15.
  • Remove selfloop • Check |v| =4>2 YES • Pick an edge (A,BD) • V={ABD,C,EF} • Check |V|=3>2 YES • Pick an edge (C,EF) • V={ABD,CEF} Example ABD EF C ABD EF C Remove self loop
• 16.
  • Check |V|=2>2,NO Example This is the minimum number of edges which should remove from the graph to make a disjoint set ABD CEF ABD CEF ABD CEF Remove self loop
• 17.
  Randomized algorithms areused whenever we are presented with time or memory constraints, and when an average case solution is acceptable. So, you will see randomized algorithms in fields such as: • Number theoretic algorithms – Primality Testing • Data Structures – Searching, sorting, computational geometry • Algebraic Identities – Verification of polynomial and matrix identities • Mathematical Programming – Faster linear programming algorithms • Graph algorithms – Finding minimum spanning trees, shortest paths, minimum cuts • Counting and enumeration – Counting combinational structures • De-randomization - Randomness can be viewed as a resource, like space and time. De-randomization is then the process of removing randomness (or using as little of it as possible). Uses
• 18.
  Thank you!