-
Notifications
You must be signed in to change notification settings - Fork 0
/
qusn 10.txt
157 lines (114 loc) · 4.04 KB
/
qusn 10.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
MCA 301 : Design and analysis of Algorithms
Assignment : 3
Promlem statement : 10
--------------------
Programming Approach
--------------------
1. Greedy
2. Iterative
-----------
EXPLANATION
-----------
Global variables
----------------
- adj_matrix : a boolean 2D matrix, where value at adj_matrix[x][y] states whether person x knows person y. True, if yes. False, if no.
- isPotenital : a boolean array, where value at isPotenital[i] states whether a person i can considered for invititation. True, if yes.
False, if no.
======================================================================================================================
--------------------------------------
Function 1: count(size, person_x)
--------------------------------------
**********
Pseudocode
**********
count(size, person_x)
1. cnt = 0;
2. for i = 1 to size
3. if isPotential[i] == true and adj_matrix[i][person_x]
4. cnt = cnt + 1
5. return cnt
/*
Description
-----------
Objective :This function calculates number of people that a person_x knows.
Input variables
- size : size of array isPotenital
- person_x : person for which number of his/her acquaintance has to be calculated
Return value :# person_x knows
*/
======================================================================================================================
-------------------------
Function 2: plan_party(n)
-------------------------
**********
Pseudocode
**********
plan_party(n):
1. potential_count = n;
2. for j = 1 to n
3. known = count(n,j);
4. unknown = potential_count - known - 1;
5. if isPotential[j] and (known < 5 or unknown < 5)
6. isPotential[j] = false
7. potential_count = potential_count - 1
8. j = 0
9. if potential_count < 11
10. for i = 1 to n
11. isPotential[i] = false
12. break
Description
-----------
/*
Objective :
This function computes all persons who can be invited for a party out of n people based on following conditions:
1. Every person invited should know at least five other people that are invited.
2. Every person invited should not know at least five other people that are invited.
3. Number of invitees is maximized
Input variable
- n : Number of people to choose from
Return value : None
*/
======================================================================================================================
-----------------------------
Function 3: invitees(n)
-----------------------------
**********
Pseudocode
**********
invitees(n):
1. cnt = 0
2. for i = 1 to n
3. if isPotential[i] == true
4. print i
5. cnt = cnt + 1
6. print cnt
Description
-----------
/*
Objective :This function print the final invitees and the count of invitees.
Input Variables : n -number of people
Return : None
*/
======================================================================================================================
----------
Complexity
----------
Function 1:
line 1 -> O(1)
loop 2-4 -> O(n) linear time
line 5 -> O(1)
--------------------------------------------------
Function 2:
line 1 -> O(1)
line 2 -> j iterates from 1 to n,
line 3 -> O(n) it makes a call to countknown in every iteration
line 4 -> O(1)
line 5 -> if the condition in this line is satisfied, the value of j is again set to 1.
which implies there will be more than n iterations in line 2. In worst case value of j is set to 1 by every value of j,
therefore the main loop runs atmost n^2 times.
line 6-8 -> O(1)
line 9 -> if this condition is true, we will come out of the main loop. and line 10-11 will iterate n times but only once, hence it will not effect the degree of time complexity
--------------------------------------------------
Since, countknown is called atmost n^2 time.
Time complexity = O(n^3)
Space complexity = O(n^2)