Data Structures and Algorithms - EE 390
Module 10
Algorithm Implementation
Paradigms
Dr. Anirban Dasgupta
Assistant Professor
Department of Electronics And Electrical Engineering, IIT Guwahati
Types of Algorithms
Algorithms
Based on Data-Structure Based on Design Based on Implementation Based on Application
String Algorithms Greedy Algorithms Iterative or Recursive Sorting
Array Algorithms Divide and Conquer Serial or Parallel Searching
Tree Algorithms Dynamic Procedural or Numerical
Programming Declarative
Graph Algorithms Deterministic or Optimization
Linear Programming
Randomized
Signal Processing
Reduction
Exact or Approximate
Computer Vision
Brute Force or
Backtracking Machine Learning
Networking
Department of Electronics And Electrical Engineering, IIT Guwahati
Types of Algorithms
Based on Implementation Paradigm
recursively exploring combinations of
possible choices to arrive at a solution
Backtracking
focuses on what needs to be function calling itself
Declarative
Recursive
achieved rather than how it Algorithm
should be achieved
incorporates randomness into
solve problems that are not solvable its logic, using random
Approximate Randomized choices to guide its behavior
in polynomial time for approximate Algorithms Algorithm
solutions
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion
• Recursion is a method of program design where you break apart a problem into
smaller repeatable subtasks
• A recursive function has at least two parts:
• a base condition
• at least one recursive case
• A recursive function is a function that calls itself until a “base condition” is true, and
execution stops
• Inputs become smaller at each step
• Recursion is the concept of well-defined self-reference.
• Advantages:
• only need to define the base condition and the recursive case in a recursive function
• makes the code pretty simple and short as compared to an iterative code
Department of Electronics And Electrical Engineering, IIT Guwahati
Department of Electronics And Electrical Engineering, IIT Guwahati
Examples of Recursion
Factorial Calculation
Fibonacci Series
Binary Search
Tree Traversal
Merge Sort
Tower of Hanoi
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion: Sum of Natural Numbers
Base Case: csum(1) = 1
Recursion: csum(n) = n + csum(n-1)
csum(5)=5 + csum(4)
=5 + 4 + csum(3)
=5 + 4 + 3 + csum(2)
=5 + 4 + 3 + 2 + csum(1)
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion: Factorial
Base Case: Factorial(1) = 1
Recursion: Factorial(n) = n × Factorial(n-1)
Factorial(5)=5 × Factorial(4)
=5 × 4 × Factorial(3)
=5 × 4 × 3 × Factorial(2)
=5 × 4 × 3 × 2 × Factorial(1)
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion: Fibonacci
Base Case: Fibonacci(1) = 1, Fibonacci(0) = 0
Recursion: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Fibonacci(5)=Fibonacci(4) + Fibonacci(3)
=Fibonacci(3) + Fibonacci(2) + Fibonacci(2) + Fibonacci(1)
=Fibonacci(2) + Fibonacci(1) + 2 Fibonacci(2) + Fibonacci(1)
=3 Fibonacci(2) + 2 Fibonacci(1)
=3 (Fibonacci(1) + Fibonacci(0)) + 2 Fibonacci(1)
= 5 Fibonacci(1) + 3 Fibonacci(0)
=5
Department of Electronics And Electrical Engineering, IIT Guwahati
Recursion: Binary Search
Base Case: BS(a,x)
Recursion:
BS(a,i,j,x):
mid=(i+j)//2
if a[mid]==x:
return mid
else:
if a[mid]<x:
return BS(a,i,mid-1,x)
else:
return BS(a,mid+1,j,x)
Department of Electronics And Electrical Engineering, IIT Guwahati
Stack Overflow Error in Recursion
Recursion is implemented using stack as activation records are to be stored in LIFO order
If the base
case is
not not incorrectly
reached defined defined
Department of Electronics And Electrical Engineering, IIT Guwahati
Direct and Indirect Recursion
fun1
fun
fun2
Direct Indirect
Department of Electronics And Electrical Engineering, IIT Guwahati
Solving Recurrences
Substitution Method
Recurrence Tree Method
Master Method
Department of Electronics And Electrical Engineering, IIT Guwahati
Substitution Method
Form the recurrence relation
Use back substitution to reach
the base case
=
Advantage:
Solve any kind of recurrence relation
Disadvantage:
𝑂 (log 2 𝑛)
Sometimes complex derivation
Department of Electronics And Electrical Engineering, IIT Guwahati
Substitution Method
𝑂 (𝑛 !)
=
Department of Electronics And Electrical Engineering, IIT Guwahati
Recurrence Tree
No. of branches = No. of choices
Department of Electronics And Electrical Engineering, IIT Guwahati
Recurrence Tree Method
Consider the recurrence
𝑛
𝑛 8
𝑐𝑛 log 𝑛
4 𝑛
𝑛 8
2 𝑛
𝑛 8
4 𝑛
8
𝑛 𝑛
𝑛 8
𝑛
2
4 𝑛
8
𝑛
𝑂 ¿
𝑛 8
4 𝑛 Height of the tree
8
𝑐𝑛 𝑐𝑛 𝑐𝑛 𝑐𝑛 … 𝑐𝑛
Department of Electronics And Electrical Engineering, IIT Guwahati
Master Method
If the recurrence is of the form
= size of input data Solution is:
= number of subproblems in the recursion
= size of each subproblem depends on
= cost of the work done outside the recursive call
and are constants The relationship between and is
is an asymptotically positive function
Advantage:
Faster derivation
Disadvantage:
Only solves relations with specific form
Department of Electronics And Electrical Engineering, IIT Guwahati
Master Method
For example consider the recurrence
Solution is:
Department of Electronics And Electrical Engineering, IIT Guwahati
Master Method Limitations
The Master Theorem cannot be used if:
• is not monotone. e.g.
• is not a polynomial. e.g.
• is not a constant. e.g.
Department of Electronics And Electrical Engineering, IIT Guwahati
Randomized Algorithms
Department of Electronics And Electrical Engineering, IIT Guwahati
Randomized Algorithm
Randomized algorithm is a different design approach taken by the standard algorithms where
few random bits are added to a part of their logic.
They are different from deterministic algorithms.
Deterministic algorithms follow a definite procedure to get the same output every time an input
is passed whereas randomized algorithms produce a different output every time they're executed.
It is not the input that is randomized, but the logic of the standard algorithm.
Department of Electronics And Electrical Engineering, IIT Guwahati
Randomized Algorithm
Deterministic Algorithm Randomized Algorithm
Department of Electronics And Electrical Engineering, IIT Guwahati
Need for Randomized Algorithm
Randomized algorithms are useful because they can
improve efficiency,
handle complex problems,
avoid worst-case scenarios, and
are essential for cryptography.
Department of Electronics And Electrical Engineering, IIT Guwahati
Classification of Randomized Algorithms
Randomized algorithms are classified based on whether they have time
constraints as the random variable or deterministic values.
They are designed in their two common forms − Las Vegas and Monte Carlo.
Department of Electronics And Electrical Engineering, IIT Guwahati
Classification of Randomized Algorithms
Las Vegas
• The Las Vegas method never gives incorrect outputs, making the time constraint as the
random variable.
• For example, in string matching algorithms, Las Vegas algorithms start from the beginning
once they encounter an error.
• This increases the probability of correctness. e.g., Randomized Quick Sort Algorithm.
Monte Carlo
• The Monte Carlo method focuses on finishing the execution within the given time
constraint.
• Therefore, the running time of this method is deterministic.
• For example, in string matching, if Monte Carlo encounters an error, it restarts the
algorithm from the same point. Thus, saving time. e.g., Karger's Minimum Cut Algorithm
Department of Electronics And Electrical Engineering, IIT Guwahati
Randomized Quick Sort Algorithm
• Quicksort chooses a pivot element and sorts the input list around that pivot
element.
• Randomized quick sort is designed to decrease the chances of the algorithm
being executed in the worst case time complexity of .
• The worst case time complexity of quick sort arises when the input given is
an already sorted list.
• There are two ways to randomize the quicksort −
• Randomly shuffling the inputs: Randomization is done on the input list so that the
sorted input is jumbled again which reduces the time complexity. However, this is
not usually performed in the randomized quick sort.
• Randomly choosing the pivot element: Making the pivot element a random variable
is commonly used method in the randomized quick sort. Here, even if the input is
sorted, the pivot is chosen randomly so the worst case time complexity is avoided.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
• The Kargers algorithm merges any two nodes in the graph into one node which is known
as a supernode.
• The edge between the two nodes is contracted and the other edges connecting other
adjacent vertices can be attached to the supernode.
Algorithm
• Step 1 − Choose any random edge [u, v] from the graph G to be contracted.
• Step 2 − Merge the vertices to form a supernode and connect the edges of the other
adjacent nodes of the vertices to the supernode formed. Remove the self nodes, if any.
• Step 3 − Repeat the process until theres only two nodes left in the contracted graph.
• Step 4 − The edges connecting these two nodes are the minimum cut edges.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
Step 1 − Choose any edge, say A → B, and contract the edge by
merging the two vertices into one supernode. Connect the
adjacent vertex edges to the supernode. Remove the self loops,
if any.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
Step 2 − Contract another edge (A, B) → C, so the supernode
will become (A, B, C) and the adjacent edges are connected to
the newly formed bigger supernode.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
Step 3 − The node D only has one edge connected to the
supernode and one adjacent edge so it will be easier to contract
and connect the adjacent edge to the new supernode formed.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
Step 4 − Among F and E vertices, F is more strongly bonded to
the supernode, so the edges connecting F and (A, B, C, D) are
contracted.
Department of Electronics And Electrical Engineering, IIT Guwahati
Kargers Minimum Cut Algorithm
Step 5 − Since there are only two nodes present in the graph, the
number of edges are the final minimum cut of the graph. In this
case, the minimum cut of given graph is 2.
Department of Electronics And Electrical Engineering, IIT Guwahati
Zero-sum Game
The zero-sum game is a mathematical representation of the game theory.
It has two players where the result is a gain for one player while it is an equivalent loss to the other player.
So, the net improvement is the sum of both players status which sums up to zero.
Randomized algorithms are based on the zero-sum game of designing an algorithm that gives lowest time
complexity for all inputs.
There are two players in the game; one designs the algorithm and the opponent provides with inputs for the
algorithm.
The player two needs to give the input in such a way that it will yield the worst time complexity for them to win
the game.
Whereas, the player one needs to design an algorithm that takes minimum time to execute any input given.
Department of Electronics And Electrical Engineering, IIT Guwahati
Pseudo-random Number Generator
Q: Can a computer generate a truly random number?
A: Since computers have no imagination whatsoever, it is physically
impossible for them to come up with a truly random number.
If you use built-in functions to randomize a number, it will produce a
pseudo-random number using a complex algorithm.
Q: How to get a pure random number?
A: Input from some real-world random phenomenon, such as sensors.
Department of Electronics And Electrical Engineering, IIT Guwahati
Methods
Linear Congruential
Generator (LCG)
Methods Middle Squared
Multiply-With-Carry
(MWC)
Department of Electronics And Electrical Engineering, IIT Guwahati
Pseudo-random Number Generator
Linear Congruential Generator (LCG)
Uses a linear recurrence equation of the form:
Seed =34
,,
Department of Electronics And Electrical Engineering, IIT Guwahati
Pseudo-random Number Generator
Middle Square method
Suppose, we want to generate a two digit random sequence.
Input a 2-digit seed number: e.g., 34
2
34 34 =1 15 6
2
15 15 =0 22 5
2
22 22 =0 48 4
48
Department of Electronics And Electrical Engineering, IIT Guwahati
Pseudo-random Number Generator
Multiply-With-Carry method
Uses a linear recurrence equation of the form:
Typically
Let 4525 and a seed of 1234, i.e., .
Department of Electronics And Electrical Engineering, IIT Guwahati