Celebrity Problem.pdf

In this following presentation, one can get an idea for solving a common celebrity problem. It has general algorithm along with pseudocode, the code and the methods of solving it. It also discusses the time complexity in each step for better graphical representation.

1. THE
CELEBRITY
PROBLEM
Presented By: Group 1
IpsitaRaha–DibyenduBanik–Arnab Chatterjee –ArijitDhali
11500120054 –11500320062 –11500320076 –11500320078
SOLVING BY GRAPHICAL METHOD

2. TABLE OF CONTENTS
Disscussing Problem
& Strategy
01
Graphical
Approach
02
Pseudocode &
Algorithm
03
Complexity Analysis
& Result analysis
04
Program Code &
Other Approaches
05
Conclusion &
References
06

3. CELEBRITY
PROBLEM
Acelebrityamongagroupofnpeopleisa
personwhoknowsnobodybutisknown
byeverybodyelse.Thetaskistoidentifya
celebritybyonlyaskingquestionsto
peopleofthefollowingform:“Doyou
knowthisperson?

4. STRATEGY
00100
00100
00000
00100
00100
0
1
2
3
4
01234Person
Let us understand the solution using two sample cases where we consider a matrix of person [i, j ]
(for person iknows j or not)
Hence, 2 is the Celebrity here
Case 1:
00100
00100
01000
00100
00100
0
1
2
3
4
01234Person
Case 2:
Hence, there is no celebrity here
From these examples,
We can conclude the conditions :
•Condition 1:
Every other person knows the celebrity
•Condition 2:
Celebrity doesn’t knows no other person

5. 01
GRAPHICAL
APPROACH
●Modelthesolutionusinggraphs
●Initializeindegreeandoutdegreeofeveryvertexas0.
●IfAknowsB,drawadirectededgefromAtoB,increase
indegreeofBandoutdegreeofAby1.
●Constructallpossibleedgesofthegraphforeverypossible
pair[i,j].
●Nowthereare
n
C
2pairs.
●Foratleast1celebritypresentintheparty,therewillbeone
sinknodeinthegraphwithoutdegreeofzeroandindegree
ofN-1

6. PSEUDOCODE
1.Create two arraysindegreeandoutdegree, to store the indegree and outdegree
2.Run a nested loop, the outer loop from 0 to n and inner loop from 0 to n.
3.For every pair i, j check if iknows j then increase the outdegree of iand indegree of j
4.For every pair i, j check if j knows ithen increase the outdegree of j and indegree of i
5.Run a loop from 0 to n and find the id where the indegree is n-1 and outdegree is 0

7. ALGORITHM WITH TIME COMPLEXITY
findCelebrity (n):
indegree -> [0 for x from 0 to n]
outdegree -> [0 for x from 0 to n]
for i<-0 to n -1
for j <-0 to n -1
x = knows( i, j )
outdegree[ i] + = x
indegree[ j ] + = x
for i<-0 to n -1
if indegree[ i] = n -1 and outdegree[ i] = 0
return i
return -1
Cost Times
C
1
nC
2
C
3
C
4
෍
??????=0
??????−1
??????
??????
C
5
C
6
C
7
C
8
nC
9
C
10
C
11
1

8. CONTINUATION
knows(a, b):
return MATRIX[ a ][ b ]
Main:
id <-findCelebrity(n)
if id = -1:
No celebrity
else
Celebrity Present, print id
Cost Times
C
12 1
Here,t
jisthenumberoftimesthewhileloopisexecuted.
Also,MATRIX=[[0,0,1,0], andN=4(Personinparty)
[0,0,1,0],
[0,0,0,0],
[0,0,1,0]]
Cost Times
C
13 1
C
14
1
C
15
C
16
1
C
17

9. COMPLEXITY ANALYSIS
●Time Complexity : O(n
2
)
A nested loop is run traversing the array, SO the
time complexity is O(n
2
)
= (C
1+C
2+C
3+C
8+C
9+C
10)(n) + (C
4+C
5+C
6+C
7)(n
2
) +
C
11 + C
12 + C
13 + C
14 + C
15 + C
16+ C
17
= O(n
2
)
●Space Complexity: O(n)
Since extra space of size n is required.

10. RESULT ANALYSIS 1
Let us consider the previous case 1, and create tables for
indegree and outdegree
00100
00100
00000
00100
00100
0
1
2
3
4
01234Person
IndegreeOutdegree
0 0 0
1 0 0
2 0 0
3 0 0
4 0 0
1
12
1
1
3
1
4
In this table we can see, person 2 has
Indegree = 4 = (5 –1) or (n –1)
Outdegree = 0
∴Person 2 is the celebrity

11. RESULT ANALYSIS 2
Let us consider the previous case 2, and create tables for
indegree and outdegree
IndegreeOutdegree
0 0 0
1 0 0
2 0 0
3 0 0
4 0 0
1
12
1
1
3
1
4
In this table we can see, person 2 has
Indegree = 5 ≠(5 –1) or (n –1)
Outdegree = 1
∴Returns -1 which means no celebrity
00100
00100
01000
00100
00100
0
1
2
3
4
01234Person 1
1

12. PROGRAM
CODE

13. OTHER APPROACHES
02
RECURSIVE
APPROACH
03
STACKING
APPROACH

14. CONCLUSION
Inthistermpaperwesolvedthegivenproblemusing
graphicalmethod.
Forgraphstobecomputationallyuseful,theyhavetobe
convenientlyrepresentedinprograms.
Howeveritissimpletoimplement,easyandfasttotellif
apair(i,j)isanedge:simplycheckifA[i][j]is1or0.
Nomatterhowfewedgesthegraphhas,thematrixtakes
O(n
2
)inmemory

15. References
●https://www.geeksforgeeks.org/the-celebrity-problem/
●https://tutorialspoint.dev/data-structure/stack-data-structure/the-celebrity-problem
●https://www.youtube.com/watch?v=aENYremq77I&list=LL

16. CREDITS: This presentation template was created bySlidesgo,
including icons by Flaticon, infographics & images by Freepik
THANK
YOU
For your kind attention towards our
presentation
Group 1