UGC NET Paper 2: Computer Science 04th Dec 2019 (Previous Year Paper)

Data:

Memory unit = 512 K words

1 word = 32 bits = 4 B

Binary instruction code stored in 1 word of memory

Instruction divided as follows,

Calculation:

Addressing mode = 1 bit for direct or indirect

Register code = ln (256) = 8 bits

Since, registers are already addressed, only memory needs to be addressed

Address part = ln (512 K) = 19 bits

Operation mode = 32 – 1 – 8 – 19 = 4 bits

Therefore, bits for addressing mode part, opcode part, register code part and the address part = (1, 4, 8, 19)

Loop evaluation

Data:

Block size = 8192 bytes = 2¹³ bytes

Key size = 32 byte

Block pointer = 4 byte

Order of the b-tree = M

Number of keys = M – 1 

Formula:

In a B-Tree, the size of non-leaf node = M × (Block pointer) + (M – 1) × (key + Record pointer)

Calculation:

Assuming Record pointer = 0  (since nothing is mentioned about it)

Total size = M(4) + (M - 1)(32) = 36 M - 32

(142)_b + (112)_b-2 = (75)₈

b² + 4 × b + 2 + 1 × (b – 2)² + 1 × (b – 2) + 2 = 7×8 + 5

2b² + b + 6 = 61

2b² + b – 55 = 0

2b² +  11b – 10b – 55 = 0

b(2b + 11 ) – 5(2b + 11) = 0

(b – 5).(2b + 11) = 0

∴ b = 5.  

Alternate:

Option 1: b = 3

It has base 3 which is not possible because (142) having a digit 4 cannot exist in base 3.

Option 2: b = 6

(142)₆ = (62)₁₀

(112)₄ = (22)₁₀

62 + 22 = (84)₁₀

(75)₈ = (61)₁₀

Therefore 6 is not the base

Option 3: b = 7

(142)₇ = (79)₁₀

(112)₅ = (32)₁₀

79 + 32 = (111)₁₀

(75)₈ = (61)₁₀

Therefore 7 is not the base

Option_4:  b = 5

(142)₅ = (47)₁₀

(112)₃ = (14)₁₀

47 + 14 = (61)₁₀

(75)₈ = (61)₁₀

Therefore 5 is the base

Hence, (142)₅ + (112)₃ = (75)₈

Statement (a): Overloading a function gives the capability to an existing operator to operate on other data types.

This statement is incorrect. Operator overloading is a type of polymorphism in which an operator is overloaded to give a different meaning or user defined meaning. It allows to change the way an operator can work. It gives the capability to an existing operator to operate on other data types.

Statement (b): Inheritance in object-oriented programming provides support to reusability.

This statement is correct.  When a class acquires the properties of another class, this is known as inheritance. The class which acquire the properties and method is known as derived class and other one is parent or base class. Inheritance another name for reusability.

Statement (c): When object of a derived class is defined, first the constructor of derived class is executed then constructor of a base class is executed.

This statement is incorrect Constructor is a special member function of class that is automatically executed or called when objects of that class will be created. As when object of derived class is defined, automatically derived class constructor and base class constructor will execute inside them.

Statement (d): Overloading is a type of polymorphism.

This statement is correct. Operator is a type of polymorphism in which an operator is overloaded to give a different meaning or user defined meaning. It allows to change the way an operator can work.

Concept:

Post correspondence problem (PCP): It defines the un-decidability of strings. For the solution of PCP , we have to check whether there is a finite sequence (i₁,….i_p) with i_j belongs to {1,….,m} for j = 1,….p so that u_i1u_i2…u_ip = v_i1v_i2………v_ip.

Explanation:

CASE: for pair (A, B)

A = {001, 0011, 11, 101}

B = {01, 111, 111, 010}.

Consider it as: A₁ = 001, A₂ = 0011, A₃ = 11, A₄ = 101

B₁ = 01, B₂ = 111, B₃ = 111, B₄ = 010

Here A₃A₄ = B₂B₁ or A₃A₄ = B₃B₁

i.e. 11101= 11101

So, pair (A, B) has a PCP solution.

CASE 2: Consider pair (C, D)

C = {00, 001, 1000}

D = {0, 11, 011}.

There does not exist any such combination of strings which satisfy the property for PCP solution. So, Pair (C, D) does not have PCP solution.

In this scenario, first connection request is established, weather information system is requesting for the weather report.

Request takes place as:

1. Request will be sent from weather information system to sat communication.

2. sat comm is forwarding that request to weather station.

3. Then weather station sends get (summary) request to communication link

4. After that, it will fetch data from weather data.

Reply process:

1. As the communication link is nearest to weather data, first it will get the data.

2. Then it goes from comm link to weather station.

3. Then weather station to sat comm

4. At the end, weather information system get the weather information.

So, increasing order of lifeline of objects in the system will be same as objects similar or larger distance from weather data, in the way reply is gone through. So, it will be:

Weather data → Comms link → Weather station → Sat Comms

Consider it as option-wise:

1. x₁ = 750, x₂ = 750, z = 1500

Maximize z = x₁ + x₂

x₁ + 2x₂ ≤ 2000      -----(1)

x₁ + x₂ ≤ 1500      -----(2)

x₂ ≤ 600      ------  (3)

and x₁, x₂ ≥ 0

Check whether the values in the option are satisfying these equations or not.

750 + 2 × 750 < = 2000

2250 < = 2000            [false]

So, this option is not correct.

2) x₁ = 500, x₂ = 1000, z = 1500

Put value of x₁ and x₂ in equation (1).

500 + 2× 1000 < = 2000

2500 < = 2000          [False]

Option is incorrect.

3. x₁ = 1000, x₂ = 500, z = 1500

Put x₁ and x₂ in equation 1.

1000 + 2 × 500 < = 2000

2000 < = 2000 [true]

For equation (2), 1000+ 500 < = 1500            [true]

For equation (3), 500 < = 600                     [true]

For maximize z = x₁ + x₂ = 1000 + 500 = 1500 [true]

It is satisfying all equations.

4. x₁ = 900, x₂ = 600, z = 1500

Put the values in equation (1),

900 + 2× 600 < = 2000

2100 < = 2000          [False]

Option is incorrect.

Linux operating system supports both preemptive priority scheduling and time sharing CPU scheduling.

Linux scheduler is a priority preemptive scheduler with two priority ranges – Real time from 0 to 99 and a nice range from 100 to 140.

Explanation:

Preemptive priority scheduling: It maintains two array: active array and expired array.  Schedule the processes based on their static and dynamic priorities.

1.  It finds the highest priority queue with a runnable process and find the first process on that queue. Calculate its time quantum and then run. After time quantum, it put that process on expire array list and repeat the process again.

2. When priority level of active queue is empty, it looks for next highest queue, after running all active queues, it swaps active and expired queues.

Diagram:

Concept:

Javascript is a programming language for use in HTML pages. Its programs are run by interpreter built into the user’s web browser.

Explanation:

Programs in javascript language are known as scripts. It can execute both on browser and server or any device that supports special program javascript virtual machine. It has full integration with HTML/CSS.

Javascript programs can be inserted into any part of HTML document with the help of  <script > tag.

Example :

Concept:

Dijkstra’s algorithm is used to find single source shortest path i.e path between any two vertices in a graph. All edges must have non-negative weights and graph must be connected.

Explanation:

So, we get the shortest distance from a to g . (a -> b -> c -> d -> f -> g).

Concept:

Duality in Linear programming problem (LPP) : It means a linear programming problem has another LPP which is derived from it.  Original LPP is known as primal and derived LPP is known as Dual.

Explanation:

Some points about dual LPP:

1. The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.

2. If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.

3. If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all

Example:

We have a set of equations as:

Maximize z = 10x₁ + 20 x₂

Subject to:

3x₁ + 4x₂ < =100

5x₁ + 6x₂ < = 150

X₁, x₂ >= 0

Dual of this will be:

Minimize z = 100 y₁ + 150 y₂

Subject to:

3y₁ + 4y₂ >=10

5y₁ + 6y₂ > = 20

y₁, y₂ <= 0

Gantt Chart with time slice of 2ms

0        2          4          5         7          9         11       12

Process Table: (time in milliseconds)

Average TAT = $\frac{{17}}{3}$ = 5.66

Average WT = $\frac{5}{3}$ = 1.66

Given language:

\(L = \left{ {{a^n}{b^{n - 3}} |n > 2} \right}\)

It is generating strings of type = {aaa, a⁴b, a⁵b², a⁶b³, ………………….}

Now, consider all the options one by one :

Option 1: S → aA|a, A → aAb|b

This grammar is generating strings of type = {a, ab, aabb…………}. But in given language, we are not getting {a}. So, it is not generating given language.

Option 2: S → aaA|λ, A → aAb|λ 

Smallest string that is generated by this grammar is λ. But for given language it is not true, because strings are starting with aaa.

Option 3: S → aaaA|a, A → aAb|λ

In this grammar also, smallest string possible is {a} which is not required here. So, it is not generating given language.

Option 4: S → aaaA, A → aAb|λ

This grammar generates string of type = {aaa, a⁴b, a⁵b²,…….} which is same as in the given language. It generates the given language.

Concept:

Inherently ambiguous language: A context free language is inherently ambiguous if every context free grammar for that language is ambiguous.

Explanation:

If we get any one unambiguous grammar for each of the option given above, then that language will not be inherently ambiguous.

Case 1:

\({L_1} = \left{ {{a^n}{b^n}{c^m}} \right} \cup \left{ {{a^n}{b^m}{c^m}} \right},;n,;m \ge 0\)

This is inherently ambiguous language. There does not exist any unambiguous grammar for this. It is somewhat similar to the language L = {aⁱb^jc^k | i = j or j = k} . It has a common subset aⁿbⁿcⁿ.

\({L_2} = { w{w^R}|w \in \left{ {a,;b} \right}*} \) Where R represents reversible operation.

This is not inherently ambiguous language. An unambiguous grammar exists for it:

S -> aSa | bSb |  λ

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}

For 5 vertices, we need 4 edges in MST,

So, edge set for MST = {2, 3, 4, 6}

Minimum spanning tree

Minimum cost 2 + 3 + 4 + 6 = 15

In poset (z⁺, /), / is the division relation. Hence, Hasse diagram for the given POSET

A = {3, 9, 12, 36 (added)}

A with GLB = 3 and LUB = 36

B = {1, 2, 4, 5, 10, 20 (added)}

B with GLB = 1 and LUB = 20

Statement a:  Correct:

RISC has pipelined implementations with the goal of executing one instruction per machine cycle.

Statement b:  Incorrect

RISC has fixed length instruction formats

Statement c:  Incorrect

c – RISC can perform only Register to Register Arithmetic operations

Statement d:  Correct

d – RISC has efficient instruction pipeline

Therefore, statement a and d are correct.

a – Pointer variable P cannot store address of a value which is not assigned to a variable.

b – Pointer variable P can store address of variable r.

c – Integer variable P cannot store address of variable a.

d – Integer variable P can store value of variable a.

Hence int * P = &r; and int P = a; are legal statements in C programming language.

Concept:

\({\rm{Speed;up}} = \frac{{{\rm{n}}; \times ;{{\rm{t}}{\rm{n}}}}}{{\left( {{\rm{n}}; +; {\rm{k}}; - ;1} \right){{\rm{t}}{\rm{p}}}}}\)

Given:

For a non-pipelines system,

time to process a task, t_n = 30 ns

For a pipelined system,

number of segments, k = 4

clock cycle of each segment, t_p = 10 ns

For n = 100 tasks,

Calculation:

${\rm{Speed;up}} = \frac{{100; \times ;30}}{{\left( {100; + ;4; - ;1} \right)10}}$

∴ speed up = 2.91

Data:

Bandwidth = 10 Mbps = 10⁶ bps

Data network can pass on average = 12,000 frames in 60 seconds.

1 frame = 10,000 bits

Calculation:

Therefore, data network can pass in 60 seconds = 12,000 × 10,000

Throughput is data network can pass in 1 second

Throughput = $\frac{{12,000; \times ;10,000}}{{60}}$ = 2,000,000 bps = 2 Mbps.

Given:

t(x, y) = 1 – s(1 – x, 1 - y).

$t\left( {x,;y} \right) = \frac{{xy}}{{\left( {x; + ;y; - ;xy} \right)}}$ 

$s\left( {x,;y} \right) = 1 - \frac{{\left( {1; - ;x} \right)\left( {1; - ;y} \right)}}{{1; - x; + ;1; - ;y; - ;\left( {1 - x} \right)\left( {1; - ;y} \right)}}$ 

$s\left( {x,;y} \right) = 1 - \frac{{1; - ;y; - ;x; + ;xy}}{{1 ;-; x ;+; 1; - ;y; - ;1 ;+ ;y ;+ ;x; - ;xy}}$

$s\left( {x,;y} \right) = 1 - \frac{{1; - ;y; - ;x; +; xy}}{{1; - ;xy}}$

$s\left( {x,;y} \right) = \frac{{1; - ;xy; - ;1; + ;y; + ;x; - ;xy}}{{1 ;- ;xy}}$ 

$s\left( {x,;y} \right) = \frac{{x; + ;y ;- ;2xy}}{{1; -; xy}}$

Concept:

Inter process communication (IPC) is a mechanism which allows processes to communicate with each other and synchronize their actions.

By maintaining this type of communication, processes are said to so-operate with each other. Processes can communicate with each other using these two ways:

• Shared Memory
• Message passing

Data:

TLB hit ratio = 0.8

TLB miss ration = 0.2

TLB reference time = 20 ns

Main Memory reference time = 80 ns

Formula:

Effective memory access time (EMAT)

= TLB hit (TLB time + Main memory time) + TLB miss (TLB time + 2 × Main memory time)

Calculation:

EMAT = 0.8 (20 + 80) + 0.2 (20 + 80 + 80)

= 80 + 36

∴ EMAT= 116 ns

Concept:

Following are the methods used to pass parameters to the OS.

1. Registers:

Parameters are passed via registers but the limitation of this method is that the number of parameters cannot exceed the number of registers.

2.  Blocks:

When there are more parameters than registers, these parameters are stored on a main memory block and the pointer to this block (block address) is passed as a parameter to a register.

3.  Stack:

Parameters can also be pushed on and popped off the stack by the OS. This method can be used when we don’t certainly know the number of parameters beforehand.

Therefore, methods used to pass ANY NUMBER of parameters to the operating system through system calls are via block and stack. Registers cannot pass ANY NUMBER of parameters.

Explanation:

Physical layer: Concerned with transmitting raw bits over a communication channel

Physical layer is the only layer of OSI network model which actually deals with the physical connectivity of two different stations. This layer defines the hardware equipment, cabling, wiring, frequencies, pulses used to represent binary signals etc.

Transport layer: True end-to-end layer from source to destination

It is termed as an end-to-end layer because it provides a point-to-point connection rather than hop-to- hop, between the source host and destination host to deliver the services reliably.

Session layer: Provide token management service

The session layer of OSI model is responsible for establishing, managing, synchronizing and terminating sessions between end-user application processes. Through token, this layer prevents the two users to simultaneously attempt the same critical operation.

Presentation layer: Concerned with the syntax and semantics of the information transmitted

It is responsible for data encryption and decryption of sensitive data before they are transmitted over common channels.

G₁ : S → aSb|bSa|aa

gives a language G₁ = {number of a = number of b + 2}

G₂ : S → aSb|bSa|SS|λ

gives a language G₂ = {number of a = number of b}

G₃ : S → aSb|bSa|SS|a

gives a language G₃ = {number of a > = number of b + 1}

G₄: S → aSb|bSa|SS|SSS|λ

gives a language G₄ = {number of a = number of b}

Hence, G₂ and G₄ are equivalent.

Statement S₁: L² is context free language – True

L² means L.L which will give the language {aⁿbⁿ aⁿbⁿ |n≥ 0} and this is context free language.

Statement S₂: L^k is context-free language for any given k ≥ 1 – True

L^k is context-free language because CFLs are closed under kleene closure.

Statement S₃: L̅ and L* are context free languages – True

L̅ is a DCFL because L is a DCFL. L̅ is a language that accepts all inputs on a and b except aⁿbⁿ and this is easily determined by a PDA.

L* is a CFL because CFLs are closed under kleene closure.

Important Point:

Deterministic Context free language is closed under complementation

To encrypt any message, any encryption algorithms necessarily require

1. Plain text (message)
2. Key (private or public)

Encryption algorithm doesn’t require Ciphertext, it produces ciphertext.

To decrypt any message, any decryption algorithms necessarily require

1. Ciphertext
2. Key (private or public)

No encryption or decryption algorithm requires user details.

Therefore, more appropriate answer is 4.

Data:

Degree of 2n vertices = 1

Degree of 3n vertices = 2

Degree of n vertices = 3

Formula

Handshaking theorem:

Sum of the degree of vertices = 2 × number of edges(E)

In a tree, number of edges(E) = number of vertices – 1

Calculation

Using 1^st formula,

2n × 1 + 3n × 2 + n×3 = 2E

11n = 2E

$E = \frac{{11}}{2};n$

E = 2n + 3n + n – 1

E = 6n – 1

Comparing above two equations for E,

$\frac{{11}}{2}n = 6n - 1$

11n = 12n – 2

n = 2

number of vertices = 6n = 12

number of Edges = 12 – 1 = 11

Micro operation: Elementary operation performed on data stored in registers

In computer central processing units, micro-operations (also known as micro-ops) are the functional or atomic, operations of a processor. These are low level instructions used in some designs to implement complex machine instructions.

Micro programmed control unit: Control Memory

To execute an instruction, the control unit of the CPU must generate the required control signal in the proper sequence. Micro programmed control unit fetches microinstructions from the control memory.

Interrupts: Improve CPU utilization

Interrupts are important because they give the user better control over the computer.

Micro instruction: Specify micro operations

A collection of micro instructions perform a specific micro operation.

Data:

Remaining Need = Maximum need – Current need

Total resources = 12

Total resources allocated = 5 + 2 + 2 = 9

Available resources = 12 – 9 = 3

Calculation:

Available resource ≥ remaining need of p₁

Using 3 resources, p₁ gets executed first. It frees 2 resources.

Available resources = 3 + 2 = 5

Available resource ≥ remaining need of p₀

Using 5 resources, p₀ gets executed first. It frees 5 resources.

Available resources = 5 + 5 = 10

Available resource ≥ remaining need of p₂

Now, p₂ can be executed easily. Hence, (p₁, p₀, p₂) is a safe sequence.

Concept:

To understand pre-emptive scheduling, we first need to understand the process state diagram.

Scheduling is performed from when the process is taken from ready state on to the running state.

Hence, CPU scheduling decisions take place under one of four conditions,

1. Process switch from Running state to Waiting state.
2. Process switch from Running state to Ready state. (Statement a)
3. Process switch from Waiting state to ready state. (Statement b)
4. Process termination.

Statement c – No need for preemptive scheduling as execution is complete.

Statement d – Process cannot switch from Ready state to Waiting state.

Given grammar is generating string of type: {0, 000, 00000,0000000…...}

1. L((00) * 0 + (11) * 1)

This language generating string with combination of 0’s and 1’s. But given grammar is not generating any string composed of 1’s.

2. L(0(11) * + 1(00) * )

This language is not generating string which contains three 0’s together. Also, it is generating strings which contains 1 in it. So, it is not correct option.

3. L((00) * 0)

It is generating strings of type: {0, 0³, 0⁵, 0⁷,.}. These set of strings is similar to the one generating from given grammar. So, this language is generated by given grammar.

4. L(0(11) * 1)

It is incorrect because it is generating strings which contains 1 which is not the case with given grammar.

P = {(01101), (11000), (01000), (10011)}

Also, strength of fitness of a chromosome in decimal form, x is given by:

$Sf\left( x \right) = \frac{{f\left( x \right)}}{{\sum f\left( x \right)}};where;;f\left( x \right) = {x^2}$ 

So, first convert the population in decimal form, then find f(x).

We have to find the strength of fitness of chromosome 11000.

11000 in decimal = 24, f(24) = 576

$Sf\left( x \right) = \frac{{576}}{{169; + ;576; + ;64; + ;361}}$ 

Sf(x) = 576/1170

Sf(x) = 0.492

(a) The running time of dynamic programming algorithm is alway θ (ρ) where ρ is number of subproblems.

This statement is incorrect. Running time for dynamic algorithm is the number of subproblems multiplies with time for each subproblem. It means running time of dynamic programming algorithm is O(1).

(b) When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.

Cyclic dependency is relation between two or more modules which depends on each other indirectly or directly, these are mutually recursive. So, given statement is correct.

(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization.

This statement is incorrect. For a dynamic programming algorithm, computing all values using recursion and memorization takes less time than computing in bottom- up fashion.

(d) If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.

If a problem X can be reduced to a known NP hard problem, then X must be NP complete not NP hard. SO, given statement is incorrect.

R is a relation on P such that (a, b) is in R if a is a brother of b.

Case 1: check symmetric relation

(a, b) – a is the brother of b

(b, a) – b may or may not be brother of a.

So, given relation is not symmetric.

Case 2: Check transitivity

If a is the brother of b, b is the brother of c, then a will also be brother of c.

It means if (a, b) and (b, c) then (a, c).

So, given relation is transitive.

Case 3: Equivalence

As relation is not symmetric, so it cannot be equivalence relation.

Case 4: Partial order relation

For this, we have to check anti-symmetric property.

i.e. if (a, b) is in relation than (b, a) should not be in relation unless a = b. Here, it is not partial order relation.

Line clipping: It involves clipping of lines which are outside the window line.

Explanation:

From above given options line clipping algorithms are:

Cohen- Sutherland algorithm:  It cuts lines to portions which are within a rectangular area. It eliminates those lines which are outside the view port and clip those lines which are partially inside and partially outside of view port. To clip a line, we must have the endpoints. Region code in cohen – Sutherland algorithm is:

Two cases are there: trivial acceptance and trivial rejection. If both end points are inside the window, then trivially accepted. If both end points lie entirely to one side, or outside of window. Then trivially rejected otherwise clip the line.

Liang Barsky algorithm: It uses four computations to find the appropriate end points of a line. It is based on floating point arithmetic. It uses parametric equations for the line.

Nichole-Lee-NicholI algorithm: It divides the clipping window into separate areas and matches the start point area code to one of those areas. Imaginary lines are drawn to all the edges of the window and based on these imaginary lines, line is clipped.

During transpose of the matrix, it is partitioned into 4 submatrices of size N/2.

If n = 1, then T(1) = 1

Else T₁(n) = 4T₁(N/2) + O(1)       ----- (1)

Solving equation 1 by master’s theorem:

${n^{log_b^a}} = ;{n^{log_2^4}} = {n^2}$, here a= 4 and b = 2

So, T₁(n) = O(N²)

But the algorithm is multithreaded, and transposing is going in parallel. And we solved one subproblem already.

So, T_n(N) = T_n(N/2) + O(1)

T_n(N) becomes O(log N)

asymptotic parallelism of the algorithm:

T₁/T_∞ or θ (N²/lg N)

Concept:

Java virtual machine is component of technology for its hardware and operating system independence, the small size of its compiled code and its ability to protect users from malicious programs.

Explanation:

Java virtual machine is an abstract computing machine. Like a real computing machine, it has an instructions set and manipulated various memory areas at run time.

• Java virtual machine knows nothing of java programming language, only of  a particular binary format, the class file format.
• A class file contains JVM instructions or bytecodes and a symbol table, as well as other information.
• JVM imposes strong syntactical and structural constraints on code in a class file.
• Class loader and interpreter is needed by JVM to execute Java code.
• Basic structure in JVM are: heap store, stack, method area, runtime constant pools, PC.

There are five objects among whom the message will be exchanged :

These are:

1. Customer

2. Person who takes the order

3. Chef

4. Serving person

5. Cashier

Process with the help of diagram is:

Concept:

Context free grammar : A grammar G = (V, T ,S, P) is said to be context- free if all productions in P have the form A -> x where A ϵ V and x ϵ (V U T)^*.

Explanation:

If context free grammar G = (V, T, S, P) is without λ-productions or unit productions.

K = maximum number of symbols on right side of production.

The maximum number of production rules for equivalent grammar in CNF:

(K - 1)|P| + |T|

A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions:

1. Should not contains null or unit productions.

2. A non-terminal symbol generating two non-terminals. For example, S -> AB

3. A non- terminal generating a terminal. Example: S -> a

(a) Message confidentiality means that the sender and the receiver expect privacy.

Message confidentiality means that only sender and intended receiver should be able to access the contents of a message. Confidentiality gets compromised if an unauthorized person is able to access a message. It means sender and receiver expect privacy.

(b) Message integrity means that the data must arrive at the receiver exactly as they were sent.

When the contents of a message are changed after the sender sends it, but before it reaches the intended recipient, we say that the integrity of the message is lost. It means that the data must arrive at the receiver exactly as they were sent.

(c) Message authentication means the receiver is ensured that the message is coming from the intended sender.

Authentication mechanisms help establish proof of identities. The authentication process ensures that the origin of an electronic message or document is correctly identified. It means that receiver is ensured that the message is coming from the intended sender.

Concept:

Learning algorithms: These algorithms are used in machine learning to help technology in human learning process. It is used to process data to extract patterns appropriate for application in a new system.

Explanation:

From above given options, only a) and b) are learning algorithms.

a) Logistic regression: It is used for binary classification problems. It is used to examine and describe the relationship between a binary variable and set of predicator variables.  The primary objective of logistic regression is to model the mean of the response variables, given a set or predicator variables.

b) Back propagation: It is the essence of neural net training. It is the method of fine tuning the weights of a neural net based on the error rate obtained in the previous iteration. It is a standard method of training artificial neural networks.

Micro instruction format: It consists of two fields of micro-operation. One field from conditions, one for branch field and one is address field.

Explanation:

Micro operation field into two subfields containing 15 micro operations each.

Condition field: 4 status bits

Branch: 4 options in conjunction with address

So, bits required for microoperations = log₂15 + log₂15 = 4 + 4 = 8

Condition = log₂4 = 2

Branch in conjunction with address field = log₂(4 × 128) = log₂ 512 = 9

Size of micro – instruction = 8 + 2 + 9 = 19 bits

Given query is:

             Select count (*) total

             from EMPLOYEE where DEPTNO IN (D1, D2)

             group by DEPTNO

having count (*) >5

STEP 1: It will first find the all the entries with department no. as D1 and D2 with the help of natural join from both the relations.

STEP 2: Then in the resulting table, it groups the tuples with the department no. (DEPTNO)

STEP3: Then select all those tuples having count > 5.

STEP 4: Finally, it results in the total number of employees of department D1 and D2 if their total is > 5.

(a) Microsoft Azure is a cloud-based operating system.

This statement is correct. Microsoft Azure is a cloud-based operating system which enables running of business applications, services and workload in the cloud itself. It mainly deals with the foundation of running applications and keeping the data on the cloud.

(b) Google App Engine is an integrated set of online services for consumers to communicate and share with others.

Google app engine is PaaS (Platform as a service) product. It provides web developing services to developers. Apps must be written in java or python.  So, this statement is incorrect.

(c) Amazon Cloud Front is a web service content delivery.

Amazon cloud front is a fast content delivery network service that securely delivers data, video, applications and APIs to customers. Cloud front is integrated with AWS global infrastructure and services. So, statement is correct.

Problems that can occur during concurrent execution of two transactions in an uncontrolled manner:

a) Lost update problem:  Lost update problem occurs when two transactions that access the same database items have their operations interleaved in a way that makes the value of some database item incorrect.

b) Dirty read problem: It occurs when a transaction is allowed to retrieve or update a record that has been updated by another transaction. Because it has not yet been committed, there is always a possibility that it will never be committed but rather rollback.

d) Inconsistent database state: It occurs when a transaction reads several values, but a second transaction updates some of these values during the execution of first. This causes an inconsistency. For example: if one transaction is calculating an aggregate summary function on a number of records while other transactions are updating some of records.

Step 1:

Step 2:

Step 3:

Step 4:

The value of root node become 17.

S₁: If a group (G, *) is of order n, and a ∈ G is such that a^m = e for some integer m ≤ n, then m must divide n.

Given statement is correct. As a ∈ G , is such that a^m = e for some integer m<=n, then it means it is a subgroup of G and m is the order of a. where order of given group is n. By the property of subgroup or Lagrange’s theorem, a order of subgroup divides the order of a group. So, here m must divide n is true.

S₂: If a group (G, *) is of even order, then there must be an element a ∈ G such that a ≠ e and a * a = e

This statement is correct.  Consider an example for this : Consider G is of order 2n. There exists a ∈ G such that a^p = e and p divides 2n. Let n = pq. So, (aⁿ)² = (a^pq)² = ((a^p)^q)² = (e^q)² = e . It means aⁿ is an element which satisfy the condition and a =! e. Here, a is non trivial subgroup of G.

Concept:

In link state and distance vector routing, every router has to save some information about other routers. When network size grows, the number of routers in network increases. Due to this, routers can’t handle network traffic efficiently. That’s why there comes a need of hierarchical routing.

Explanation:

In hierarchical routing, routers are classified in groups known as regions. In three level hierarchical routing, network is classified into a number of clusters. Each cluster is made up of number of regions and each region contain number of routers.

Given: number of routers = 720

Clusters = 8

Regions = 9 of 10 routers

Total number of entries in hierarchical table of each router = (number of clusters – 1) + (number of regions - 1) + routers in each region

= (8 - 1) + (9 - 1) + 10 = 7 + 8 + 10 = 25

CPM (critical path method) models the activities and events of a project as a network. Activities are identified as nodes and events that signify the start and end of activities are denoted as edges between nodes.  CPM provides a graphical view of the project. It predicts the time required to complete the project.

• Main aim of CPM is to determine the minimum completion time for a project
• It uses forward and backward pas routines to analyse the project network
• It monitors the progress of project on basis of network schedule.
• In CPM, critical path is the longest sequence of dependent tasks and it defines project duration.
• During forward pass, it is assumed that each activity will begin at its earlies starting time.
• During backward pass, it is assumed that each activity begins at its latest completion time

Steps of CPM project planning:

1. Specification of individual activities and determining the sequence of those activities.

2. Then draw network diagram as directed graph.

3. Estimation of completion time for each activity.

4. Then identify the critical path or longest path through the network

5. Finally update the CPM as the project progresses.

Concept:

Bluetooth is a wireless LAN technology designed to connect devices of different functions. A Bluetooth LAN is an ad hoc network which means that the network is formed spontaneously; devices sometimes called gadgets, find each other and make a network called piconet.

Explanation:

Bluetooth defines two types of networks: piconet and scatternet

PICONET: A Bluetooth network is called piconet or small net. A piconet can have up to eight stations one of which is called primary and rest are secondaries. All the secondary stations synchronize their clocks and hopping sequence with the primary.  Communication between primary and secondary can be one to one or one to many. A piconet can have a maximum of 7 secondaries.

Diagram:

1. Scrum model: It is an agile project management methodology which articulates a set of values and principles to guide decisions on how to develop high quality software. It is related with sprint backlog. Sprint backlog is a list of tasks identified by scrum team to be completed during scrum sprint.

2. Adaptive software development: It is a design principle for creation of software systems. It focuses on rapid creation and evolution of software. It is a series of three steps: speculate, collaborate and learn. It considers <action> the <result> <by/for/of/to> a(n) <object>.

3. Extreme programming: It is a methodology designed to improve the quality of software. It uses CRC modelling which includes CRC cards that divided into three sections: class name, responsibilities and collaborators.

4. Feature driven development: It is a client centric and pragmatic software process. Features are an important aspect of feature driven development. A feature is a small, client valued function expressed in the form. It is based on time box release plan as time boxing is used as project planning technique.

Concept:

In hill climbing algorithm, at each point in the search path, a successor node that appears to lead most quickly to the top of the hill or goal is selected for exploration.

In this method of searching, the generate and test method is augmented by a heuristic foundation which measures the closeness of the current state to the goal state.

Explanation:

Problems in hill climbing are:

1. Local maximum: It is a state which is better than all of its neighbours but is not better than some other states which are farther away. Solution of this problem is backtracking.

2. Plateau: It is a flat area of search space in which a whole set of neighbouring states have the same value. On a plateau, it is not possible to determine the best direction in which to move.

3. Ridge:  It is an area of search space which is higher than the surrounding areas and that itself has a slope.

ISO 9126 software quality model has six quality characteristics: functionality, reliability, usability, efficiency, maintainability, portability.

1. Functionality: This characteristic is related with the achievement of purpose. It is the essential purpose of any product. It is expressed as a total of essential functions that the software product provides.

2. Reliability: It is capability of software to maintain performance of software. Fault tolerance is one of the aspects of the characteristic. Fault tolerance is the ability of a system to withstand component failure.

3. Efficiency: It is relationship between level of performance and amount of resources. Amount of disk space, memory, network etc. are part of this characteristic.

4. Maintainability: It is the ability to identify and fix a fault within a software component. It is related with the efforts needed to make for improvement in software.

Concept:

There are many plans that a database management system can follow to process a query, but it is the amount of time that they need to run is given importance. For this, query optimization is required.

Explanation:

Query optimization examines all algebraic expressions that are equivalent to the given query and chooses the one that is estimated to be the cheapest.

• Query optimization procedures either attempt to maximize the output for a given a number of resources or to minimize the resource usage for a given output.
• It tries the minimize the response time for a given query language.
• It does rearrangement and possible ordering of operations, eliminate redundancy in query.
• In order to allow fair comparison of efficiency, the functional capabilities of the query evaluation systems to be compared must be similar.

Given:

Rectangle is bound by the lines x =0 , y = 0 , x = 5 and y = 3.

We follow the pattern of

Steps:

1. As P lies in the left of window. So region for this will be : 0001

2. Q point lies in the top of the window, So, region for this will be : 1000

3. Logical AND of 0001 AND 1000 = 0000 i.e. line is partially inside the window.

4. Slope of the line PQ = (5-0)/(4-(-1)) = 5/5 = 1

5. Now, we have to find the coordinates of P’ , Slope of P’Q’ is same as slope of PQ.

6. So, we have to find the y coordinate as x coordinate is 0.

(5- y’)/(4-0) = 1 , 5- y’ = 4, y’ = 1

Coordinates of P’ will be (0,1).

7. Next we have to find the coordinates of point Q’. For this , y coordinate we already know. i.e. 3

8. So, (5 - 3)/ (4- x’) = 1 , 2 = 4 – x’ , x’ = 2

Coordinates of point Q’ will be (2,3).

So, The line segment joining (-1, 0) and (4, 5), if clipped against this window will connect the points (0,1 ) and (2, 3).

Concept:

Homomorphism is a function from strings to string that is based on the concatenation. For any x and y ϵ Σ^*, h(xy) = h(x)h(y)

Explanation:

L is the regular language with the regular expression r = (w + x*)(ww)*

Then h(L) = (h(w) + h(x))(h(w)h(w))

Given: h(x) = xzy

h(w) = zxyy

h(L) = (zxyy + (xzy))(zxyy zxyy)

S₁: ∀x P(x) ∨ ∀xQ(x) and ∀x(P(x) ∨ Q(x)) are not logically equivalent.

This statement is correct. Consider an example: x – is a number. P(x) denotes x is even and Q(x) denotes x is odd. 

∀x P(x) ∨ ∀xQ(x)- it means for all numbers x is even or for all numbers x is odd.

∀x(P(x) ∨ Q(x)) – it means for all x, x is either odd or even.

From this, it is clear that both these are not logically equivalent.

S₂: ∃x P(x) ∧ ∃x Q(x) and ∃x (P(x) ∧ Q(x)) are not logically equivalent

This statement is correct.  Consider the same example as of first case.

∃x P(x) ∧ ∃x Q(x) – It means there exists a number which is odd and there exists a number which is even also which is true.

∃x (P(x) ∧ Q(x))- It means, there exists a number which is both even and odd which is not possible. It is false.

So, these are not logically equivalent.

Concept:

A binary coded decimal code in which the combination for the complement of a digit is the complement of the combination for that digit.

Explanation:

Self-complementing codes are: excess-3 code, and 2421 code.

1. 2421 code: It is positive weighted code. Values in binary terms for each digit from 0 to 9 are given as :

2. Excess -3 code: It is a non-weighted code and self-complementary code. It is derived from 8421 code by adding 3 to each digit.

Concept:

In raster scan system, electron beam move across the screen one row at a time from top to bottom. In this, electron beam intensity is turned on and off to produce illumination on the screen.

Explanation:

There are two approaches used in area filling on raster systems: one is scan line algorithm and another is seed fill algorithm.

1. Scan line algorithm: determine the overlap intervals for scan lines that cross the area or scan line. A scan line is a line of pixels that are plotted on display device when electron beam scans the display area horizontally.

2. Seed fill algorithm: It starts from interior position and point outward from this point until the boundary condition reached. In this, a point is selected and then four or eight connected approaches is used to fill it.

Dempster – Shafer theory: It is designed to deal with the distinction between uncertainty and ignorance. Rather than computing the probability of a proposition it computes the probability that evidence supports the proposition.

Rather than estimating probabilities it uses belief intervals to estimate how close the evidence is to determining the truth of a hypothesis.  It allows representation of ignorance about support provided by evidence.

• Belief or possibility is the probability that B is provable by the evidence.
• Plausibility is the probability that B is compatible with the available evidence.
• According to Dempster – shafer theory (Bel A) = 1 – Bel (¬A)

For example: if there are three groups A, B and C who did the crime. We may have evidence the group

C is guilty. We would not want to say the probability of other two groups being guilty is 1. Belief and

Disbelief are functional opposites. Dempster –shafer theory allows to leave relative beliefs unspecified.

Given values are: d[v] = 29

d[u] = 15

where d[x] represents the current shortest distance from source S to node x.

w[u, v] = 12

Representation in graph form:

From graph it is clear that, source node s to node v path is also described as: s -> u -> v

Cost of this path = 15 + 12 = 27

So, update value of d[v] = 27

     C1A5 =1100 0001 1010 0101

& 93C6 = 1001 0011 1100 0110

      8184 = 1000 0001 1000 0100

The content of accumulator register in hexadecimal after the execution of the program is 8184

Important Point:

In instruction address in mentioned not data

Rules for finding a minimum number of tables required for an ER diagram:

1. A strong entity with single or composite attributes requires one table.

2. A strong entity with multivalued attributes requires two tables.

3. In the case of many to many relations between two entities, 3 tables are required.

Explanation:

There is one to many relationships between R₁and R₂. So, two tables are required for two entities. But, entity R₁ contains multivalued attribute B, due to which one table for this is also needed.

Here we have 1 to Many relation so we requires two tables.

Attribute B being multi-valued, we need to remove the multi-valued attribute B to convert the given entity-relationship diagram into a relational database.

As relational database do not allow multi-valued attributes. We have to introduce a new table.

So, the number of tables is as below:

R1

R12R2

A table for B (Multi-valued attribute)

So, a total of 3 tables are required for the given entity relational diagram.

So, option 3 is the correct answer.

(a) Fiber optic cable i**s much lighter than copper cable

Given statement is correct. Fibre optic cable transmit signal in the form of light pulses. They can transmit data at higher speed than copper cables and these are lighter than copper cables. Also, fibre optic cable have higher bandwidth.

(b) Fiber optic cable is not affected by power surges or electromagnetic interference

This statement is correct. Fibre optic cables are non metallic and they transmit signal in the form of light pulses. That’s why they are immune to electromagnetic interference. Integrity of signal is not affected by electrical noise.

(c) Optical transmission is inherently bidirectional.

This statement is incorrect. Two optical modules are connected by single fibre cable which supports unidirectional communication. For bi- directional communication, two cables will be required.

Mamdani model*:* In a Mamdani system, output of each rule is a fuzzy set. These are well suited to expert system applications where the rules are created from human expert knowledge. It is a method to create a control system by synthesizing a set of linguistic control rules obtained from experienced human operators.

Takagi – Sugeno-Kang model : This model allows to construct  the system of analysis from a set of example data. These are used for the approximation of a large class of non – linear systems. The degree of relevance of a linear model is determined by the degree the input data belongs to fuzzy subspace associated with the linear model. This is an example of additive rule model.

Kosko’s additive model (SAM) :  It assumes the inputs are crisp and uses the scaling method. It uses addition to combine the conclusion of fuzzy rules and includes the centroid defuzzification technique.

Concept:

A schema is a set of binary strings that match the template which is made up of 1’s , 0’s and *s where * matches with either 0 or 1. The order of schema is the number of its fixed bits i.e. number of bits that that are either 0 or 1.

Explanation:

Given schema is: ?10?101? and ???0??1

CASE 1:

For ?10?101?, number of bits  that are either 0 or 1 are 5.

So, order of this schema is 5.

CASE 2:

For ???0??1, number of bits that are fixed are 2. So, order of schema is 2.

Concept:

Direct address: Address field contains the effective address of operand.

Register indirect: Address field of instruction refers to CPU that contains effective address.

Relative addressing: Effective address = next instruction address + address part(direct)

Index addressing: Effective address = content of index register + address part of instruction

Explanation:

Instruction is stored at location 500 with address field at 501 with value 400.

So, direct address will be 400.

Register indirect address will be 200.

Relative addressing mode = 502 + 400 = 902

Index addressing = 200 + 400 = 600

7¹⁷mod561

= 7((7⁴)²)²)mod561

= 7((2401)²)²)mod561

= 7((157)²)²)mod561 [2401 mod 561 ≡ 157]

= 7(24649)²mod561 

= 7(−35)² [∵24649mod561 ≡ 526 ≡ −35]

= 7(1225)mod561

= 7(103)mod561

= 721mod561

= 160

S₁ : These exists no algorithm for deciding if any two Turing machines M₁ and M₂ accept the same language.

Equivalence problem for recursive enumerable language is undecidable which means there does not exist any algorithm to decide if two Turing machine accept the same language or not. If it were decidable, there will be algorithm to decide the acceptance of a string by a Turing machine and problem of whether the language accepted by Turing machine is empty.

S₂: Let M₁ and M₂ be arbitrary Turing machines. The problem to determine L(M₁) ⊆ L(M₂) is undecidable.

It is correct. Subset problem for Turing machine is undecidable. There can exists a problem which is accepted by Turing machine M₂ but not by Turing machine M_1. The problem to determine L(M₁) ⊆ L(M₂) is undecidable.

Aspect ratio of an image = width/height

Here we have given a image with size 1024 × 768 pixels.

Width = 1024 pixels

Height = 768 pixels

Aspect ratio = 1024/768 = 4/3

Also, width changes to 640 pixels while aspect ratio remain same.

So, $\frac{4}{3} = \frac{{640}}{{height}}$

${\rm{height}} = \frac{{640; \times ;3}}{4} = 480{\rm{;pixels}}$

Height of resized image will be 480 pixels.

$T\left( n \right) = 4T\left( {√ n } \right) + lo{g^2}n$

Consider n = 2^m

m = log₂n

n = 2m

Taking square root

√n = 2m/2

T(2^m) = 4T(2^m/2) + m²

Put S(m) = T (2^m/2)

S(m) = 4 S(m/2) + m²

Comparing with

T(m) = a T(m/k) + cmk

a = 4, b = 2, k = 2

a = b^k = 4

Now use master’s theorem :

T(m) = O(mklog m)

So, Time complexity will be O(m²log m)

Put the value of m

Time complexity will be :  O (log²n log (logn))

Concept:

Object of Derived class cannot access any member of Base class directly. So it cannot access public, protected as well as private members directly.

Therefore, Object of derived class B can access public base class data is false.

Concepts:

V(S): Signal operation will increment the semaphore variable, that is, S++.

P(S): Wait operation will decrement the semaphore variable., that is, S--.

Data:

Initial counting semaphore = I = 8

Wait operation = 3 P

Signal operation = 4 V

Final(current) counting semaphore = F

Formula:

F = I + 4V + 3P

Calculation:

F = 8 + 4(+1) + 3(-1)

∴ F = 9

the resulting value of the semaphore is 9

Let F(A, B, C) = AB + AB̅ + A̅C + AC

F(A, B, C) = A(B + B̅) + (A̅ + A).C

F(A, B, C) = A + C     ...(∵  A + A̅ = 1  and 1.A = A)

Since the minimized Boolean expression does not contain Boolean variable B.

Therefore, F(A, B, C) is unaffected by the value of the Boolean variable B

ICANN stands for internet corporation for assigned names and numbers. It is formed as an international multi- stakeholder organization responsible for the coordination policies related to domain name system which are:

• Related to the unique assignment of internet domain names.
• Assignment of IP address, protocol port numbers.
• Coordinated the DNS root server system

Its aim is to ensure the stable and secure operation of the internet’s unique identifier systems. It

promotes competition and choice for registrants, especially in the generic top-level domain area and

develop policies appropriate to its mission through bottom up, consensus-based processes

Concept:

Data encryption standard (DES) is a block cipher that encrypts data in blocks of size 64 bits each. That is 64 bits of plain text goes input to the DES which produces 64 bit of cipher text. Key length is 56 bits.

Explanation:

Broad level steps of DES are:

• In first step, 64 – bit plain text block is handed over to initial permutation.
• Next , initial permutation (IP) produces two halves of permuted block, say left plain text and right plain text
• Now, each LPT and RPT go through 16 rounds of encryption process each with its own key.
• At the end, LPT and RPT are re-joined and a final permutation is performed on combined block.

Each of the 16 rounds, in turn consists of these steps:

During expansion permutation, it goes to S- box substitution after doing XOR of 48 bit key with 48 bit right plain text. S- Box produces the 32-bit output using substitution technique. Then a straight permutation is done. These 32 bits are permuted using P- box.

Concept:

A natural join is based on common attributes or common columns to join two tables or relations.

Explanation:

Consider an example, suppose there are two tables Employee(Eid, Ename) consists of 5 tuples and department(Eid, Did) consists of 3 tuples only.

Natural join of employee and department(Employee * Department) gives:

5 × 3 = 15

So, maximum number of tuples in natural join are from the relation having minimum tuples. So, in given question, R2 contains 30 tuples, so , maximum number of tuples in the output of natural join between tables R1 and R2 i.e. R1 * R2 = 50 × 30 = 1500.