Birla Institute of Technology (BIT Mesra) 2007 MS Software Engineering Comprehensive (STRUCTURE OF PROGRAMMING LANGUAGES ) - Question Paper

Birla Institute of Technology & Science, Pilani
Distance Learning Programmes Division
2nd Semester 2006-2007

Comprehensive exam (EC-2 Regular)

Course No. : IS ZC342
Course Title : STRUCTURE OF PROGRAMMING LANGUAGES
Nature of examination : Open Book
Weightage : 60%
Duration : three Hours
Date of examination : 01/04/2007 (AN)


Note:
1. Please follow all the Instructions to Candidates provided on the cover page of the ans book.
2. All parts of a ques. should be answered consecutively. every ans should begin from a fresh page.
3. Mobile phones and computers of any type should not be brought inside the exam hall.
4. Use of any unfair means will outcome in severe disciplinary action.



Q.1 (a) Consider the subsequent algorithm to calculate GCD (Greatest Common Divisor) of 2 positive integers.
Procedure gcd(n, m: integers) : integer
start
if m =0 then return n;
else return gcd(m, n mod m)
end;
Show all the snap shots and contents of the stack during the execution of gcd(18, 120). Is it tail recursive? If so provide an equivalent procedure after eliminating tail recursion. Show the snap shots for activation records (during execution of stack) for your procedure.




Q.1 (b) Draw the flow diagram for the subsequent fragment:
if E1 then S1; elsif E2 then S2 ; else S3; end [6 X two = 12]





Q.2 Given an array A of size n, assuming that it has enough room for insertions, write C –like code for the function:
void reverseList ( int A[ ], int n)
that reverses the contents of the array A.

List out the pre-condition and post -condition for the above function.
Using the axiomatic semantics construct loop invariant condition and prove the partial correctness of your procedure. [4 + two + two + four =12]




Q.3 Given a C –procedure in C –like syntax:
FUNNY_FUN(int x, int y) {x=x+y; y=x-y; x=x-y; }
What will be the output for the function call: FUNNY_FUN(2, 3), if the parameter passing method is
(a) call by value (b) call by reference (c) call by value outcome (d) call by name?
[4 x three = 12]





Q.4 Design a compile time descriptor for the subsequent kind definitions in C –like language:
typedef enum{SPHERE, CIRCLE, RECTANGLE}ShapeKind;
struct Geometry
{
ShapeKind kind;
union
{
Sphere s;
Circle c;
Rectangle r;
}Shape;
};

struct Sphere {double rad; double x,y,z;};
struct Circle{double r; double x,y;};
struct Rectangle{double base; double height ;};

Here Sphere contains the centre co-ordinates provided by x, y, z respectively with radius rad; Circle contains the centre co-ordinates provided by x, y respectively with radius r;
Rectangle contains its length and width provided by the fields base, height respectively. Outline the implementation of this compile time descriptor. [8 + four = 12]




Q.5 Design and implement an abstract data kind MyList using any Object Oriented language that you know, keeping the subsequent Operations in mind. MyList should have suitable constructor

(i). int searchElement( Element key) that returns the position of key in MyList; in case the Element is absent it should return -1.

(ii). boolean isSorted() that returns actual if MyList is a sorted in ascending order; otherwise it returns false.

(iii). int getFrequency(Element key) that returns the number of occurrences of key in MyList

(iv). Apply synchronization principles to implement a method
void doOperation(Element key)

that will be called by 2 threads 1 for inserting key into MyList and a different for deleting the identical from MyList. discuss the synchronization mechanism involved in this method referring to block synchronization and code synchronization. [2 + two + two + two + four =12]

***************************

Earning:   Approval pending.