The following Pascal program segments finds the largest number in a two-dimensional integer array A[0...n-1,0...n-1] using a single loop. Fill up the boxes to complete the program and write against 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:= , i:=0,j:=0;
     while  do
           begin
           if A[i,j]>max then max:=A[i,j]
           if  then j:=j+1
           else begin
                 j:=0;
                 i:= 
           end
     end
 end.

Program PARAM (input, output);
 var m, n : integer;
 procedure P (var, x, y : integer);
    var m : integer;
    begin
      m : = 1;
      x : = y + 1
    end;
 procedure Q (x:integer; vary : integer);
    begin
      x:=y+1;
    end;
 begin
    m:=0; P(m,m); write (m);
    n:=0; Q(n*1,n); write (n)
 end 

The value of n, output by the program PARAM is:

Program PARAM (input, output);
 var m, n : integer;
 procedure P (var, x, y : integer);
    var m : integer;
    begin
      m : = 1;
      x : = y + 1
    end;
 procedure Q (x:integer; vary : integer);
    begin
      x:=y+1;
    end;
 begin
    m:=0; P(m,m); write (m);
    n:=0; Q(n*1,n); write (n)
 end 

What is the scope of m declared in the main program?

What does the following code do?

 var a, b : integer;
 begin
    a:=a+b;
    b:=a-b;
    a:=a-b
 end; 

Program PARAM (input, output);
 var m, n : integer;
 procedure P (var, x, y : integer);
    var m : integer;
    begin
      m : = 1;
      x : = y + 1
    end;
 procedure Q (x:integer; vary : integer);
    begin
      x:=y+1;
    end;
 begin
    m:=0; P(m,m); write (m);
    n:=0; Q(n*1,n); write (n)
 end 

The value of m, output by the program PARAM is:

An array a contains n integers in non-decreasing order, A[1] ≤ A[2] ≤ ... ≤ A[n]. Describe, using Pascal like pseudo code, a linear time algorithm to find i, j, such that A[i] + A[j] = a given integer M, if such i, j exist.

(a) Draw a precedence graph for the following sequential code. The statements are numbered from S₁ to S₆

 S1       read n
 S2       i:=1
 S3       if i>n goto next
 S4       a(i):=i+1
 S5       i:=i+1
 S6       next : Write a(i) 

(b) Can this graph be converted to a concurrent program using parbegin-parend construct only?

Consider the program below:

 Program main;
    var r:integer;
    procedure two;
    begin write (r) end;
    procedure one;
    var r:integer;
    begin r:=5 two; end
    begin r:=2;
    two; one; two;
    end. 

What is printed by the above program if
(i) Static scoping is assumed for all variables;
(ii) Dynamic scoping is assumed for all variables.
Give reasons for your answer.

What function of x, n is computed by this program?

 Function what (x, n:integer): integer:
 Var
     value : integer;
     begin
     value:=1
     if n>0 then
 begin
     if n mod 2 = 1 then
     value:=value*x;
     value:=value*what(x*x, n div 2);
     end;
     what:value
     end; 

The following is an incomplete Pascal function to convert a given decimal integer (in the range -8 to +7) into a binary integer in 2’s complement representation. Determine the expression A, B, C that complete program.

 function TWOSCOMP (N:integer):integer;
 var
 RAM, EXPONENT:integer;
 BINARY :integer;
 begin
 if(N>=-8) and (N<=+7) then
     begin
 if N<0 then
     N : = A;
 BINARY:=0;
 EXPONENT:=1;
 while N<>0 do
     begin
       REM:=N mod 2;
       BINARY:=BINARY + B*EXPONENT;
       EXPONENT:=EXPONENT*10;
       N := C
     end
 TWOSCOMP:=BINARY
 end
 end; 

(a) Using the scope rules of Pascal determine the declaration that apply to each occurrence of the names A and B in the following program segment.

 procedure T(U, V, X, Y: integer);
 var
    A: record
        A, B : integer
    end; 
    B: record
        B, A : integer
    end;
 begin
    with A do
        begin
          A:=4;
          B:=V
 end;
 with B do
    begin
         A:=X;
         B:=Y
    end
 end; 

(b) Find the lexical errors in the following Pascal statement:

     if A > 1, then B = 2.5A else read (C);  

Consider the following high level program segment. Give the contents of the memory locations for variables W, X, Y and Z after the execution of the program segment. The values of the variables A and B are 5 CH and 92H, respectively. Also indicate error conditions if any.

 var
     A, B, W, X, Y   :unsigned byte;
     Z               :unsigned integer, (each integer is represented by two bytes)
 begin
     X               :=A+B
     Y               :=abs(bA-b);
     W               :=A-B
     Z               :=A*B
 End;  

(a) Consider the following Pascal function where A and B are non-zero positive integers. What is the value of GET(3,2)?

 function GET(A,B:integer);integer;
 begin
          if B = 0 then
    GET:=1
 else if A < B then
    GET:=0
 else
    GET:=GET(A-1,B)+GET(A-1,B-1)
 end ; 

(b) The Pascal procedure given for computing the transpose of an N × N (N>1) matrix A of integers has an error. Find the error and correct it.
Assume that the following declaration are made in the main program

 const
     MAXSIZE=20;
 type
     INTARR=array [1.,MAXSIZE,1..MAXSIZE] of integer;
 Procedure TRANSPOSE (var A: INTARR; N : integer);
 var
     I, J, TMP, integer;
 begin
     for I:=1 to NO – 1 do
     for J:=1 to N do
     begin
          TMP: = A[I,J];
          A[I,J]:=A[J,I];
          A(J,I):=TMP
     end
 end; 

A variant record in Pascal is defined by

                    type varirec      =   record
                                          number : integer;
                                          case (var1,var2) of
                                          var1: (x,y : integer);
                                          var2: (p.q.: real)
                        end
                    end   

Suppose an array of 100 records was declared on a machine which uses 4 bytes for an integer and 8 bytes for a real. How much space would the compiler have to reserve for the array?

What is the value of X printed by the following program?

 program COMPUTE (input, output);
    var
                  X:integer;
    procedure FIND (X:real);
                  begin
                  X:=sqrt(X);
                  end;
   begin
                  X:=2
                  Find(X)
                  Writeln(X)
   end 

Assume that X and Y are non-zero positive integers. What does the following Pascal program segment do?

 while X <>Y do
 if X > Y then
    X := X – Y
 else
    Y := Y – X;
 write(X); 

Which of the following strings can definitely be said to be tokens without looking at the next input character while compiling a Pascal program?

 I. begin           II. program           III. <>   

In the following Pascal program segment, what is the value of X after the execution of the program segment?
X:=-10; Y:=20;
If X > Y then if X < 0 then X:=abs(X) else X:=2*X;

Consider the following C functions.

  int fun1 (int n)  {                              int fun2 (int n)  {
    static int i = 0;                                static int i = 0;  
    if (n > 0)  {                                    if (n > 0)  { 
       ++i;                                              i = i + fun1 (n);   
       fun1 (n-1);                                       fun2 (n-1);
    }                                                 }
    return (i);                                           return (i);
  }                                                 } 

The return value of fun2 (5) is _______.

Given the following Pascal-like program segment

Procedure A;
  x,y: integer;
   Procedure B;
    x,z: real
    S1
   end B;
   Procedure C;
      i: integer;
       S2
   end C;
end A; 

The variables accessible in S1 and S2 are

What value would the following function return for the input x=95?

                 Function fun (x:integer):integer;
      Begin
                 If x > 100 then fun = x - 10
                 Else fun = fun(fun(x + 11))
      End;  

What is the result of the following program?

program side-effect (input, output);
    var x, result: integer;
    function f (var x:integer):integer;
    begin
        x:x+1;f:=x;
    end;
begin
    x:=5;
    result:=f(x)*f(x);
    writeln(result);
end; 

Consider the following pascal program skeleton:

                        var a,x,...;
                        procedure readarray;
                              var i,....;
                              begin
                                             ...:=a...
                              end;
      procedure exchange(...);
                       begin
                                             ...:=a...
                                             ...:=x...
                       end;
      procedure qsort(...);
                       var k,v,...;
                       function partition (...)...;
                              var i,j,...;
                              begin
                              ...:=a...
                              ...:=v...
                              end;
                       begin
                              .
                              .
                       end;
      begin
                       .
                       .
      end; 

Assume that at a given point in time during program execution, following procedures are active: sort, qsort(1,9), qsort(1.3), partition(1,3), exchange(1,3).

Show snapshots of the runtime stack with access links after each of the activations.

What will be the output of the following program assuming that parameter passing is

(i) call by value
(ii) call by reference
(iii) call by copy restore

      procedure P{x, y, z};
                        begin y:y+1; z: x+x end; 
      begin
                        a:= b:= 3;
                        P(a+b, a, a);
                        Print(a) 
      end. 

Suppose we have a function HALTS which when applied to any arbitrary function f and its arguments will say TRUE if function f terminates for those arguments and FALSE otherwise. Example, Given the following function definition.
FACTORIAL (N) = IF(N=0) THEN 1 ELSE N*FACTORIAL (N-1)
Then HALTS(FACTORIAL 4) = TRUE and HATS(FACTORIAL - 5) = FALSE

Let us define the function FUNNY(f) = IF HALTS(ff) THEN not(ff) ELSE TRUE
(a) Show that FUNNY terminates for all functions f.
(b) Use (a) to prove (by contradiction) that it is not possible to have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.

Consider the following C function definition.

int Trial (int a, int b, int c)
{
    if ((a >= b) && (c < b) return b;
    else if (a >= b) return Trial(a, c, b);
    else return Trial(b, a, c);
} 

The function Trial:

Given the programming constructs (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to (v) arbitrary go to (vi) non-recursive procedure call (vii) recursive procedure/function call (viii) repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language.

Consider the following program is pseudo-Pascal syntax.

    program main;
       var x: integer;
       procedure Q [z:integer);
       begin
          z: z + x;
          writeln(z)
       end;
    procedure P (y:integer);
          var x: integer;
       begin
          x: y + 2;
          Q(x);
          writeln(x)
       end;
       begin 
          x:=5;
          P(x);
          Q(x);
          writeln(x)
       end. 

What is the output of the program, when
(a) The parameter passing mechanism is call-by-value and the scope rule is static scooping?

(b) The parameter passing mechanism is call-by-reference and the scope rule is dynamic scooping?

The value of j at the end of the execution of the following C program.

int incr(int i)
{
   static int count = 0;
   count = count + i;
   return (count);
}
main()
{
   int i,j;
   for (i = 0; i <= 4; i++)
      j = incr(i);
} 

is

The following C declarations

struct node
{
   int i;
   float j;
};
struct node *s[10]; 

define s to be

The most appropriate matching for the following pairs

    X: m=malloc(5); m= NULL;        1: using dangling pointers
    Y: free(n); n->value=5;         2: using uninitialized pointers
    Z: char *p; *p = ’a’;           3. lost memory  

is:

Aliasing in the context of programming languages refers to

Consider the following C declaration

struct {
    short s [5]
    union {
    float y;
    long z;
    } u;
} t; 

Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is

Consider the following C program:

           void abc(char*s)
           {
              if(s[0]==’\0’)return;
              abc(s+1);
              abc(s+1);
              printf(“%c”,s[0]);
           }
           main()
           {  abc(“123”)
           }  

(a) What will be the output of the program?
(b) If abc(s) is called with a null-terminated string s of length n characters (not counting the null (‘\0’) character), how many characters will be printed by abc(s)?

Consider the following program

                Program P2 
                   var n: int: 
                   procedure W(var x: int) 
                   begin 
                          x=x+1; 
                          print x;   
                   end 

                procedure D 
                begin  
                          var n: int; 
                          n=3; 
                          W(n);  
                End 
            begin               //beginP2 
                n=10; 
                D; 
            end  

If the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?

What is printed by the print statements in the program P1 assuming call by reference parameter passing?

Program P1()
{
   x = 10;
   y = 3;
   func1(y,x,x);
   print x;
   print y;
}
func1(x,y,z)
{
   y = y+4;
   z = x+y+z;
} 

In the C language

Consider the following program written in pseudo-code. Assume that x and y are integers.

Count (x, y)  {
    if (y != 1)  {
        if (x != 1)  {
            print("*") ;
            Count (x/2, y) ;
        }
        else  {
             y = y - 1 ; 
             Count (1024, y) ; 
        }
    }
}

The number of times that the print statement is executed by the call Count(1024, 1024) is ______.

Consider the following C code. Assume that unsigned long int type length is 64 bits.

        unsigned long int fun(unsigned long int n)  { 
            unsigned long int i, j, j=0, sum = 0; 
            for (i = n; i > 1; i = i/2) j++; 
            for ( ; j > 1; j = j/2) sum++; 
            return sum; 
        } 

The value returned when we call fun with the input 2⁴⁰ is

Consider the following C program:

#include<stdio.h> 

void fun1(char *s1, char *s2)  { 
     char *tmp;  
     tmp = s1; 
     s1 = s2; 
     s2 = tmp; 
} 

void fun2(char **s2, char **s2)  { 
     char *tmp; 
     tmp = *s1; 
     *s1 = *s2; 
     *s2 = tmp; 
}

int main ()  { 
     char *str1 = "Hi", *str2 = "Bye"; 
     fun1(str1, str2);     printf("%s %s", str1, str2); 
     fun2(&str1, &str2);   printf("%s %s", str1, str2); 
     return 0; 
} 

The output of the program above is

Consider the following C program.

#include <stdio.h>
struct Outnode { 
    char x, y, z ; 
};

int main () { 
    struct Outnode p = {'1', '0', 'a'+2} ; 
    struct Outnode *q = &p ; 
    printf ("%c, %c", *((char*)q+1), *((char*)q+2)) ; 
    return 0 ; 
} 

The output of this program is

(a) Consider the following pseudo-code
(all data items are of type integer):

   Procedure P (a, b, c);
                 a:=2;
                 c:=a+b;
   end {P}
   begin
                 x:=1
                 y:=5;
                 z:=100;
                 P(x,x*y,z);
                 Write (‘x=’,x,z=’,z)
   end: 

(b) For the following pseudo-code, indicate the output, if
(i) static scope rules and (ii) dynamic scope rules are used

      Var, a, b : integer;
      Procedure P;
         a:=5; b:=10
      end {P};
      procedure Q;
      var a, b : integer;
      P;
      end {Q};
      begin
      a:=1; b:=2;
      Q;
      Write (‘a =’, a, ‘b=’,b)
      end. 

Give short answers to the following questions:
(i) Convert the following Pascal statement to a single assignment statement:

       if x > 5 they y:=true
             else y:=false; 

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Consider the following Pascal function:

 function X (M:integer) : integer;
 var i:integer;
 begin
   i = 0;
   while i*i < M do i; =i+1
   X;=i
 end

Consider the following recursive definition of fib:

 fib (n) : = if n = 0 then 1
             else if n = 1 than 1
             else fib (n – 1) + fib (n – 2)

The number of times fib is called (including the first call) for an evaluation of fib (7) is ___________

Consider the following PASCAL program segment:

 if i mode 2 = 0 then
           while i > = 0 do
             begin
              i:=i div 2;
              if i mod 2 < > 0 do then i:=i – 1
                   else i:=i – 2
 end

An appropriate loop-invariant for the while-loop is ______