Algorithms (CS-5101)
Introduction
• Instructor:
– Dr. Sourav Kumar Dandapat(sourav@[Link])
– Dr. Abyayananda Maiti (abyaym@[Link])
• TA:
– Md Tauseef Alam(tauseef_2121cs04@[Link])
– Srishti Gupta(srishti_2021cs38@[Link])
• Course Homepage:
– [Link]
• Class Timing:
– Monday (11am – 12pm)
– Tuesday (11am – 12 pm)
– Thursday(9am-10am)
– Thursday (11 am – 12 pm)(T)
Evaluation breakup
• End Sem: 40
• Mid Sem: 30
• Class performance (30)
– Best of two quizzes before mid-sem (15)
• 1st quiz: 22/08/24
• 2nd quiz: 17/09/24
• Best of two quizzes after mid-sem(15)
– Schedule of 3rd and 4th quiz will be announced
after mid-sem
Regarding course structure
• Recursion
– Divide and Conquer
– Backtracking
– Recurrence Solving
• Graph algorithms
• Hardness of the problems – NP
• Optimization techniques: linear programming
• Fibonacci heap, unionfind, splay trees.
• Amortized complexity analysis
• Randomized algorithms
• Branch and bound
• Approximation algorithms
• Geometric algorithms
• Algebraic and number-theoretic algorithms
Introduction to Algorithm
• What is algorithm:
– Set of steps for performing a particular task.
• Specification:
– Must have unambiguous and well defined input and
output.
• Desired Feature:
– Correctness, Termination, Efficiency
Design of Algorithm
• Understand the problem and try to explore
solution space.
• What is solution space?
• It is set of all feasible solutions
• Compare the solution space in terms of
efficiency and choose the right solution
Finding minimum element in
unordered list
• Specification:
– Input: L={l1,l2,…,ln} li ∈ Integers
– Output: s ∈ L and s <= li ∀ li ∈ L
• Approach:
• We can think about a tournament, where n teams (a
team corresponds to one number in input list)
participated and a team wins a game played between
two teams if it holds smaller number. That means if there
is a game between x and y then x will win if x is less than
or equal to y otherwise y will win.
• So we have to design a tournament to find out the
winner.
• Tournament can be organized in number of ways.
• we will create two groups where first group
consists of (Team1, …, Team K) and second group
consists of (Team K+1, …, Team n)
• Now depending on the value of 1<=k<n many
different strategies are possible to organize the
tournament. Different strategies will form the
solution space.
• However, all strategies will lead us to decide
winner of the tournament.
A recursive Solution
• Approach: Split the list into two sub-lists say L1 and
L2(of smaller size). Find the winner (minimum) of L1
and L2 in similar way. Then arrange a game between
winner of L1 and L2 (combine the solution obtained
from L1 and L2) to get final winner (solution) of L.
• It is a recursive definition of finding minimum.
• Are we missing anything?
• We are missing base condition.
• What is base condition?
• Progress towards base is needed.
• FindMinimum(Integer List L)
– if |L| <= 1:
• if |L| == 0 Print error message; exit;
• if |L| == 1 return (L[0]);
– else
• Split L into L1 and L2
• x1=FindMinimum(L1)
• x2=FindMinimum(L2)
• If(x1 <x2) return x1
• else return x2;
How should we split the list?
• We can split a list in a number of ways
• Will it affect correctness?
• Will it affect termination?
• Will it affect efficiency?
Impact of split size on efficiency
8 1
1 7 1
1:n-1(split strategy)
Total Cost(number
1 6 1 of comparisons) = 7
1 5 1
1 4 1
1 3 1
1 2 1
1 1
Impact of split size on efficiency
8 1
2 1 6 1 2:n-2 (split Strategy)
Total Cost = 7
2 1 4 1
1 1
2 1 2 1
1 1
1 1 1 1
Impact of split size on efficiency
8 1
3 1 5 1 3:n-3
Total Cost = 7
3 1 2 1
1 2 1
2 1 1 1
1 1
1
1 1
Impact of split size on efficiency
8 1
4 1
4 1 4,n-4
Total Cost = 7
2 1 2 1 2 1 2 1
1 1 1 1 1 1 1 1
Cost Analysis
T(1)=0
T(n)= 1+T(n-1)
T(8)=1+T(7)=1+1+T(6)=3+T(5)=4+T(4)=7+T(1)=7=
n-1
T(n) = T(n/2)+T(n-n/2)+1
T(8) =T(4)+T(4)+1 = 2(2T(2)+1)+1=4(2T(1)+1)+3=7=n-1
T(n) = O(n)
What Can We Conclude?
Searching element in a ordered integer list
• Approach: Split the list L into two sub-lists say L1 and
L2 (of smaller size). Search element q in L1 and L2 in
similar way. Then combine the result to obtain the
result of searching q in list L.
• We missed to mention base condition, split size
• Search(Integer List L, integer q)
• if |L| == 0 print error message and exit
• if |L|== 1
– if L[0] == q then return True;
– else return False;
• else split L (k:n-k) into L1 and L2
x1= Search(L1,q)
x2=Search(L2,q)
If (x1==True || x2 == True) return True;
• Correctness?
• Termination?
• Efficiency?
Do we really need to check both sub-lists?
• Search(Integer List L, integer q)
• if |L| == 0 print error message and exit
• if |L|== 1
– if L[0] == q then return True;
– else return False;
• else
– Find some k for splitting
– split L into L1(0,k-1) and L2(k,n-1)
– If L1[k-1]<=q return Search(L1,q);
– else return Search(L2,q)
Does all the split cost same?
Impact of split size on efficiency
8 1
1 1 7 1
K=1
WorstCost = 8
1 1 6 1
1 1 5 1
1 1 4 1
1 1 3 1
1 1 2 1
1 1 1 1
Impact of split size on efficiency
8 1
2 1 6 1 K=2
Worst Cost = 5
1 2 1 1
1 1 4
1
1 1 1 2 1 2 1
1
1 1 1 1 1 1
1 1
Impact of split size on efficiency
8 1
5 1 K=3
3 1
WorstCost = 5
3 1 2 1
2 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
Impact of split size on efficiency
8 1
4 1
4 1 Worst Cost = 4
2 1 2 1 2 1 2 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1
Cost Analysis
• T(1)=1
• T(n)=T(n/2)+1=T(n/4)+2=T(n/2i)+i
• n/2i=1 => i=log2n
• T(n)=T(1)+log2n=1+log2n = O(log2n)
Homework
• Given a list L of n unordered integers. You are asked
to find out minimum as well as maximum of n
elements. Analyze the cost of your algorithm in
terms of number of comparison made.