UGC NET (Computer Science) Official Paper (Held On 11 Nov, 2020) (Previous Year Paper)

Concept:

• A design solution is said to be highly modular if the different modules in the solution have high cohesion and their inter-module couplings are low.
• Cohesion is like a type of ranking which is used to measure the degree of modules that are functionally related

The degree of Cohesion can be defined as

Therefore B → C → E → D → A is the correct order

Additional Information

Logical cohesion:

A module is said to be logically cohesive, if all elements of the module perform similar operations, such as error handling, data input, data output, etc.

Example of logical cohesion

consider a module that contains a set of print functions to generate various types of output reports such as grade sheets, salary slips, annual reports, etc.

 

Sequential Cohesion:

An element outputs some data that becomes the input for other elements, i.e., data flow between the parts. It occurs naturally in functional programming languages.

 

Temporal Cohesion:

The elements are related by their timing involved. A module connected with temporal cohesion all the tasks must be executed in the same time-span. This cohesion contains the code for initializing all the parts of the system. Lots of different activities occur, all at init time.

 

Communicational Cohesion:

Two elements operate on the same input data or contribute towards the same output data. Example- update record in the database and send it to the printer.

 

Procedural Cohesion:

Elements of procedural cohesion ensure the order of execution. Actions are still weakly connected and unlikely to be reusable. Ex- calculate student GPA, print student record, calculate cumulative GPA, print cumulative GPA.

The correct answer is option 4

Explanation:

1. (R ∧ E) ⟺ C says that all (and only) conservatives are radical and electable. So, this assertion is not true.

2. R ⇒ (E ⇔ C) says that same as the given assertion. This is a correct assertion.

3. R ⇒ ((C ⇒ E) V ¬E) = ¬R∨(¬C∨E∨ ¬E) which is true for all interpretations. This is not a correct assertion.

4. ( ¬ R V ¬ E V C) ∧ (¬ R V ¬ C V E) = (¬ RV( E⇒ C)) ∧ (¬ R V (C ⇒ E)) = R ⇒ (E ⇔ C) which is equivalent to assertion B. This is also true.

The correct answer is option2

Explanation:

For C and E to be true, the assertion should be P(c) ∧ Q(c). Hence, this is not a correct inference

Additional Information

In predicate logic, universal generalization states that if ⊢P(x)⊢P(x)⊢P(x) {\displaystyle \vdash !P(x)}

has been derived, then ⊢∀xP(x)⊢∀xP(x)⊢∀xP(x) {\displaystyle \vdash !\forall x,P(x)}

can be derived.

The correct answer is option 4

K-maps

F(A, B, C, D) = ∑ (0, 1, 2, 3, 6, 12, 13, 14, 15)

Two K-Maps can be constructed from the given boolean function

The expression for K-Map 1 is AB + A'B' + A'CD'

The expression for K-Map 2 is AB +A'B' + BCD'

The correct answer is option 1

Key Points

Caesar Cipher:

• It is one of the simplest techniques for encryption where each letter of a given text is replaced by a letter some fixed number of positions down the alphabet.
• For example, the text "ABC" can be encrypted using the Ceasar Cipher technique as "CDE". Here the shift (number of positions shifted) is 2.

Diffie-Hellman algorithm:

• Diffie-Hellman algorithm is used for the exchange of secret key over an insecure channel.
• Once the key is shared by both the sender and receiver, then the communication is done using the shared symmetric keys.

Data:

TLB hit ratio = p = 0.8

TLB access time = 15 nanoseconds

Memory access time = m = 150 milliseconds

Formula:

EMAT = p × (t + m) + (1 – p) × (t + m + m)

Calculation:

EMAT = 0.8 × (15 + 150) + (1 – 0.8) × (15 + 150 + 150)

EMAT = 195 nanoseconds.

Important points:

During TLB hit

Frame number is fetched from the TLB (15 ms)

and page is fetched from physical memory (150 ms)

During TLB miss

TLB no entry matches (15 ms)

Frame number is fetched from the physical memory (150 ms)

and pages are fetched from physical memory (150 ms)

Concept:

Speed up factor is defined as the ratio of time required for non-pipelined execution to that of time received for pipelined execution.

Data:

Time for non-pipelined execution per task = t_n = 50 ns

Time for pipelined execution per task =  tp = 10 ns

Number of stages in the pipeline = k = 6

Number of tasks = 500

Formula

$S = \frac{{{T_n}}}{{{T_p}}}$

S = speed up factor

Calculation:

Time for non-pipelined = Tn = t_n × Number of tasks

Time for non-pipelined = T_n =  50 × 500

Time for pipelined = Tp​ = 1st task × k × t_p + (All Remaining Tasks (k - 1)) × t_p

Time for pipelined = Tp​ =  1 × 6 × 10 + (500 - 1) × 10

$S = \frac{{T_n}}{{T_p}} = 4.95$

The correct answer is option 1

Both statement l and statement ll are correct

Solution:

Statement l: 5 divides n⁵ - n

Using mathematical Induction, if n⁵ - n is divisible by 5, then (n+1)⁵ - (n+1) is also divisible by 5.

If 5 divides, n⁵ - n = 5.k

(n+1)⁵ - (n+1) = n⁵ + 5n⁴ + 10n³ + 10n² + 5n - n

                       = 5.k + 5( n⁴ + 2n³ + 2n² +n)

This shows that (n+1)⁵ - (n+1) is a multiple of 5. Hence it is always divisible by 5.

Statement ll: 6 divides n³ - n

n³ - n = n (n² - 1)

          = n (n + 1)(n - 1)

Here n, n + 1, and n-1 are three consecutive integers. One of them is a multiple of 2 and the other is a multiple of 3. Hence 6 divides n³ - n is always divisible by 6 whenever n is a non-negative integer.

The correct answer is option 1

Key Points

Virtualization is a technique where multiple operating systems run simultaneously on a single machine virtually.

These machines can be accessed remotely by different users at the same time.

Here, the same hardware like memory and CPU are utilized by all the operating systems in a systematic manner.

Additional Information

Virtual Memory:

• In computers, the size of the main memory is very less compared to the size of the secondary memory.
• This limits the size of the program and the degree of concurrency.
• The concept of virtual memory is developed to address this problem.
• Here the entire secondary memory can be accessed just like main memory using page replacement algorithms.

The correct answer is option 2

Explanation:

L(r) = {a, aa, ab, aaa, aab, .... } This is a set of all strings starting with 'a'

L(s) = {aa, ab, aaa, aab, .... } This is a set of all strings starting with 'aa' or 'ab'

L(t) = {ab, aab, aaab, aaaab, ...} This a set of all strings starting with 'a', ending with 'b' and contains any number of 'a's in between them.

Therefore L(r) ⊇ L(s) ⊇ L(t)

Additional Information

• represents 0 or more number of symbols.

• represents 1 or more number of symbols.

The correct answer is option 3

Explanation:

fork() is a system call used to create a child process.

Once a child process is created, both the parent process and the child process run the next line following the fork() command simultaneously.

'n' number of successive for() calls create 2ⁿ - 1 child processes.

in P1:

Each child process prints one "Happy".

Parent process also prints one "Happy".

So, number of times P1 displays "Happy" = (2³ - 1) + 1 = 8

In P2:

At first fork(), a new child process with two fork() and printf statements is created.

Similarly, more child processes are created at each fork() command.

So, P2 shows "Happy" 14 (2 + 4 + 8 )times.

The correct answer is option 3

Explanation:

Statement l: Correct

Undirected graphs do not have cross edges in Depth First Search. But there can be cross edges in directed graphs. This statement is true.

Statement ll: InCorrect

In Breadth-First Search, an edge can be present between vertices of the same level. So,  | i - j | = 0. This statement is false.

The correct answer is option 3.

Key Points

A hash function is defined as any function that can be used to map data of the arbitrary size of data to fixed-size data.

Definition of hash function Statement 1 is correct and Statement 1 is incorrect.

 A hash function may give the same hash value for distinct messages. Yes, it's true. If N%10 is a Hash function. It gives the same values for 101, 11,21,31 as 1.

Hence statement C is correct.

∴ Hence the correct answer is (A) and (C) only.

The correct answer is option 2.

Key Points

Given data, Functional Point=864

team=6 persons

average each peson(FP) productivity=12

designer month salary=70000

programmers month salary=2x60000

tester month salary=2x60000

Requirement gatherer=50000

Projected cost of project=?

Total number of months=$\frac{Functional Point(FP)}{(Team \times Average each person (FP) productivity)}$= $\frac{864}{6\times12}$

=12 months

Total cost of the project=(one designer salary+2 x Programmer month salary+2 x tester month salary+one requirement gatherer) x total number of months

=(70000+2x60000+2x60000+50000)x12

=43,20,000

∴ Hence the correct answer is Rs. 43,20,000.

The correct answer is option 1.

Key Points

Pipelining: Overlapping execution- parallelism improves performance. The aim of using pipelining is to use a single clock per instruction (CPI) which automatically improves performance.

Statement A is true:

$S = {{tn} \over tp} \$ if we assume that the time it takes to process a task is the same in the pipeline and pipelined circuits, we will have tn = kt_p. Including this assumption, the speedup reduces to $S = {{ktp} \over tp} \$=k

This shows that the theoretical maximum speedup that a pipeline can provide is k, where k is the number of segments in the pipeline.

Statement B True:

K × efficiency =speedup

The speedup can not be equals to K till efficiency becomes 1 and in real-time environment efficiency can not become 1 of many reasons like the delay at intermediate buffers, different times taken by different segments to perform their sub-operations which cause all other segments to waste time while waiting for the next clock.

Statement C False: Because different segments can take different times to complete their sub-operations.

Hence the correct answer is (A) and (B) only.

The correct answer is option 3.

Key Points

Corrective, adaptive, perfective, and preventive maintenance are the four forms of maintenance.

• Corrective maintenance focuses on resolving issues that arise when the programme is in operation.
• Adaptive maintenance is concerned with the changes made to the software in order to make it adaptable to new environments, such as running it on a new operating system.
• The term "perfective maintenance" refers to the changes in the software that occur as a result of adding new features.
• Preventive maintenance entails making adjustments to avoid mistakes from occurring. The following graph shows the distribution of maintenance types by type and percentage of time spent.

∴ Hence the correct answer is Perfective maintenance.

The correct answer is option 4.

Key Points

Topological sort of DAG= O(V + E)

Bellman-Ford's single-source shortest path algorithm=O(VE)

Floyd-Warshall's all-pairs shortest path algorithm= θ(V3)

Kruskal's MST algorithm= θ (V + E)

Due to sorting the edges, the dominant term in Kruskal's time complexity is O(ElogE). However, if we can conduct sorting in linear time or if the edges are already sorted, the problem can be solved by detecting whether there is a cycle in the graph or not. Since the edges have already been sorted, add each edge to MST one by one.

It is now possible to determine whether or not an undirected graph has a cycle:

1)   select one among DFT or BFT:- O(V+E)

2)   Using Union-Find:- O(ElogV)

 ∴ Kruskal’s MST algorithm :-  θ(V+E)

∴ Hence the correct answer is A - I, B - III, C - II, D - IV.

The correct answer is option 2

Explanation:

Lexicographic order is nothing but dictionary order.

To determine the order of strings, we need to compare each bit of all the strings one by one.

For example, take 001 and 010. Here, the second bits of the strings are 0, 1 respectively.

Since 0 < 1 as per the given question, 001<010.

Similarly, 0001 < 001 < 010 < 0101 < 011

Alternate Method

Replace 0 with A and 1 with B and follow dictionary order 

AAAB<AAB<ABA<ABAB<ABB

The correct answer is option 4

Explanation

Since  a > 1 and a < b

int x=0 , int p=1

Let us assume a=2 and b=15

Whenever the loop is entered, the value of p is doubled and the value of x is incremented by 1.

In iteration 1: p = 2, x = 1

In iteration 2: p = 4, x = 2

In iteration 3: p = 8, x = 3

In Iteration 4: p = 16, x = 4

Final values are a = 2, b = 15, p = 16, x = 4

From the above values, it can be seen that x =[loga**b]

The correct answer is option 3.

Key Points

Statement (A): Minimax search is breadth-first: it processes all the nodes at a level before moving to a node in the next level. But it is a depth-first search.

Hence the statement A is False.

Statement (B):  The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined.

Yes. It depends on which children are visited first. It's likely that no pruning happens if a node's children are visited in the worst possible order. We want to visit the best child first for max nodes so that time is not lost on the other children who are exploring worse scenarios. We want to start with the worst child when it comes to min nodes.

Hence the statement B is true.

Statement C: The alpha-beta search algorithm computes the same optimal moves as the minimax algorithm.

True, it prunes nodes that have no bearing on the final outcome.

Hence the statement C is true.

Statement D: Optimal play in games of imperfect information does not require reasoning about the current and future belief states of each player.

False, it necessitates.

Hence the statement D is False.

The correct answer is option 3.

Key Points

Initial (chaotic, ad hoc, individual heroics) - the stage at which a new or undocumented repeat mechanism may be used.

**Repeatable -**At the very least, the procedure is well recorded such that the same steps can be tried again.

Defined - As a normal business procedure, the process has been described and verified.

Managed (Capable)- The method is handled quantitatively according to agreed-upon metrics.

Optimizing (Efficient)- process management includes deliberate process optimization.

∴Hence the correct answer is A-IV, B - III, C - II, D - I.

Additional Information

The correct answer is option 4.

Key Points

Edge set consists of edges from i to j, using either two conditions are j = i + 1 or j = 3i

Second choice helps us to move from 1 to 100. The trick to slot this is to think the other way around. Try to find a 100 to 1 trail, instead of having a 1 trail to 100.

So, the edge sequence with the minimum number of edges is

1 → 3 → 9 → 10 → 11 → 33 → 99 → 100

which consists of 7 edges.

Hence the correct answer is 7.

The correct answer is option 1 and option 3.

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.

Key Points

 

The final sequence will be (a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e) with a cost 37.  

Another final sequence is (a, b), (a, h), (g, h), (f, g), (c, f), (c, i), (c, d), (d, e) with a cost is 37(Two sequences possible ).

The correct answer is option 3.

Key Points

A multiprocessor is a computer system having two or more processing units i.e multiple processors each sharing main memory and peripherals, in order to simultaneously process programs.

• Multiprocessor systems are controlled by one or more operating systems. Hence Statement I is correct.
• In a Multiprocessor system, multiple processors are connected under single computer systems. Hence Statement II is incorrect.
• Multiprocessor system is classified as multiple instruction streams and multiple data streams systems. Hence Statement III is correct.

​∴ Hence the correct answer is (A) and (C) only.

The correct answer is option 2.

Key Points

• Serial Line Internet Protocol (SLIP) is a Data Link layer simple protocol that works with TCP/IP for communication over serial ports and routers. They provide communications between machines that were previously configured for direct communication with each other.
• Border Gateway Protocol (BGP) is a Network layer used to exchange routing information for the internet and is the protocol used between ISP which are different ASes.
• User Datagram Protocol (UDP) is a Transport Layer protocol. UDP is a part of the Internet Protocol suite, referred to as UDP/IP suite. Unlike TCP, it is an unreliable and connectionless protocol.
• SNMP is an application layer protocol that uses UDP port number 161/162.SNMP is used to monitor the network, detect network faults and sometimes even used to configure remote devices

∴ Hence the correct answer is A-III, B -IV, C -II, D -I.

Additional Information

The correct answer is option 4.

Key Points

Option A: ((p → r) ∧ (q → r)) and ((p ∨ q) → r)

Both are equal and it gives the same truth table. Hence it is logically equivalent. 

Option B:  p ↔ q and (¬ p ↔ ¬ q)

(p → q)(q → p) and (¬ p → q)(¬ q →p)

(p+q̅)(q+p̅) and (p+q̅)(q+p̅)

Both are equal and it gives the same truth table. Hence it is logically equivalent. 

Option C:  (p → q) ∧ (q → p) and p ↔ q 

Both tables give equal values. Hence it is logically equivalent.

Option D: ((p ∧ q) → r ) and ((p → r) ∧ (q → r))

The above truth table is not equivalent. Hence the above statement is True, Logically not equivalent. 

∴ Hence the correct answer is  ((p ∧ q) → r ) and ((p → r) ∧ (q → r)).

The correct answer is option 4.

Key Points

The relationship of entailment between sentences is crucial to our understanding of reasoning. A sentence α entails another sentence β if β is true in all world where α  is true. Equivalent definitions include the validity of the sentence α⇒β and the unsatisfiability of sentence α∧¬β.

Hence statement I is False.

For information bases in Horn form True, forward and backward chaining is rather normal reasoning algorithms. These are very natural algorithms that run in linear time.

Hence statement II is True.

Both sentences that are entailed False are derived by sound inference algorithms (it is complete not sound) If only sentences entailed by Knowledge Base are derived, the inference algorithm is sound.

Hence statement III is False.

Propositional logic does not scale to unbounded conditions. That is right. Propositional logic is relatively efficient for certain tasks within an agent, but it does not scale to unbounded environments because it lacks the descriptive capacity to deal concisely with time, space, and universal patterns of object relationships.

Hence statement IV is True.

∴ Hence the correct answer is (B) and (D) only.

The correct answer is option 1.

Key Points

(A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).(O = big O)

True,

Big-Oh(O) denotes upper bound or worst case. 

Big-Omega(Ω) denotes lower bound or best case.

Big-Theta(Θ)  denotes Average bound or average case.

(B) its worst-case running time is Ω(g(n)) and its best-case running time is O(g(n)).(O = big O)

False, worst case should be Big-oh and best case should be Big-Omega

(C) O(g(n)) = Ω(g(n))(O = big O)

False, Can not cover  Big-Omega.

(D) O(g(n)) ∩ ω(g(n)) is non-empty set. (o = small o)

False, no such f(n) exists, i.e. the intersection is indeed the empty set.

∴ Hence the correct answer is (A) only.

The correct answer is option 3.

Key Points

Both data points would be in a straight line if the correlation between the variables V1 and V2 is 1. As a result, all three cluster centroids will form a straight line.

∴ Hence the Statement I is correct but Statement II is false.

Additional Information

K-Means Clustering is an unsupervised learning algorithm used in machine learning and data science to tackle clustering problems.   Unsupervised Learning algorithm K-Means Clustering divides the unlabeled dataset into separate clusters. K specifies the number of pre-defined clusters that must be generated during the process; for example, if K=2, two clusters will be created, and if K=3, three clusters will be created.

The correct answer is option 1.

Key Points

Noiseless channel: Nyquist Bit Rate

For a noiseless channel, the Nyquist bit rate formula defines the theoretical maximum bit rate

BitRate=2 X bandwidth x10g2L

In this formula, bandwidth is the bandwidth of the channel, L is the number of signals used to represent data, and BitRate is the bit rate in bits per second.

Noisy channel: Shannon Capacity

In the reality, we cannot have a noiseless channel; the channel is always noisy. In 1844, Claude Shannon introduced a formula, called the Shannon capacity, to determine the theoretical highest data rate for a noisy channel:

Capacity= bandwidth x log2(1+SNR)

In this formula, bandwidth is the bandwidth of the channel, SNR is the signal-to-noise ratio, and capacity is the capacity of the channel in bits per second. Note that in the Shannon formula there is no indication of the signal level, which means that no matter how many levels we have, we cannot achieve a data rate higher than the capacity of the channel. In other words, the formula defines the characteristics of the channel, not the method of transmission. 

∴ Hence both Statement I and Statement II are true the correct answer.

The correct answer is option 3.

Key Points

• Any tree is 2-colourable. True every tree is no loops and a bipartite graph with chromatic number 2. Odd levels coloured with one colour and even levels coloured with another colour.

• A graph G has no cycles of even length if it is bipartite. False

• A graph G is 2-colourable if is bipartite True. A graph K(2,3), set of  V₁ vertices coloured with one colour and set of V₂ vertices coloured with another colour.

• A graph G can be coloured with d+1 colours if d is the maximum degree of any vertex in the graph G.True as the vertex of degree d means it is adjacent to d vertices hence need d+1 different colours required.

• A graph G can be coloured with O(log∣v∣) colours if it has O(∣v∣) degrees False as Kn has O(n^2) edges with chromatic number n so it needs O (√ V) colours

∴ Hence the correct answer is (B) and (E) are incorrect.

The correct answer is option 1.

Key Points

• Greedy best-first search algorithm always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms.
• Time complexity: The worst-case time complexity of the greedy best-first search is O(b^m).
• Space Complexity: The worst-case space complexity of the greedy best-first search is O(b^m). Where m is the maximum depth of the serach space
• Complete: Greedy best-first search is also incomplete, even if the state space is finite.
• Optimal: Greedy best-first search algorithm is not optimal.
• A* is optimal and complete but time complexity and space complexity too high. It requires more computation.
• Recursive Best-First Search retents more memory knowledge but uses only O(bd) memory
• Memory Simplified Bound A* such as A* Optimal if you can get optimal solution otherwise as it is memory-bound.

∴ Hence the correct answer is A - II, B - IV, C - I, D - III.

The correct answer is option 3.

Key Points

The frames must be held before they are used if the date of the frames arrives at the receiver side faster than they can be processed. The receiver, in most cases, does not have enough storage space, particularly if it is receiving data from multiple sources. Frames may be discarded or service may be denied as a result of this. To keep the receiver from being overloaded by the frames, we need to tell the sender to slow down. This can only be achieved by input from the receiver to the sender.

The protocol we'll talk about now is called Stop and Wait because the sender sends one frame, then waits for confirmation from the receiver before sensing the next frame. Although data frames still require unidirectional communication, axillary acknowledgement frames travel in the opposite direction.

∴ Hence the correct answer is Simplex stop and wait protocols.

The correct answer is option 4.

Key Points

 The Bezier curve is defined by P0 through Pn and n is named its order (n = 1 for the linear, 2 for the quadratic, etc.). The first and last checkpoints are often the endpoints of the curve, but interim checkpoints do not usually lie on the curve.

Statement I is incorrect

The cubic Bezier curve is defined by four points P0, P1, P2, and P3 in the plane or in greater space.

Statement II is correct.

A cubic bezier curve has four control points.

The correct answer is option 2.

Key Points

f(x) = x is my friend

P(x) = x is perfect

So, they are asking about SOME. Finally, outer most parentheses will get SOME ∃x.

They are given conditions like NOT perfect. So,we get  ¬ p(x).

The final condition is ∃x (f(x) ∧ ¬ p(x))

∴ Hence the correct answer is ∃x (f(x) ∧ ¬ p(x)).

The correct answer is option 3.

Key Points

(a+b)* is a universal set grammer which can generate all strings over all possible alphabet "a"and"b".

(a* + b)= a can generate epsilon, and reamaining part is like (a + b)*

(a + b)=(a + b*)=(ab)=(a+ b)^* =a(ba)=b(ab)=(a + b)* all grammers are equal.

∴ Hence the correct answer is L1 = L2.

The correct answer is option 2.

Key Points

Two functions are said to be incompatible if any of the following conditions are met:

• They are associated with various transactions.
• They both work with the same data object.
• One of them must be a write operation.

If you note the issues mentioned below, it's because different transactions have performed at least one write operation on the same data object.

a) Item X has an incorrect value because its update by T1is lost(overwritten).

b) Transaction T1 fails and must change the value of X back to its old value; meanwhile, T2 has read the temporary incorrect value of x.

 

c)T3 reads X after N is subtracted and reads Y before N is added; a wrong summary is a result(off by N).

∴ Hence the correct answer is (A), (B) and (C) only

The correct answer is option 4.

Key Points

A is ambiguous because λ can be generated using leftmost derivation having two different parse trees with an empty string.

B is ambiguous grammar with string abab.

C is an ambiguous grammar with string abbbb.

∴ Hence the correct answer is (A) (B) and (C).

Data:

Period = T = 100 ms

Formula:

${\rm{Frequency;f}} = \frac{1}{{\rm{T}}}{\rm{;}}$

Calculation:                        

${\rm{f}} = \frac{1}{{100{\rm{;ms}}}} = \frac{1}{{100 × {{10}^{ - 3}}{\rm{s}}}} = 10{\rm{;}}{{\rm{s}}^{ - 1}} = 10{\rm{;Hertz}}$

f = 10 × 10^-3 kilohertz = 10^-2  kilohertz

The correct answer is option 3.

Key Points

 L̅REC ∪ LRE  = (Recursive  ∪ Recursively enumerable)=  Recursively enumerable

Recursive languages closed under complement so,  L̅REC is Recursive. Union of recursive and recursively enumerable is recursively enumerable.

L̅CF ∪ LREC    = (not Context-free ∪ Recursive ) =(Recursive ∪ Recursive)= Recursive.

Context-free is not closed for a complement so, L̅CF is Recursive.  The union of recursive and recursive is recursive.

LR ∩ LCF         = (Regular ∩ Context Free ) = Context Free.

The intersection of regular and context-free is Context Free.

∴ Hence the correct answer is A - I, B - II, C - III.

Additional Information

The correct answer is option 4.

Concept:

A candidate key is a column, or set of columns, in a table that can uniquely identify any database record without referring to any other data

Explanation:

The following functional dependencies,

U → V, VW → X, Y → W, X → U

S = (U, V, W, X, Y, Z)

Here YZ is an independent key. So, for every key, the YZ should their. Hence only option 4 is containing YZ for all keys.

∴ Hence the correct answer is UYZ, VYZ, XYZ.

 

Options Verify:

The correct answer is option 3. 

Data:

p = 3, q = 11 and d = 7

Formula:

Φ(n)=(p-1)x(q-1)

n=p x q

Calculation:

n=3 x 11 =33

Φ(n)==(3-1)x(11-1) = 20

ex7 mod Φ(n)=1

Option 3

if e=3, 7x3 mod 20 =1

Encrypt key M^emod n= C

C=19³mod 33

C=28

∴ Hence the correct answer is (3,28)

 

RSA Algorithm (Rivest Shamir Adleman):

• Step 1: choose two large primes, p,q
• Step 2: Compute n=pxq , Φ(n)=(p-1)x(q-1)
• Step 3: Choose a number relatively prime to Φ(n) and call it 'd' , GCD(d, Φ(n))=1
• Find 'e' such that, exd mod Φ(n)=1
• Encrypt key M^emod n= C where C=ciper text
• Decrypt key C^dmod n= M where M=plain text

The correct answer is option 1.

Key Points

Control signals are provided by a hardwired circuit in hardwired control techniques. The main goal of the control unit is to produce the control signal in the correct order. The speed of a hardwired control unit can be optimized.

Hence statement I is correct

 Indirect addressing mode needs two memory references to fetch operand as the address of the operand is not given in instruction but the address field contains the address where the address of the operand is stored.

Hence statement II is correct.

​

Additional Information

• Advantages of Hardwired Control unit:
• ​It is faster than the microprogrammed control unit.​
• It can be optimized to produce a fast mode of operation.
• Disadvantages of Hardwired control unit:
• ​Instruction set, the control logic is directly implemented.
• Requires a change in the wiring if the design has to be controlled.
• An occurrence of an error is more.
• It requires a more chip area, therefore, it is a costlier control unit.

The correct answer is option 4.

Key Points

R1 U R2 (union) is the relation containing all tuples that appear in R1, R2, or both. 

                     R1 ∪ R2= R1 or R2= R₁+R₂- R1 ∩ R2 

                             R1 ∪ R2 =  {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)}​

 R1 - R2 (set difference) is the relation containing all tuples of R1 that do not appear in R2

                    R1 - R2 =  R1 -R1 ∩ R2 

                    R1 - R2= {(2, 2), (3, 3)}

R1 ∩ R2 (intersection) is the relation containing all tuples that appear in both R1 and R2.

                   R1 ∩ R2 = R₁and R₂=  {1, 1}​                   

 R2 - R1 (set difference) is the relation containing all tuples of R2 that do not appear in R1

                   R2 - R1=R2 -R1 ∩ R2  = {(1, 2), (1, 3), (1, 4)}

∴ Hence the correct answer is A - I, B - IV, C - II, D - III.

The correct answer is option 3.

Key Points

Handshaking:

When one computer sends a message to another indicating that it wants to create a contact channel, it is called handshaking.  It requires two control signals working in opposite directions

Programmed I/O:

​​The output of the I/O instructions written in the computer programme is the trigger. It requires the CPU to check the I/O   flag & perform the transfer

Interrupt-initiated I/O:

Interrupt powered I/O is a different way to deal with I/O. Interrupt I/O is a method of monitoring input/output operation by sending a signal from a peripheral or terminal that needs to send or receive data. I/O interface informs the CPU that the device is ready for transfer

I/O processor:

A processor with direct memory access is known as an input-output processor (IOP). The computer system is divided into memory units and processors in this way. I/O processor has local memory & control a large set of I/O devices.

∴ Hence the correct answer is A-II, B - IV, C - I, D - II.

The correct answer is option 3

Formula:

The total cost of the project = Total development cost + Total maintenance cost

Calculation:

Let p1 be the LOC using L1 and p2 be the LOC using L2.

Total cost of the project using L1 = (p1/1000) x 70,000 + (10 x 1,00,000) = 70p1 + 10,00,000

Total cost of the project using L2 = (p2/1000) x 90,000 + (10 x 40,000) = 90p2 + 4,00,000

Given that p2 = 3xp1

=>70p1 + 10,00,000 = 90p2 + 4,00,000

=>70p1 + 10,00,000 = 270p1 + 4,00,000

=> 200p1 = 6,00,000

=> p1 = 3000

The correct answer is option1

Key Points

• Context-free language is closed under Union, Concatenation, and Kleen closure. But not closed under complementation and intersection.
• If a Language is Context Free, it can be either deterministic or non-deterministic language. only deterministic languages are accepted by the deterministic pushdown automaton.
• Let L1 and L2 be Context-free language

Option 1: 

L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct

The correct answer is option 4.

Key Points

3 pages of physical memory mean 3 frames (so at a time only max 3 pages in  frames)

5 pages of  virtual memory mean 5 page

 FIFO (First In, First Out)

    The operating system uses this algorithm to keep track of all pages in memory in a queue, with the oldest page at the top. When a page has to be replaced, the first page in the queue is chosen for replacement.

Page faults= A B C  D A  B E  C D  B A 

Page faults= 11

Least Recently Used –

   In this algorithm, the page will be replaced which is the least recently used.

Page faults=  A B C D A B E C D E B A

Page faults= 12

 

∴ Hence the correct answer is (11, 12).

The correct answer is option 4.

Key Points

If one solve the quadratic equation, ax2 + bx + c

then the sum of roots of quadratic equation = −b/a

Quadratic equation x2 - 10x + 26 = 0

since 4 and 7 are the roots of the equation

∴ $\frac{-b}{a} = \frac{(10)_r}{(1)_r} = (4)_r + (7)_r$

r = 4 + 7 = 11

∴ Hence the correct answer is 11.

Alternate Method

In this case, it would be sufficient to take one solution and put it into the equation. Say we do it with x=4. Convert the coefficients into base 10. Let the radix be r.

x2 - 10x + 26 = 0

(4)2 – (1 × r1 + 0 × r0) × 4 + (2 × r1 + 6 × r0)=0 

16 − 4r + 2r + 6 = 0

2r = 22

r = 11

The correct answer is option 2.

Key PointsUML (Unified Modeling Language) diagrams can be categorized into two main types: structural diagrams (which present a static view of the system) and behavioral diagrams (which represent the dynamic aspects).

• Collaboration diagram – Represents interactions between objects or parts in terms of sequenced messages. It is a kind of behavioral diagram.
• Use-Case diagram – Represents the functionality provided by a system in terms of actors, their goals represented as use cases, and any dependencies between those use cases. It is a kind of structural diagram, providing a static view of the system's functionality.
• State chart diagram – Shows how an object changes its state in response to events. It is a type of behavioral diagram.
• Activity diagram – Represents workflows of stepwise activities and actions with support for choice, iteration and concurrency. It is considered a behavioral diagram.

Therefore, the diagram that represents a static view among the options listed is the Use-Case diagram.

The correct answer is option 3.

Key Points

• The execution time of a programme is the time that a processor spends actually executing the program's instructions.
• The second kind of time is calendar time It is the familiar time that we normally experience.
• Clock time is the normal wall clock time.

and Software reliability is described with respect to all these.

∴ Hence the correct answer is (A), (B) and (C).

Additional Information

Software reliability, like hardware reliability, is defined as the probability that the software system will work without failure under specified conditions and for a specified period of time.

The correct answer is option 3.

Key Points

Statement 1: FALSE: 

Gouraud shading requires less calculation and this greatly decreases the cost of shading steeply. 

Statement 2: TRUE:

Gouraud shading linearly interpolates the color of an interior pixel from the color at the vertices. The original paper makes it clear Gouraud shading is a linear interpolation of colour between vertices, specifically.

Statement 3:TRUE:

Phong shading interpolates over the normal vectors specified at the vertices.

∴ Hence the correct answer is (B) and (C) only.

The correct answer is option 4.

Key Points

Here, there are six copies of the same book into four identical boxes(same box). We will enumerate all ways to pack the books. For each way to pack the books, we will list the number of books in the box with the largest number of books, followed by the numbers of books in each box containing at least one book, in order of decreasing the number of books in abox

6,0,0,0 

5,1,0,0

4,2,0,0

4,1,1,0

3,3,0,0

3,2,1,0

3,1,1,1

2,2,2,0

2,2,1,1.

So the total number of ways is 9.

∴ Hence the correct answer is 9.

The correct answer is option 3.

Key Points

• L1 will first contain 0's followed by an equal number of 1's. After that, there will be a single 2 which will again be followed by 0's and an equal number of 1's i.e.   L1={2,012,00112,20011,01201,0011201,0120011,001120011,........}
• L2={epsilon,0,1,2,01,12,012,00112,20011,01201,0011201,0120011,001120011,............}
• L=L1∩L2={2,012,00112,0001112,........}
• L=L1∩L2={0^m1^m2/ m>=0}, which is a context free language but not regular language.

∴ Hence the correct answer is Context-free but not regular.

Additional Information

The correct answer is option 4.

Key Points

Network layer Firewall can filter on Source And Destination IP address, Source and Destination Port no for both TCP and UDP packet.

​∴ Hence the correct answer is (A), (B), (C), (D), and (E) only.​

Additional Information

What is a Firewall?

            A firewall is a form of cybersecurity device that filters network traffic. Network nodes can be separated from external traffic sources, internal traffic sources, or even individual applications using firewalls.

The correct answer is option 1.

Key Points

A genetic algorithm is a stochastic hill-climbing algorithm that maintains a wide population of states. Mutation and crossover, which blends pairs of states from the population, create new states.

Hence Statement I is correct.

Agents may use AND-OR search in non-deterministic environments to produce contingent plans that achieve the target regardless of which outcomes occur during execution.

Hence Statement II is correct

​

Additional Information

• AND-OR search trees: 
• ​OR nodes: The only branching in a deterministic setting is implemented by the agent's own choices in each state; we call these nodes OR nodes.
• AND nodes: Branching is often implemented in a non-deterministic setting by the environment's choice of outcome for each action, which we call nodes AND nodes.

The correct answer is option 1

Key Points

The main difference between NameNode and DataNode in Hadoop is that the NameNode is the master node in Hadoop Distributed File System (HDFS) that manages the file system metadata while the DataNode is a slave node in Hadoop distributed file system that stores the actual data as instructed by the NameNode.

Additional Information

• NameNode stores the metadata of all files in HDFS. Metadata includes file permission, names, and location of each block. Namenode maps these blocks to DataNodes.
• The data nodes store and retrieve blocks as instructed by the NameNode.

The correct answer is option 3.

Key Points

If the tree is 1-ary and 'I' is an internal node, the number of leaves is 1

If the tree is 2-ary and  'I' is an internal node, the number of leaves is I+1

If the tree is 3-ary and 'I' is an internal node, the number of leaves is 2I+1

If the tree is 4-ary and  'I' is an internal node, the number of leaves is 3I+1

If the tree is 5-ary and 'I' is an internal node, the number of leaves is 4I+1

If the tree is n-ary and  'I' is an internal node, the number of leaves is (n-1)I+1

Given that leaves L= 41, internal nodes I=10

L=(n-1)I+1

41=10(n-1)+1

10n=50

n=5 

∴ Hence the correct answer is 5.

 

Internal nodes  I=10

Leaf nodes  L=41

In an n-ary tree, the levels start at 0 and there are n^k nodes at each level, where k is the level number.

Total number of nodes−L=I

(1+n¹+n²+⋯+n^K)−L=I

(1+n¹+n²+⋯+n^K)−41=10

(n¹+n²+⋯+n^K)=50

 $\frac{n(n^K−1)}{n-1}$=50

Option verify, if n=3, nK=35 is not equal to leaves.

if n=4, nK=39 is not equal to leaves.

if n=5, nK=41 is equal to leaves. So, it is 5-ary tree.

if n=6, nK=43 is not equal to leaves.

The correct answer is option 4.

Key Points

\(\left[ {\begin{array}{*{20}{c}} 2&0&0\ 0&2&0\ 0&0&1 \end{array}} \right]\) It is the scaling matrix. 2 in x and y-direction by a factor,

Hence A-II is the correct pair.

\(\left[ {\begin{array}{*{20}{c}} 1&0&2\ 0&1&2\ 0&0&1 \end{array}} \right]\) is the translation matrix. Vector 2 in each direction of x and y

Hence  B-IV is the correct pair

\(\left[ {\begin{array}{*{20}{c}} {0.5}&{ - 0.866}&0\ {0.866}&{0.5}&0\ 0&0&1 \end{array}} \right]\)is an angle of 60 degrees rotation matrix.

Hence  C-III is the correct pair

\(\left[ {\begin{array}{*{20}{c}} 1&2&0\ 0&1&0\ 0&0&1 \end{array}} \right]\)is the shear matrix of quantity 2 with only x-shear.

Hence  D-I is the correct pair

∴ Hence the correct answer is A-II, B - IV, C - III, D - I.

The correct answer is option 4.

Explanation

 

(9CE2)₁₆ = (1001 1100 1110 0010)₂

1's complement of (9CE2)16 = (0110 0011 0001 1101)₂ = (631D)₁₆

(631D)16 & (1235)₁₆ = (0215)₁₆

Hence the correct answer is 0215H.

The correct answer is option 1.

Key Points

Arrange one below the other the XOR operations

For correcting, the d-bit error hamming distance should be 2d+1.

So,2d+1=5

d=2

It means the hamming distance between the codeword 0000000111 and gives option should be 2-bits. Only Option 1 matches.

Option verify:

                                                                                                                           

0000011111 is minimum with the 2-bit error.

∴ Hence the correct answer is 0000011111.

The correct answer is option 1.

Key Points

• Under perspective projection, each set of parallel lines in the object do not stay parallel in the image The lines converge to the middle of the projection at a single point. Points of intersection of converging lines with the screen plane generate the projected image on the screen.

           Hence statement I is correct.

• Applying a perspective transformation in the graphics pipeline to a vertex involves dividing by its 'z' coordinate.

           Hence statement II is correct.

• Perspective transformation is a non-linear transformation.​

           Hence statement III is incorrect.

The correct answer is option 1.

 

Key Points

Direct Mapping: 

Given Data,

Main memory size =216 bytes

No of blocks in Main memory (M)=216  ÷ 23

Block Size (P)= 23 bytes

No of blocks in the cache memory (N) =25 bytes 

Tag=2⁸=Tag bits= log2(M/N)

line or cache block= 2⁵ =cache block  bits= log₂^N

word field or word offset= 2³=word offset bits=log2P^​

∴ Hence the correct answer is (8,5,3).

Important Points

N = No of blocks in cache memory  =(cache memory size)/Block size

M=  No of blocks in main memory   = (main memory size)/Block size

P=Block size

The correct answer is option 1.

Key Points

 The behavioral model indicates how the software will respond to external events. To create the model, the analyst must perform the following steps.

1. Evaluate all use-cases to fully understand the sequence of interaction within the system.
2. Identify events that drive the interaction sequence and understand how these events relate to specific objects.
3. Create a sequence for each use-case
4. Build a state diagram for the system
5. Review the behavioral model to verify accuracy and consistency.

∴ Hence the correct answer is (A), (B) and (C) only.

The correct answer is option4

Only the language L2 is regular.

Key Points

\({L_1} = { {a^{{{̇ z}^z}}}|̇ Z;is;an;integer} \)

∴ L₁ = {a¹, a^4, a²⁷, a²⁵⁶, .....}

L2 = {azż | Ż ≥ 0}

∴ L₂ = {ε, a¹¹, a²², a³³, ......}

L3 = {ωω | ω ϵ {a, b}* }

L₃ = set of all strings starting and ending with the same word.

Explanation:

L₁ does not contain any pattern to form a loop. Hence it's not possible to construct a DFA for L1.

L₂ is a regular language since a DFA can be constructed using a loop that after every 11 symbols, the automata reaches the final state.

In L₂, once the word 'ω' is scanned, there is no way to compare the next word with the starting symbol of the first word.

The correct answer is option 1.

Key Points

The function f(1,3) pass the values to m,n. Then the value will typecast to float and result=0.3333. Then it enters into else statement the function f is f(2,9). 

And finally it returns result as 0.20000003.

∴ Hence the correct answer is 0.2.

The correct answer is option 3.

Key Points

• "alignment rules" that "require the address of every primitive data element to be an even multiple of the element’s size". It's not very interesting that we're talking about alignment rules; we knew that already.
• "require the address" of "every primitive data element" to be "an even multiple of the element’s size". Now we're getting somewhere. We have a requirement and a scope:
• Requirement: The address is an even multiple of the element's size.
• Scope: Every primitive data element.
• So, every time we position an element, we must impose the requirement. It may also mean "even" as in "integral" rather than "multiple of two"

That would make the array:

 

In that case, you have 24 bytes per element for a total of 240 bytes. Again, you need padding to ensure that r is aligned correctly.

∴ Hence the correct answer is 240 bytes.

The correct answer is option 3.

Key Points

E-R diagrams and their corresponding descriptions.

The correct answer is option 1

Key Points

In Boolean Logic, conjunctive normal form or CNF means the product of sums ( POS ) which clearly states that it is a product of clauses which in turn are the sum of literals.

For Example,

Y = (A + B) (A' + B)

Y is in the form of Conjunctive Normal Form. It is a product of (A + B) and (A' + B) which are Sums of A and B, A' and B.

The correct answer is option2

Solution:

Size of the disk block = 2048 Bytes

disk address = 32 bits = 4 Bytes

Number of addresses per block = 2048/4 = 512 = 2⁹

Maximum file size = 12 Direct Blocks + 1 indirect block + 1 double indirect block

                            = 12 + 2⁹ + 2⁹ * 2⁹

                            = 12 + 2⁹ + 2¹⁸

The size of each block = 2¹¹ Bytes

Maximum size of the file = ( 12 + 2⁹ + 2¹⁸ ) × 2¹¹ Bytes

∴ Maximum size of the file =   513.0234 ≈ 513 MBytes

The correct answer is option 4.

Key Points

Max Z=2x₁+3x₂

2x1 + x2 ≤ 4

x1 + 2x2 ≤ 5           x1, x2 ≥ 0

Graphical method,

 

Draw lines by removing inequality Z at (1,2)  =2+6=8

Z at (2,0) =4+0 =4

Z at (0,5/2)

    =0+15÷2 =7.5

∴ Hence the correct answer is 8.

Hint

The smart way to answer as per the given options

The correct answer is option 4.

Key Points 

The 'process of removing detail' from a 'given state representation' is called an abstraction.

∴ Hence the correct answer is Abstraction.

Additional Information 

• Abstraction is a type of Artificial Intelligence problem formulation and problem-solving process.
• In the analysis of structures or objects, this method includes the elimination of physical, temporal, or spatial information in order to concentrate on more important details.
• The abstraction method is a simple principle in computer science that is used as a declarative statement in many programming languages such as Java and C++.

The correct answer is option 3.

Key Points

Order of complexity. MIMD>SIMD>SISD

∴ Hence the correct answer is B, C, A.

Important Points 

Based on Flynn’s classification

MIMD (multiple instruction stream, multiple data stream):

This includes machines with multiple processing units that can apply multiple instructions to different data at the same time. The MIMD machines are the most complicated, but they also hold the most promise for increasing productivity by concurrent processing. Concurrency here means that not only are multiple processors running at the same time but also that multiple programs (processes) are running at the same time, concurrently.

SIMD (single instruction stream, multiple data stream):

This means that a single instruction is applied to several data sets at the same time. Many different processing units are activated by a single control unit in these machines.

SISD (single instruction stream, single data stream):

This is the von Neumann principle of serial computer architecture, which only executes one instruction at a time.

The correct answer is option 3.

Key Points​

 

∴ Hence the correct answer is D, C, A, B.

The correct answer is option 2.

Key Points

• The <map> tag is used to define an image map. An image map is an image with clickable areas.
• The required name attribute of the <map> element is associated with the 's use map attribute and creates a relationship between the image and the map.
• An image map is made up of an image with clickable areas. When you click on the image, it will open to a new or previously selected destination.

Code

<html> <head><br>

...

</head> <body><br>

...

<map name = "html">

<area shape = "circle" coords = "154,150,59" href = "about/about_team.htm" alt = "Team" target = "_self" />

</map>

</body> </html>

∴ Hence the correct answer is defining the clickable region in an image.

The correct answer is option 2.

Key Points

Black-box testing, also known as behavioural testing, focuses on the software's functional specifications. In other words, black-box testing allows a software developer to create sets of input conditions that completely exercise all of a program's functional requirements. The methods for behavioural testing are as follows.

1. graph-based testing methods
2. equivalence partitioning
3. boundary value analysis
4. comparison testing
5. orthogonal array testing

 ∴ Hence the correct answer is (A), (B) and (C) only.

The correct answer is option 4.

Key Points

1. Heuristic search is a search technique that seeks to solve a problem by iteratively enhancing the solution using a heuristic function or a cost analysis. Heuristic search is two types.  Direct Heuristic Search Techniques in AI( Breadth-First Search (BFS) and Depth First Search (DFS).) and Weak Heuristic Search Techniques in AI (Best-First Search, A* Search, etc)
2. Every AI program has to do the process of searching for the solution steps that are not explicit in nature.
3. knowledge plays a vital role in intelligence as well as creating artificial intelligence.

∴ Hence the incorrect statement is It works on or implements a repetition mechanism.

The correct answer is option 1.

Key Points

• The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context-sensitive languages L1 and L2. Here L₁∧ L₂ is a disjoint operator it's undecidable problem.

Hence statement I is correct.

• The problem "Is WϵL?" is decidable for context-sensitive language L, (where W is a string). Here W is a string that is accepted by the particular language is a membership problem and its decidable problem.

Hence statement II is correct.

Additional Information

Context-sensitive language is accepted by linear bounded automata and only membership(WϵL) problems are decidable.

Context-free language is accepted by pushdown automata and only membership problems(WϵL), finiteness L=finite, emptiness L=Φ are decidable.