DSA-Mids Solution-2018

Roll No:-BSCS-2017 Name:____________ Section:

GC UniversityLahore

Solution of DSA MidTerm Exam Spring-18Selester-4

Time Allowed: 10Minutes      MCQ Part Set “X”                    Max. Marks: 10

Q#1:    Answer MCQ questions by FILLING THE CIRCLE.

1.     Brute Force Sorting techniques require comparison of each element with each other element, and therefore run in  _____________ time?

A	Linear	¡
B	Fixed	¡
C	N	¡
D	N2	¡

2.       Brute-force Sorting algorithm’s Average case time is ____________ ?

A	N	¡
B	N/2	¡
C	Constant	¡
D	Quadratic.	¡

3.       Only method to dynamically increase/decrease capacity of __________ data structure is to dynamically delete and then allocate ccording to new size.

A	Singly Linked list	¡
B	Circular Linked list	¡
C	Array	¡
D	All of above	¡

4.       Operators stack used in expression evaluator maintains __________ priorityof operators from top to bottom.

A	FIFO	¡
B	LIFO	¡
C	Descending	¡
D	Ascending	¡

5.       The _______________has the advantage that compaction is not required.

A	Circular buffer	¡
B	Circular Linked list	¡
C	Only A is correct.	¡
D	Both A and B are correct.	¡

6.       General order of operations when inserting a new node in any dynamic data structure is to adjust the pointers of_______________? 

A	New node, then adjacent nodes, then globals.	¡
B	Globals, then new node, then adjacent.	¡
C	Adjacent nodes, then globals, then new node.	¡
D	New node, then globals, then adjacent.	¡

7.       Following is the correct PRE-FIX form of A+B*C/D?

A	+A*B/CD	¡
B	ABCD/*+	¡
C	A+*B/CD.	¡
D	None of above.	¡

8.       Priority Queue is different from simple queue as it requires _________________.

A	Compaction	¡
B	In-order deletion	¡
C	In Order insertion.	¡
D	Deletion from both ends.	¡

9.       A[i -1 ] =  i* A[i]   is the typical technique to find ___________ of polynomial? 

A	Root	¡
B	Antiderivative	¡
C	Derivative	¡
D	One of above (actual statement was None of above)	¡

10.   Divide & Conquer Algorithms have the advantage that Time Cost is reduced to _____________________.

A	Log(N)	¡
B	Quadratic.	¡
C	Linear	¡
D	N2.	¡

Roll No:-BSCS-2016Name:______________Section:_____

Q1	Q2	Q3	Q4	Total

                    GC University Lahore

Solution of DSAMidTerm Exam Spring-18Semester-4

Time Allowed: 1 Hour 5 Minutes Subjective Part                Max. Marks: 10

All necessary boundary checks and special cases must be applied.

Note: Following solution is not complete. DIY means Do it yourself. Boundary checks and special cases are applied in some answers.

Q#2: a) Number x is to be inserted into a linear doubly linked list in order. Write  pseudocode.

Node * t=new node(x);

If(!first){first=last=t; return;}//empty case

If(first-> data > =x){//new node to be inserted even before first.

t-> next=first;

first->prev= t;

first =t;

}

If(last->data<x){insert at last; }//DIY

Node * t1=first;

While(t1 ->next->data<x || t1->next!=NULL){t1=t1->next;}//search for node’s position or last, then insert  after t1

//step-1 set new node’s pointers

t->prev=t1;

t->next=t1->next;

step-2: set adjacent nodes pointers

t1->next->prev=t;

t1->next=t;

//step-3 set global pointers. Not needed because node is inserted in between first and last

b) Write pseudocode to store Antiderivative of Polynomial Array A into array B. Consider contant of integration is zero.

B[0]=0;//coefficient of constant term. i.e constant of integration

For(inti=1;i<N; i++){

B[i]= A[i-1]/i; i-1th power is now ith power but divided by i power.

}

c)Write pseudocode to find an element x and delete its previous node in singly linked list.

Bool findAndDeletePrev(int x){

If(first->data= =x )return false;//there is no node previous to first

If((first->next->data= =x) {//data matches next to first, therefore delete first

Node * t=first;

First=first->next;

Delete t;

}

Node * t=first;

While(t->next->next->data!=x|| t->next->next!=NULL)t=t->next;//scan for next to next  node matching data;

If(t==NULL) return false;//element not found

If(t==last)// assign last pointer to second last, then delete last. DIY.

}

Q3: a) Write pseudocode to search &remove a value x from a sortedlinearsingly linked list.

If(!first) return false;//empty list

If(first->data> x|| last->data<x) {// x does not lie in range of sorted list.

Return false;

}

If(first->data==key){//first node to be deleted. DIY

}

Node * t=first;

While(t->next->data<=x|| t->next!=NULL){//find node whose next matches

T=t->next;

}

If(t->next-data==x)//above loop broken before required node

{

//delete t-> next. DIY

}

Q.3: b) What is problem with following code for insertion into a circular queue. Give reasons and write correct version.

bool insert(int x){

If (head = = tail) {//circular queue is full

                        Return False;

}

else{

            If(tail= = MAX)compact( );

            A[tail + +] = x;

Return True;

}

}

1.       CQueueis full only when head = = tail+1, (not when head = = tail)

2.       Tail = = MAX does not apply to circular queue and compaction is not required.

3.       if(tail = = MAX) tail  = 0;

thenA[tail]= x; Tail + +;

c) Write pseudocdeto  implementinsertlast( int x) for a circular double linked list.

Node * t=new node(x);

If(!first)[first=t;first->prev=first->next=t; return;} insert to empty

If(first->next==first){t->prev=t->next=first;first->next=first->prev=t; return;}

t->next=first;

t->prev=first->prev;

first->prev=t; return;

Q. 3 d)Convert the following expression into Postfix form using stack technique. Then evaluate the answer using stack. Show dry run steps, especially stack states.

Conversion Steps

Infix=1+9/3^2^1 *4 – 7^2/7*7*7/7

Postfix=1932^1^/*4*+72^7/7*77/*-

+

^	^			/
/	/	*		*
+	+	+	-	-

Evaluation Steps

1932^1^/*4*+72^7/7*77/*-

	^	=		^	=
2	2		1	1
3	3	9	9	9	9
9	9	9	9	9	9
1	1	1	1	1	1

Q. 4: a) Write typical pseudocode to insert a number x into a dynamic array, with the feature that array grows double when space utilization is greater than 70%.

If(SIZE > = MAX * 0.7)//if utilization is around 70%

{

Int * t= new int(MAX);// allocate a new array

For(int I = 0 ;I < SIZE ; i++ ) t[i] = A[i]; copy elements

Delete A;

A=new int(MAX * 2);//delete and re-allocate double size

For(int I = 0 ; I < SIZE; i++) A[i] = t[i];//copy back

}

A[SIZE++]=x; //insert-last, if no other method is specified

b) Write pseudocode to search and modify an element x in a sorted array, such that its new value becomes x1 and it travels to its new position in-order.

Int index = search(A, 0,N,x)//can use binary search to find position of x

If(index= = -1) return false; //element not found, search returs -1

int index2 = search(A,0,N,x1);//find its new position.

If(index2>index){//element has to be shifted righttside

For(inti=index2;i<=index ;i--)A[i-1]=A[i];//copy each element to its left side

}

Else{//element is  to  be shifted leftside

For(inti=index;i<=index2;i++)A[i-1]=A[i];

}

A[index2]=x2;

//make necessary corrections. Above code is just a concept

 Following is recursive definition of  a mathematical formula. Write the recursive function. Apply proof of correctness to check if algorithm is correct or not.

Is it divide &conqer or not?

Is it branch recursion?

x¹= x

x^N = { x * (x^(N-1)/2)² for N odd

     = { (x^N/2)² for N even

IntrecPow(float x, int N)

{

If(N==1)return x;//base case

If(N%2){//odd-case

N=N-1;

Float y= recPow(x,N/2);

Return x*y*y;

}

Else{//even-case

Float y= recPow(x,N/2);

Return y*y;

}

}

This is Divide & Conquer. This is branch recursion, but only one branch executes in each call.

Proof of correctness:

Base case: x^N for N=1 is x¹ = x itself.  hencebasecase proved

Recursive call:

Even case:algebraically x^AB = (x^A )^B so x^N = (x^N /2)²because N/2 * 2= N

(x^N /2)²=  (x^N /2) * (x^N /2)by square rule. So even case is proved.

Odd case: N is decremented to smaller even number. Then recursive call is generated for even case N – 1.

Then x is multiplied with result. As x^N  = x * x^N-1 . henceproved.

d) Fill the following table, assign precedence numbers to all operators and also mention associativity is right-to- left ot left-to-right.

Operator	Precedence	Associativity
=	0	Left-right
-          (subtract)	4	Left-right
*	3	Left-right
^	1	Right-left
/	2	Left-right
+	4	Left-right