-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathproblem1.html
54 lines (54 loc) · 3.09 KB
/
problem1.html
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
<!DOCTYPE html>
<html>
<head>
<title> Problem 1 - SmartLAB Recruitment Drive </title>
</head>
<script language=JavaScript> var message="Function Disabled!"; function clickIE4(){ if (event.button==2){ alert(message); return false; } } function clickNS4(e){ if (document.layers||document.getElementById&&!document.all){ if (e.which==2||e.which==3){ alert(message); return false; } } } if (document.layers){ document.captureEvents(Event.MOUSEDOWN); document.onmousedown=clickNS4; } else if (document.all&&!document.getElementById){ document.onmousedown=clickIE4; } document.oncontextmenu=new Function("alert(message);return false") </script>
<body bgcolor="#FFFFFF" ondragstart="return false" onselectstart="return false">
<p> <h4>PSUEDO - CODE </h4> </p>
X[1..N] is a set of positive integers. (array)
<br><br>
PROCEDURE( X[1..N] ):<br>
     Step[1] -<br>
         j = 1<br>
         k = N - 1<br>
         m = X[N]<br>
         goto Step[2]<br><br>
     Step[2] - <br>
         if k is 0<br>
             terminate<br>
         else<br>
             goto Step[3]<br><br>
     Step[3] -<br>
         if X[k] <= m<br>
             goto Step[5]<br>
         else<br>
             goto Step[4]<br><br>
     Step[4] -<br>
         j = k<br>
         m = X[k]<br>
         goto Step[5]<br><br>
     Step[5] - <br>
         k = k-1<br>
         goto Step[2]<br>
<hr>
<p>
<h4> Answer the following questions with regard to the above pseudo-code</h4>
</p>
<p>
<ol>
<li> Justify why this procedure will always terminate in finite number of steps. </li>
<li> What is the output produced by the above procedure? </li>
<li> Write down the number of times each step will be executed as a function of N. </li>
<li> Provide a test case for which the algorithm will execute for: (a)Maximum number of steps (b)Minimum number of steps </li>
<li> Assuming that the input X[1..N] is some permutation of the set {1..N}, find out the average number of times Step 4 is executed. [Hint: Each permutation of {1..N} is equally probable] </li>
<li> Does the answer for Q5 change, if X[1..N] is allowed to take any N distinct integer values ? </li>
<li> Implement the code for the above given procedure in your preferred programming language. </li>
</ol>
</p>
<hr>
<p> This question carries 15 marks </p><br>
<a href="problem2.html">Next</a><br>
<a href="index.html">Home</a>
</body>
</html>