Which one of the following is NOT logically equivalent to ¬∃x(∀y(α) ∧ ∀z(β))?

A D flip-flop is to be connected to an 8085 microprocessor chip as a 1-bit output port with a port address of FF hex. Data bit D3 should be involved in the data transfer from CPU to the flip-flop. The flip-flop should be cleared on power ON.
(a) Using only one NAND gate (fan in of 10), one NOT gate and one D flip-flop. Draw the required interface logic circuit (only the relevant signals should be shown).
(b) Write a program to generate a square wave on the output of the flip-flop. ON and OFF periods of the square wave should be 7 bus cycles each.

Consider the following program in Pseudo-Pascal syntax.

      var z: integer
       procedure recur(x):
       begin if x <= 40 then
                  begin x:x+z
                     recur(x);
                     z:=x+10
                  end
       end(*recur*)
   begin(*what*)
       z=10;
       recur(z);
       writeln(z)
   end 

(a) Suppose the parameter to the procedure ‘recur’ is passed by value.
i. What value is printed by program?
ii. How many times is ‘recur’ called?
(b) What value is printed by the program if the parameter is passed by reference?

Consider the grammar

   S → bSe
   S → PQR
   P → bPc
   P → ε
   Q → cQd
   Q → ε
   R → dRe
   R → ε  

where S,P,Q,R are non-terminal symbols with S being the start symbol; b,c,d,e are terminal symbols and ‘ε’ is the empty string. This grammar generates strings of the form bⁱ, c^j, d^k, e^m for some i,j,k,m ≥ 0.
(a) What is the condition on the values of i,j,k,m?
(b) Find the smallest string that has two parse trees.

Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights are assigned to edges of G as follows:

A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex ν₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed?

Let L = {a₁, a₂, ......, a_n} n ≥ 0 be a list whose Pascal representation is

                  type list = record
                     next: ↑ list; val: integer end  

The following function returns a list in which a_2i and a_2i-1, 1 ≤ i ≤ [n/2] are interchanged. Complete the function by filling the boxes. Write the line number and the content of the box in your answer sheet.

1. function change (p: ↑ list): ↑ list;
2. var q.t: ↑ list;
3. begin 
4. if p = nil then change := p
5. else if p ↑ next = nil then change : ▭
6. else begin
7. q : p ↑ next;
8. ▭ := q;
9. t : q ↑ next;
10. ▭ := p;
11. ▭ := change(t)
12. end
13. end 

Consider a graph whose vertices are points in the plane with integer co-ordinates (x,y) such that 1≤x≤n and 1≤y≤n, where n≥2 is an integer. Two vertices (x₁,y₁) and (x₂,y₂) are adjacent iff ∣x₁−x₂∣ ≤ 1 and ∣y₁–y₂∣ ≤1. The weight of an edge {(x₁,y₁),(x₂,y₂)} is √(x₁–x₂)² + (y₁–y₂)²
(a) What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any explanations.
(b) What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

Consider a hash table with n buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is 1/n. The hash table is initially empty and K distinct values are inserted in the table.

(a) What is the probability that bucket number 1 is empty after the K^th insertion?
(b) What is the probability that no collision has occurred in any of the K insertions?
(c) What is the probability that the first collision occurs at the K^th insertions?

Let F be the set of one-to-one functions from the set {1,2,…,n} to the set {1,2,…,m}, where m≥n≥1.
(a) How many functions are members of F?
(b) How many functions f in F satisfy the property f(i) = 1 for some i, 1≤i≤n?
(c) How many functions f in F satisfy the property f(i) < f(j) for all 1≤i≤j≤n?

Let R be a reflexive and transitive relation on a set A. Define a new relation E on A as

 E = {(a,b) ∣ (a,b)∈R and (b,a)∈R} 

(a) Prove that E is an equivalence relation on A.
(b) Define a reason ≤ on the equivalence classes of E as E₁ ≤ E₂ if ∃a,b such that a∈E₁, b∈E₂ and (a,b)∈R. Prove that ≤ is a partial order.

Consider the following function.

Function F (n, m: integer): integer;
begin
       If (n <= 0) or (m <= 0) then F:=1
       else
            F:= F(n-1, m) + F(n, m-1);
       end;

Use the recurrence relation to answer the following question. Assume that n, m are positive integers. Write only the answers without any explanation.
(a) What is the value of F(n,2)?
(b) What is the value of (n,m)?
(c) How many recursive calls are made to the function F, including the original call, when evaluating F(n,m).

A size-balanced binary tree is a binary tree in which for every node, the difference between the number of nodes in the left and right subtree is at most 1. The distance of a node from the root is the length of the path from the root to the node. The height of a binary tree is the maximum distance of a leaf node from the root.
(a) Prove, by using induction on h, that a size-balance binary tree of height h contains at least 2^h nodes.
(b) In a size-balanced binary tree of height h≤1, how many nodes are at distance h−1 from the root? Write only the answer without any explanations.

Construct a finite state machine with minimum number of states, accepting all strings over {a,b} such that the number of a's is divisible by two and the number of b's is divisible by three.

Given that L is a language accepted by a finite state machine, show that L^P and L^R are also accepted by some finite state machines, where
L^P = {s|ss' ∈ L, for some string s'}
L^R = {s|s obtainable by reversing some string in L}

A language L is a subset of Pascal with the following constructs:

(a) Expressions involving the operators '+' and '<' only
(b) Assignment statements
(c) 'while' statements and
(d) Compound statements with the syntax 'begin...end'
Give an unambiguous grammar for L.

Following is a state table for some finite state machine.

(a) Find the equivalence partition on the states of the machine.
(b) Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states X and Y are equivalent then use XY as the name for the equivalent state in the minimal machine.)

Let f = (w'+y)(x'+y)(w+x'+z)(w'+z)(x'+z)
(a) Express f as the minimal sum of products. Write only the answer.
(b) If the output line is stuck at 0, for how many input combinations will the value of f be incorrect?

An array A contains n≥1 positive integers in the locations A[1], A[2],... A[n]. The following program fragment prints the length of a shortest sequence of consecutive elements of A, A[i], A[i+1],...A[j] such that the sum of their values is ≥M, a given positive number. It prints ‘n+1’ if no such sequence exists. Complete the program by filling in the boxes. In each case use the simplest possible expression. Write only the line number and the contents of the box.

1. begin
2. i: +1; j:=1;
3. Sum := ▭;
4. min: n; finish:=false;
5. While not finish do
6. If ▭ then
7. if j=n then finish:=true.
8.     else
9. begin
10.    j:=j+1;
11.    sum:=▭
12.        end
13. else
14. begin
15.        If(j-1) < min then min:=j-1;
16.        sum:=sum - A[i];
17.        i:=i+1;
18. end
19. writeln (min+1);
20. end.   

Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.

Node  *remove-duplicates(Node *head, int *j)
{
    Node *t1, *t2;
    *j=0;
    t1 = head;
    if (t1! = NULL) t2 = t1 →next;
    else return head;
    *j = 1;
    if(t2 == NULL) return head;
    while t2 != NULL)
    {
        if (t1.val != t2.val) --------------------------→ (S1)
        {
            (*j)++; t1 → next = t2; t1 = t2: ----------→ (S2)
        }
        t2 = t2 → next;
    }
    t1 → next = NULL;
    return head;
} 

Assume the list contains n elements (n≥2) in the following questions.
(a) How many times is the comparison in statement S1 made?
(b) What is the minimum and the maximum number of times statements marked S2 get executed?
(c) What is the significance of the value in the integer pointed to by j when the function completes?

A B⁺ - tree of order d is a tree in which each internal node has between d and 2d key values. An internal node with M key values has M+1 children. The root (if it is an internal node) has between 1 and 2d key values. The distance of a node from the root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from the root.
(a) What is the total number of key values in the internal nodes of a B⁺ - tree with l leaves (l≥2)?
(b) What is the maximum number of internal nodes in a B⁺ - tree of order 4 with 52 leaves?
(c) What is the minimum number of leaves in a B⁺ - tree of order d and height h(h≥1)?

The language L, defined by the following grammar allows use of real or integer data in expressions and assignment statements.

    (assign-stmt):: = (LHS):= (E)
             (E) :: = (E) + (T)|(T)
             (T) :: = (T) * (V)|(V)
             (V) :: = id|((E))
           (LHS) :: = id 

It is required to convert expression and assignment strings of L into postfix strings that use the type-specific operators (+, i), (+, r), (*, i), (*, r), (:=, i) and (:=,r).
Write a syntax directed translation scheme to convert expression and assignment strings into the post-fix form. You may assume that the name and type of a variable can be obtained by making the function calls 'give-type (id)' and 'give-name (id)' respectively.

Consider the following program fragment in Pascal:

   Program Main;
      var X : integer;
      procedure A:
         var Y : integer;
         procedure B:
            var Z : integer;
            procedure C:
               var Z : integer;
               begin(* Procedure C *)
               :
               end(* Procedure C *)
 begin(*Procedure B*)
    :
  C; (* call to C *)
  A; (* call to A *)
    :
 end(*Procedure B*)
     begin(* Procedure A *)
        :
        B; (* call to B *)
        :
     end(* Procedure A *)
  begin (* Main *)
        :
        A; (* call to A *)
        :
  end(* Main *) 

Assume that there are no calls to any procedures other than the ones indicated above. It is known that at some point of time during the execution of this program five activation records exist on the run-time stack. Describe the run-time stack at this point of time by clearly indicating the following: the top of the stack, the contents of the static link and dynamic link, and allocation of the local variables in each record.

Following floating point number format is given
f is a fraction represented by a 6-bit mantissa (includes sign bit) in sign magnitude form e is a 4-bit exponent (includes sign hit) in sign magnitude form n = (f,e) = f, 2^e is a floating point number.
Let A = 54.75 in decimal and
B = 9.75 in decimal.

(a) Represent A and B as floating point numbers in the above format.
(b) Show the steps involved in floating point addition of A and B.
(c) What is the percentage error (upto one position beyond decimal point) in the addition operation in (b)?

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

The root directory of a disk should be placed

Find if the following statements in the context of software testing are TRUE or FALSE.
(S1) Statement coverage cannot guarantee execution of loops in a program under test.
(S2) Use of independent path testing criterion guarantees execution of each loop in a program under test more than once.

Which of the following requirement specifications can be validated?

(S1) If the system fails during any operation, there should not be any loss of data
(S2) The system must provide reasonable performance even under maximum load conditions
(S3) The software executable must be deployable under MS Windows 95, 2000 and XP
(S4) User interface windows must fit on a standard monitor's screen

A concurrent system consists of 3 processes using a shared resource R in a non-preemptible and mutually exclusive manner. The processes have unique priorities in the range 1.....3, 3 being the highest priority. It is required to synchronize the processes such that the resource is always allocated to the highest priority requester. The pseudo code for the system is as follows.

Shared Data 
mutex:semaphore = 1:/* initialized to 1*/
process[3]:semaphore = 0; /*all initialized to 0 */
R_requested [3]:boolean = false; /*all initialized to false */
busy: boolean = false; /*initialized to false */
Code for processes
begin process
my-priority:integer;
my-priority:=____; /*in the range 1...3*/
repeat
    request_R(my-priority);
    P (proceed [my-priority]);
    {use shared resource R}
    release_R (my-priority);
forever
end process;
Procedures
procedure request_R(priority);
P(mutex);
if busy = true then
    R_requested [priority]:=true;
else
 begin
    V(proceed [priority]);
    busy:=true;
 end
V(mutex); 

Give the pseudo code for the procedure release_R.

A program P reads and processes 1000 consecutive records from a sequential file F stored on device D without using any file system facilities. Given the following

   Size of each record = 3200 bytes
   Access time of D = 10 msecs
   Data transfer rate of D = 800 × 103 bytes/second
   CPU time to process each record = 3 msecs 

What is the elapsed time of P if
(a) F contains unblocked records and P does not use buffering?
(b) F contains unblocked records and P uses one buffer (i.e., it always reads ahead into the buffer)?
(c) records of F are organized using a blocking factor of 2 (i.e., each block on D contains two records of F) and P uses one buffer?

You may assume that the CPU time needed to transfer a record from a buffer to a local variable of P is negligible.

An operating system handles requests to resources as follows.

A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts. The timestamps are monotonically increasing with time. Let us denote the timestamp of a process P by TS(P).

When a process P requests for a resource the OS does the following:
(i) If no other process is currently holding the resource, the OS awards the resource to P.
(ii) If some process Q with TS(Q) < TS(P) is holding the resource, the OS makes P wait for the resources.
(iii) If some process Q with TS(Q) > TS(P) is holding the resource, the OS restarts Q and awards the resources to P.
(Restarting means taking back the resources held by a process, killing it and starting it again with the same timestamp)

When a process releases a resource, the process with the smallest timestamp (if any) amongst those waiting for the resource is awarded the resource.
(a) Can a deadlock ever arise? If yes, show how. If not, prove it.
(b) Can a process P ever starve? If yes, show how. If not, prove it.

Consider the following relational database schema:

     EMP (eno name, age)
     PROJ (pno name)
     INVOLVED (eno, pno) 

EMP contains information about employees. PROJ about projects and INVOLVED about which employees involved in which projects. The underlined attributes are the primary keys for the respective relations.

(a) What is the relational algebra expression containing one or more of {σ,π,x,u,−} which is equivalent to SQL query.

select eno
from EMP, INVOLVED 
where EMP.eno=INVOLVED.eno  
and INVOLVED.pno=3 

(b) State in English (in not more than 15 words).

What the following relational algebra expressions are designed to determine
(i) π_eno(INVOLVED) − π_eno((π_eno(INVOLVED) X π_pno(PROJ))−INVOLVED)
(ii) π_age(EMP) − π_EageE(EMP) x EMP))

(Note: ρ_E(EMP) conceptually makes a copy of EMP and names it K (ρ is called the rename operator))

Given the following algorithm for sorting an array X of N numbers:

SUBROUTINE SORT(X,N)
   IF(N < 2)
       RETURN
   FOR(i=2 TO N INCREMENT BY 1)
     FOR(j=1 TO i INCREMENT BY 1) 
        IF (X[i] > X[j])
             CONTINUE
        TEMP X[i]
        X[i] = X[j]
        X[j] = TEMP
        END FOR
     END FOR
   END SUBROUTINE 

A good approximation of Halstead's estimated program length is

A graphic display system has a frame buffer that is 640 pixels wide, 480 pixels high and 1 bit of color depth. If the access time for each pixel on the average is 200 nanoseconds, then the refresh rate of this frame buffer is approximately :

The period of a signal is 100 ms. Its frequency is

CMOS is a Computer Chip on the motherboard, which is :

Suppose a system has 12 instances of some resources with n processes competing for that resource. Each process may require 4 instances of the resource. The maximum value of n for which the system never enters into deadlock is

Consider the following statements related to AND-OR Search algorithm.

S₁ : A solution is a subtree that has a goal node at every leaf.
S₂ : OR nodes are analogous to the branching in a deterministic environment
S₃ : AND nodes are analogous to the branching in a non-deterministic environment.

Which one of the following is true referencing the above statements?

Choose the correct answer from the code given below:

Which homogeneous 2D matrix transforms the figure (a) on the left side to the figure (b) on the right ?

Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a web page from a remote server, assuming that the host has been restarted.

Which of the following is true for semi-dynamic environment ?

Who among the following devised the ryotwari system during the british rule in india?

Among the various electrical safety device in the options, the one based on the heating effect of electric current is the:

Consider the following statements

S1: A heuristic is admissible if it never overestimates the cost to reach the goal
S2: A heuristic is monotonous if it follows triangle inequality property.

Which one of the following is true referencing the above statements?

Choose the correct answer from the code given below:

Match the following secret key algorithm (List-1) with the corresponding key lengths (List-2) and choose the correct answer from the code given below,

   LIST-1	      List-2
a) Blow Fish	  (i) 128-256 bits
b) DES	         (ii) 128 bits
c) IDEA	        (iii) 1-448 bits
d) RC5	         (iv) 56 bits

Which of the following statement/s is/are true ?

(i) Facebook has the world’s largest Hadoop cluster.
(ii) Hadoop 2.0 allows live stream processing of real time data

Choose the correct answer from the code given below :

Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below :

(1) Input (x1,y1) and (x2,y2)
(2) y = y1
(3) d = f(x1+1, y1+½) // f is the implicit form of a line
(4) for x = x1 to x2
(5) do
(6)       plot (x,y)
(7)       if (d<0)
(8)       then
(9)           y = y+1
(10)         d = d+(y1 - y2) + (x2 - x1)
(11)     else
(12)         d = d+(y1 - y2)
(13)     end
(14) end

Which statements are true ?

P: For a line with slope m>1, we should change the outer loop in line (4) to be over y.
Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f.
R: The algorithm fails if d is ever 0.

Choose the correct answer from the code given below :

Article 45 of the constitution of india provides provision for early childhood care and education to children below the age of:

Article 26 of the constitution of india deals with:

In which of the following states is the tuluni festival celebrated?

Which team won the ICC world twenty20 2016(Men's) tournament?

The asian development bank(ADB) has approved a USD 346 million loan for road improvements in which of the following states?

In which country was the ninth edition of the mountain echoes literature festival held in august 2018?

______ can produce a virtual image larger than the object

From the given options, select the word that can be formed using the letters from the given word

ALTERNATE

Select the option that is different from the other three options

Select the options that is related to the third term in the same way as the second term is related to the first term

CEGI:XVTR::FHJL:?

Select the option that is different from the other three options

'Restaurant' is related to 'chef; in the same way as 'garage' is related to:

Choose the correct options that will complete the given number series:

2, 2, 3, 8, 35, ?, 1421

Ruby met Nisha at a party. Nisha introduced herself as the eldest daughter of the brother-in-law of Ruby's friends mother?How is Ruby's friend related to Nisha?

Five children are standing in a single file line in ascending order of their heights. Q is second in line. P and R are taller than O. N is taller than P but shorter than R. P is the middle of the line. Who is at end of the line?

If the seventh day of the month is four days after friday, what day will it be on the thirty first day of the month?

Abhi bought an article and sold it at a loss of 10%. If he had bought it for 20% less and sold it for Rs.121 more, he would have had a profit of 40%. If he decides to sell it for Rs.506, what will he percentage gain/loss be?

A shopkeeper sold an article for Rs.494 after giving a discount of 18% on its marked proce. had he NOT given the discount, he would have earned a profit of 25% on the cost price. What is the cost price(in Rs) of the article?

In folding the HCF of two numbers by the division method, the quotients are 1 and 6 respectively. If the HCF of the two numbers in 300, then their LCM will be:

Of three numbers, the first is 7 times the second and is also 4 times the third. If the average of the three numbers is 299/7 , what is the sum of the first and the third number?

A vessel contains a solution of A and B in the ratio 5:7. If 4 1/2L of the solution is replaced by the sme quality of A, then their ratio becomes 9:7. How much(in liters) of liquid B was there in the bucket initially?

There are eleven numbers whose average is 64. The first number is 4 more than second but 10 less than the third. The average of the numbers from the fourth to the seventh is 62.5, and the average of the remaining numbers is 65.5. What is the average of the second and the third number?

A bag contains coins of Rs.1, 50 paise and 25 paise in the ratio 4:3:8. If the total amount in the bag is Rs.240, then the number of 50 paise coins is:

Select the most appropriate antonym of the given word

Select the wrongly spelt word

Select the option which is NOT an antonym of another word by way of adding the prefix 'in-'.

Select the most appropriate option to fill in the blank.

Divyanshu didn't like to work at a corporate. He wants to start____ own business.

Select the most appropriate option to fill in the blank.

____ their clothes were proper, they didn't look smart.

In the following sentence, four words or phrases have been underlined. one of them is incorrect. Choose the incorrect word or phrase from the given options.

Most of the projects is struggling to make progress due to various like land acquisition, forest clearance or release of funds from the government.

Select the most appropriate synonym of the given word

Select the most appropriate option to fill in the blank.

Usually she has milk, but today she____hot herbal tea because she has a sore throat.

Select the most appropriate option to fill in the blank.

This ward is meant for critically____children.