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 _______.

Consider the following C program

int a, b, c = 0;
void prtFun (void);
int main ()
{
    static int a = 1; /* line 1 */
    prtFun();
    a += 1;
    prtFun();
    printf ( "n %d %d " , a, b) ;
}
  
void prtFun (void)
{
    static int a = 2; /* line 2 */
    int b = 1;
    a += ++b;
    printf (" n %d %d " , a, b);
}

What output will be generated by the given code segment?

Consider the following C program

int a, b, c = 0;
void prtFun (void);
int main ()
{
    static int a = 1; /* line 1 */
    prtFun();
    a += 1;
    prtFun();
    printf ( "n %d %d " , a, b) ;
}
  
void prtFun (void)
{
    static int a = 2; /* line 2 */
    int b = 1;
    a += ++b;
    printf (" n %d %d " , a, b);
}

What output will be generated by the given code segment if:

Line 1 is replaced by auto int a = 1;
Line 2 is replaced by register int a = 2;

What will be the output of the following C program segment?

char inchar = 'A';
switch (inchar)
{
case 'A' :
    printf ("choice A n") ;
case 'B' :
    printf ("choice B ") ;
case 'C' :
case 'D' :
case 'E' :
default:
    printf ("No Choice") ;
}

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

In the following C program fragment, j, k n and TwoLog_n are interger variables, and A is an array of integers. The variable n is initialized to an integer ≥3, and TwoLog_n is initialized to the value of 2*⌈log₂(n)⌉

   for (k = 3; k < = n; k++)
               A[k] = 0;
   for (k = 2; k < = TwoLog_n; k++)
          for (j = k + 1; j < = n; j++)
                    A[j] = A[j] || (j%k);
   for (j = 3; j < = n; j++)
          if (!A[j]) printf("%d", j); 

The set of numbers printed by this program fragment is

Consider the C program shown below.

#include 
#define print(x) printf("%d", x)
int x;
void Q(int z)
{
    z += x;
    print(z);
}
void P(int *y)
{
    int x = *y + 2;
    Q(x);
    *y = x - 1;
    print(x);
}
main(void)
{
    x = 5;
    P(&x);
    print(x);
} 

The output of this program is

Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P {
    void f(int i) {
        print(i);
    }
}

Class Q subclass of P {
    void f(int i) {
        print(2*i);
    }
} 

Now consider the following program fragment:

Px = new Q();
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1); 

Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be

Consider the following logic program P

A(x) <- B(x, y), C(y) 
     <- B(x,x) 

Which of the following first order sentences is equivalent to P?

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}
main()
{
    P(i + j);
}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}
main()
{
    P(i + j);
}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are:

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:

(a) What type of parameter passing mechanism (call-by-value, call-by-reference, call-by-name, or-by-value result) is the following sequence of actions truing to implement for a procedure call P(A[i]) where P(i:integer) is a procedure and A is an integer array?

 1. Create a new local variable, say z.
 2. Assign to z the value of A[i].
 3. Execute the body of P using z for A[i]
 4. Set A[i] to z. 

Is the implementation correct? Explain and correct it if necessary. You are supposed to make only small changes.

(b) Show the activation records and the display structure just after the procedures called at lines marked x and y have started their execution. Be sure to indicate which of the two procedures named A you are referring to.

 Program Test;
   Procedure A;
     Procedure B;
       Procedure A;
     ……
   end a;
 begin
   y:A;
   end B;
 begin
   B;
   end A;
 begin
   x:A;
 end Test.