GATE CSE 1993 | Question: 12

Question

The following Pascal program segments finds the largest number in a two-dimensional integer array $A[0\dots n-1, 0\dots n-1]$ using a single loop. Fill up the boxes to complete the program and write against $\fbox{A}, \fbox{B}, \fbox{C} \text{ and } \fbox{D}$ in your answer book Assume that max is a variable to store the largest value and $i, j$ are the indices to the array.

begin
    max:=|A|, i:=0, j:=0;
    while |B| do
    begin
        if A[i, j]>max then max:=A[i, j];
        if |C| then j:=j+1;
        else begin
            j:=0;
            i:=|D|
        end
    end
end

Comments

Have you got the answer to this?? Because I am unable to detect max if it is @ A[0,1]

If you found the answer, kindly post it here. Thanks.

Answer 1

We have to traverse all elements in array. The code is doing this row wise. 

begin
    max:=A[0,0], i:=0, j:=0;
    while (i < n) do
    begin
        if A[i, j]>max then max:=A[i, j];
        if (j < n-1) then j:=j+1;
        else begin
            j:=0;
            i:=i++;
        end
    end
end

Comments

Arjun sir, just small correction for shake of accuracy, In if condition we need to check for j<n-1 otherwise it will go out of bound.

---

As we are acheving this answer using one loop. So this complexity of this code is O(n) ?

But still we willl be accessing n^2 elements. Any comment plz?

---

For loop is still running for n^2 times. Number of loops doesn't matter if it's running constant number of times, but if you have a single Loop running for n^2 or n^3 it matters.

---

I think (C) should be : j<n instead of j<n-1.

Please explain why it is n-1

---

@Ayush.

j will be incremented till n-1. So last time when j=n-2 , increment happens and it becomes n-1.

---

nice explanation @Arjun sir

---

if we put in place of A max=-1 then also code will work same.

---

Correct. Even in case of max = 0 it will work the same. Since, negative number representation has an overhead, 0 is better. Either is better than A[0,0] as that saves from additional reading of [0,0] element. That element is being read first time in the loop anyway.

---

We can do max=INT_MIN also right ?

---

i:=i++;

The above statement causes undefined behaviour in C. Isn’t this a problem in Pascal?

---

Don’t put INT_MIN in place of |A| because typical values in a compiler where integers are stored using 32 bits Value of INT_MIN is -2147483648. If all the input values are less than this value then your code will give the wrong answer and it will be INT_MIN. You can  put |D| = i+1.

Answer 2

A:=A[0,0]    B:=(i<n)    C:=(j<n-1)   D:=i++

Comments

Should'nt j be j<n instead of j<n-1?

---

No, j shouldn't be j<n; rather it must be j<n-1.

Reason : j should be incremented(i.e. j++) so that we reach till n-1(last element in the row), after which we should make j=0(first element in the next row since i++).

Answer 3

For the given question we are given an nxn 2D array:

We're trying to fing the max element in the given code. Let's analyze each part A, B, C and D part by part.

Part A: max := ?

We need to set a value for Max, such that the value will be compared to each and every element in the array and if the current value is larger than the Max value then we'd update the current value to be the max value, in this way we shall get the Maximum value of the array after traversing the whole array. 

1)We can set the max value to be the first value of the array as it would be compared to all the element in the array, i.e., 

A[0][0]

[ WRONG:  Setting the max value to be 0. Because if we are given an array with all negative elements then we'd get wrong answer. ]

Part B, C and D : 

while |B| do
    begin
        if A[i, j]>max then max:=A[i, j];
        if |C| then j:=j+1;
        else begin
            j:=0;
            i:=|D|

            inside the while loop we are comparing the current and max value as discussed earlier. By traversing 'i' we are skipping columns and traversing in the row and by traversing 'j' we are skipping rows and traversing in the coulmns(NOTE: In the row-major ordering we wont directly rows unless columns are over.) 

Part B would be the condition checking for traversing by the rows, hence i<n 

Part C would be the condidtion to check for gooing to the next element until j<n

Part D is the else condition when j exceeds n-1, there we would set j=0 and then go to the next row by i = i+1