Solution

Total number of candidate keys possible with ‘n’ attributes is (2^n)-1.

Solution

While converting the ER model into the relational model, we should create a separate table for each multivalued attribute. Hence, {Roll_no, Mob_no} and {Roll_no, Email_id} are the valid attribute sets for the newly created relations among the given options.

Solution

All strict schedules are cascadeless and all cascadeless schedules are recoverable

Solution

Conservative 2-PL is Deadlock free and but it does not ensure Strict schedule

Solution

Solution

Solution

The candidate key is HI. There are no parts of the key that are determined by the non prime attributes. Hence, the relation R is in 2NF

Solution

Put the middle element in the left node, if you follow this you will get 4 as answer. Put the middle element in the right node, if you follow this you will get 3 as answer. As the minimum number of splits is asked, the answer is 3.

Solution

The given set of FDs F is:- A → BC CD → E B → D E → A

The left side of each FD in F is unique. Also none of the attributes in the left side or right side of any of the FDs is extraneous. Therefore the canonical cover Fc is equal to F.

Solution

A decomposition {R1, R2} is a lossless-join decomposition. Because R1 = (A, B, C), R2 = (A, D, E), and R1 ∩ R2 = A. Since A is a candidate key.

The dependency B → D is not preserved

Solution

Precedence graph for the given schedule is:

T1-T3-T2

Solution

Hashing is a data structure which is used to map a given value with a particular key for faster access of elements. Whereas arrays, linked list, BST doesn’t have that motivation to do, hence those can’t be the answer.

In a direct access table where we make a big array and use phone numbers as index in the array. An entry in the array is NIL if the phone number is not present, else the array entry stores a pointer to records corresponding to the phone number. Time complexity wise this solution is the best among all, we can do all operations in O(1) time. For example, to insert a phone number, we create a record with details of given phone number, use phone number as an index and store the pointer to the created record in the table.

This solution has many practical limitations. First problem with this solution is that the extra space required is huge. For example if phone number is n digits, we need O(m * 10n) space for a table where m is the size of a pointer to record. Another problem is an integer in a programming language may not store n digits.

Due to above limitations Direct Access Table cannot always be used. Hashing is the solution that can be used in almost all such situations and performs extremely well compared to above data structures like Array, Linked List, Balanced BST in practice. With hashing we get O(1) search time on average (under reasonable assumptions) and O(n) in the worst case.

Hashing is an improvement over Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as index in a table called hash table.

Solution

#include<stdio.h>

struct Fraction

{

int num; // the numerator of the fraction

int denom; // the denominator of the fraction

};

void main()

{

struct Fraction f1; // a fraction structure

struct Fraction *fPtr; // pointer to a fraction

fPtr = &f1; // fPtr now points to f1

f1.num = 3; // this is legal, of course

fPtr.num = 10; // but how about this? NO! ILLEGAL

// cannot put a pointer on the left side

// of the dot-operator

printf("%d", f1.num);

}

The above program will give following error:

error: request for member ‘num’ in something not a structure or union

fPtr.num = 10;

If you want to replace the value of num the correct code will be:

(*fPtr).num = 10;

Solution

When the tree is skew tree, in both cases of BT and BST, in worse case the time complexity will be O(n)

As the height of balanced BST is logn so the search time will be of order logn in worse case scenario too.

In the case of min heap, searching a minimum number takes O(1) time but searching any other element in the worst case will take O(n) , as it can also be of skewed structure.

Solution

Solution

an array of n pointers => (∗ a[N])

to function => (∗ a[N]) ( )

returning pointers => (∗(∗ a[N]) ( ))

to functions => (∗(∗ a[N]) ( )) ( )

returning pointers => ∗(∗(∗ a[N]) ( )) ( )

to characters => char ∗(∗(∗ a[N]) ( )) ( );

I have decoded every word of the answer as shown what does it mean in blue font

Let's check the answer using precedence table

Solution

Recursion tree for above code:

#include<stdio.h>

void abc(char *s)

{

printf("abc(%s) call\n",s);

if(s[0]=='\0')return;

abc(s+1);

abc(s+1);

printf("==> %c <===",s[0]);

printf("endof abc(%s)\n",s);

}

int main()

{

abc("123");

}

O/P:

abc(123) call

abc(23) call

abc(3) call

abc() call

abc() call

==> 3 <===endof abc(3)

abc(3) call

abc() call

abc() call

==> 3 <===endof abc(3)

==> 2 <===endof abc(23)

abc(23) call

abc(3) call

abc() call

abc() call

==> 3 <===endof abc(3)

abc(3) call

abc() call

abc() call

==> 3 <===endof abc(3)

==> 2 <===endof abc(23)

==> 1 <===endof abc(123)

Solution

Solution

Check the output of the code with one extra printf in for loop which will make you understand what is happening in every loop of for.

#include<stdio.h>

void main()

{

int a,b;

b=2;

for(a=1;a<6;a++)

{

a=a+2;

b=b+a-2;

printf("a=%d, b=%d\n",a,b);

}

printf("%d\n",b);

}

/*

Output:a=3, b=3 //1st iteration

a=6, b=7 //2nd iteration

7 //b value

*/

Solution

computes the intersection of two lists and computes the union of two lists

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn’t matter.

Intersection (list1, list2)

Initialize the result list as NULL. Traverse list1 and look for its every element in list2, if the element is present in list2, then add the element to result.

Union (list1, list2):

Initialize the result list as NULL. Traverse list1 and add all of its elements to the result.

Traverse list2. If an element of list2 is already present in result then do not insert it to result, otherwise insert.

computes the list by considering a node alternatively from each list.

Given two linked lists, insert nodes of the second list into the first list at alternate positions of the first list.

For example, if first list is 5->7->17->13->11 and second is 12->10->2->4->6, the first list should become 5->12->7->10->17->2->13->4->11->6 and second list should become empty. The nodes of the second list should only be inserted when there are positions available. For example, if the first list is 1->2->3 and second list is 4->5->6->7->8, then first list should become 1->4->2->5->3->6 and second list to 7->8.

Use of extra space is not allowed (Not allowed to create additional nodes), i.e., insertion must be done in-place. Expected time complexity is O(n) where n is number of nodes in first list.

computes the difference of two lists.

As we have 2 head pointers, we can traverse the head of 1 linked list from start to end for every vertex of other linkedlist. And if the node value matches with the other we can skip that node anf for remaining we can create a new list out of that.

Hence A,B, C,D all are correct

Solution

a<= b == d> c

<= and > has higher precedence that ==

<= and > has left to right associativity.

Hence a<=b will result to TRUE

then d>c will result to TRUE

Now TRUE==TRUE this will result to true again

hence true will be printed

Solution

#include<stdio.h>

void switch_check(int x)

{

switch(x)

{

case 0: printf("@");

case 1: printf("H");

case 2: printf("I");

case 3: printf("M");

case 4: printf("A");

case 5: printf("L");

case 6: printf("A");

case 7: printf("Y");

case 8: printf("A");

default: printf("!");

}

}

void main()

{

printf("%d\n", 2<<1);

switch_check(2<<1 );

}

Output:

4 // 2<<1 => 010 << 1 => 100 => 4

ALAYA! // switch(4) => A after that there is no break hence everything after it gets printed!

Solution

→ Given list is in descending order which can be sorted using quick sort. This is the worst case scenario of quick sort. Quicksort takes the worst case time is O(n^2).

T(n) = O(n^2)

= c * n^2

⇒ 200 = c * n^2

⇒ c = 1/200

Note: (200)^2 = 40,000

40,000 / 200 = 200

It means worst case probability is 1/200

→ The selection sort takes O(n2) time to sort ‘n’ elements.

T(n) = c * n^2

⇒ 250 = c * n^2

⇒ n^2 = 250/c

= 250/(1/200)

= 250 * 200

= 50,000

=> n=(√50000)

= 223.60

Solution

The data can be sorted using external sorting which uses a merging technique. This can be done as follows:

Step-1. Divide the data into 10 groups each of size 2 GB.

Step-2. Sort each group and write them to disk.

Step-3. Load 10 items from each group into the main memory.

Step-4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen.

Step-5. Iterate step-4 until all items are not outputted.

Solution

T(n) = 3T(n/3) + (√n)logn

Apply master’s theorem

a = 3, b=3, k = ½, p = 1

case: a > b^k

T(n) = O(n)

Solution

To construct a spanning tree of graph, we have to remove E – V + 1 edges.

Example:

= E – V + 1

= 3 – 3 + 1

= 1

Solution

Given 2, 6, 8, 1, 4, 3

Pass1:

I =0

j = 0: 2, 6, 8, 1, 4, 3

j = 1: 2, 6, 8, 1, 4, 3

j = 2: 2, 6, 1, 8, 4, 3

j = 3: 2, 6, 1, 4, 8, 3

j = 4: 2, 6, 1, 4, 3, 8

Pass 2

I = 1

j = 0: 2, 6, 1, 4, 3, 8

j = 1: 2, 1, 6, 4, 3, 8

j = 2: 2, 1, 4, 6, 3, 8

j = 3: 2, 1, 4, 3, 6, 8

Pass 3

I = 2

j = 0: 1, 2, 4, 3, 6, 8

j = 1: 1, 2, 3, 4, 6, 8

j = 2: 1, 2, 3, 4, 6, 8

Solution

We recursively subtract the smaller number from the larger.

Let’s estimate this algorithm’s time complexity (based on n = a+b).

The number of steps can be linear, for e.g. bob(x, 1), so the time complexity is O(n).

This is the worst-case complexity, because the value x + y decreases with every step.

Note: The given algorithm is nothing but GCD of two numbers.

Solution

1. h (10) = 1 + 10 % 10 = 1

2. h (22) = 1 + 22 % 10 = 3

3. h (31) = 1 + 31 % 10 = 2

4. h (4) = 1 + 4 % 10 = 5

5. h (15) = 1 + 15 % 10 = 6

6. h (28) = 1 + 28 % 10 = 9

7. h (17) = 1 + 17 % 10 = 8

8. h (27) = 1 + 27 % 10 = 8

It collides with locations 8 and 9 and is placed at location 10.

9. h (88) = 1 + 88 % 10 = 9

It collides with location 9 and 10 then, placed at 0.

10. h (59) = 1 + 59 % 10 = 10

It collides with 10, 0, 1, 2, 3 and places at 4.

Solution

P=4

Q=8

R=11

S=6

Arrange the letters in increasing order.

Total bits=1*11+2*8+3*4+3*6

=11+16+12+18

=57

Average length=57/29=1.9655

From above solution

R = 1

P = 001

Q = 01

S = 000

Solution

Max MST:

=5+7+3+4+2+5+4+3+2+3

=38

Min MST:

=1+2+1+2+1+1+2+1+2+3

=16

Common: S6, S9 ✓

S7, S10

Solution

The recurrence relation to get minimum number of scalar multiplications are

→ To get maximum value, we are choosing maximum instead of minimum.

We can get a maximum of 5 possible parentheses using standard dynamic programming method (or) using catalan numbers.

Given the matrices A,B,C,D

Assume the dimensions of A=d₀×d₁, etc..,

Below are the five possible parenthesizations of these arrays, along with the number of multiplications:

(AB)(CD) → d₀d₁d₂ + d₂d₃d₄ + d₀d₂d₄ → 300 + 378 + 540 = 1218

((AB)C)D → d₀d₁d₂ + d₀d₂d₃ + d₀d₃d₄ → 300 + 420 + 630 = 1350

(A(BC))D → d₁d₂d₃ + d₀d₁d₃ + d₀d₃d₄ → 210 + 350 + 630 = 1190

A((BC)D) → d₁d₂d₃ + d₁d₃d₄ + d₀d₁d₄ → 210 + 315 + 450 = 975

A(B(CD)) → d₂d₃d₄ + d₁d₂d₄ + d₀d₁d₄ → 378 + 270 + 450 = 1098

→ The maximum number of scalar multiplications are 1350 and optimal parenthesization is ((AB)C)D

→ The minimum number of scalar multiplications are 975 and optimal parenthesization is (A((BC)D))

→ Difference between maximum and minimum scalar multiplications are

= 1350-975

= 375

Solution

→ True. Simply call BUILD-HEAP at the root, which runs in O(n) time.

→ True: The shortest path to t can be easily computed given the shortest paths to all vertices from which there is an edge to t.

→ False: Merge sort is stable whenever the underlying merge operation always breaks ties by selecting from the left sub-array, and it is easy to ensure that this is the case.

→ False. The auxiliary sorting routine in radix sort needs to be stable, meaning that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array.