UGC NET Paper 2: Computer Science 24th June 2019 (Previous Year Paper)

Concepts:

Constant folding is compiler optimizations technique used by many modern compilers.

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime.

Example:

int var = 4*2.14;

Replace with

int var = 8.56

Since multiplication is costly operation, it has been replaced constant which is more optimized version of previous code

p → q ≡ ¬ p ∨ q

∴ (a) → (iv)

¬ (q → ¬p) ≡ ¬ (¬ q ∨ ¬ p) ≡ p ∧ q

∴ (c) → (i)

¬p → q ≡ ¬ (¬ p) ∨ q ≡ p ∨ q

∴ (b) → (iii)

¬ (p → q) ≡ ¬ (¬ p ∨ q) ≡ p ∧ ¬ q

∴ (d) → (ii)

Therefore option 4 is correct

Alternate method:

Truth Table:

From truth table:

p → q ≡ ¬ p ∨ q

∴ (a) → (iv)

p → q ≡ ¬ p ∨ q

∴ (a) → (iv)

p ∨ q ≡ ¬p → q

∴ (b) → (iii)

p ∧ q ≡ ¬ (q → ¬p) 

∴ (c) → (i)

¬ (p → q) ≡ p ∧ ¬ q

∴ (d) → (ii)

Therefore option 4 is correct

Symbol tables are data structures that are used by compilers to hold information about source-program constructs.

The information is collected incrementally by the analysis phases of a compiler and used by the synthesis phases to generate the target code.

Entries in the symbol table contains information about an identifier (variables) such as its character string (or lexeme), its type, its position in storage, and any other relevant information.

(146)_b + (313)_b-2 = (246)₈

b² + 4b + 6 + 3(b-2)² + (b-2) + 3 = 2× 8² + 4×8 + 6

4b² – 7b + 19 = 166

 4b² – 7b – 147 = 0

4b² – 28b + 21b – 147 = 0

4b(b –  7) + 21(b – 7) = 0

(b – 7).(4b + 21) = 0

∴ b = 7 or b = -21 ÷ 4

Since b cannot be negative or in fraction

∴ b = 7

Alternate Method:

Substitute and check the result

b = 7

(146)₇ + (313)_7-2 = (246)₈

LHS = (146)₇ + (317)_7-2

 (146)₇ = 1 × 7² + 4 ×7¹ + 6 × 7⁰ = 49 + 28 + 6 = (83)₁₀

(313)₅ = 3 × 5² + 1 × 5 + 7× 5⁰ = 75 + 5 + 3 = (83)₁₀

LHS = (83)₁₀ + (83)₁₀ = (166)₁₀  

RHS = (246)₈

= 2 × 8² + 4 ×8¹ + 6 × 8⁰

= 128 + 32 + 6 = (166)₁₀  

LHS = RHS equal only if b is 7.

Concepts:

Degree of Boolean function = number variables = n

Variable is of Boolean type

Sequence possible of two Boolean= 2ⁿ

Different Boolean function = ${{2}^{{{2}^{n}}}}$

Example:

By taking n = 2

Different Boolean function = ${{2}^{{{2}^{n}}}}={{2}^{2}}^{2}=16$

Therefore 16 Boolean function is possible.

Concept:

• File system is the part of the operating system which is responsible for file management. It provides a mechanism to store the data and access to the file contents including data and programs.  The File system takes care of the following issues: File Structure, Recovering Free space, Disk space assignment to the files and Tracking data location.
• Threads refer to the highest level of code executed by a processor, so with many threads, your CPU can handle several tasks at the same time. All CPUs have active threads, and every process performed on your computer has at least a single thread.
• A virtual address space (VAS) or address space is the set of ranges of virtual addresses that an operating system makes available to a process.
• an interrupt is an input signal to the processor indicating an event that needs immediate attention. An interrupt signal alerts the processor and serves as a request for the processor to interrupt the currently executing code, so that the event can be processed in a timely manner.

Conclusion:

Disk → File system, CPU → Thread, memory → Virtual address space and Interrupt → Signal

Therefore option 2 is correct

TCP/IP model, RFC 1122

Therefore option 4 is correct.

Data:

vertices = v = 6

degree of each vertices = d = 4

Formula:

Handshaking Lemma:

\(\underset{\text{i}=1}{\overset{\text{n}}{\mathop \sum }},\text{di}=2\text{e}\)

Euler’s formula:

v – e + f = 2.

Calculation:

2e = 6 × 4    (Handshaking Lemma)

∴ e = 12

f = e – v +2

f = 12 – 6 + 2

∴ f = 8

The plane is divided in 8 regions or faces.

• Waterfall model→ Automate the manual system for student record maintenance in a school
• Incremental development→ E-business that starts with only the basic functionality and then moves on to more advanced features.
• Prototyping→ A virtual reality system for simulating vehicle navigation in a highway.
• RAD→ An inventory control system for a supermarket to be developed in a highway

Hence option 4 is correct

Concepts:

Sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20

Algorithm: shortest seek time first

Arrange in ascending order: 2, 4, 6, 7, 10, 15, 19, 20, 34, 73

Head is at cylinder: 50

Time taken to move to adjacent cylinder = 1ms

Diagram:

Calculation:

Total Head movements= (50 - 34) + (34 - 20) + (20 - 19) + (19 - 15) + (15 - 10) + (10 - 7) + (7 - 6) + (6 - 4) + (4 - 2) +

Total Head movements to serve all request = 16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71 = 119

The time taken to satisfy all requests = 119 × 1 ms = 119 ms

Tips and Tricks:

Since the direction changes only once:

Total Head movements to serve all request = (50 – 2) + (73 – 2) = 119

Formula:

If p is prime, then Φ(p) = (p - 1)

If p is a prime and it's power is k then

$\phi \left( {{\text{p}}^{\text{k}}} \right)={{\text{p}}^{\text{k}}}\left( 1-\frac{1}{\text{p}} \right)$

Calculation:

Φ(45) = Φ(9 × 5)

= Φ(3²) × Φ(5)

$={{3}^{2}}\left( 1-\frac{1}{3} \right)\times \left( 5-1 \right)$

= 6 × 4 = 24

the value of Φ(45) is 24

• A data-manipulation language (DML) is a language that enables users to access or manipulate data as organized by the appropriate model.

Example of DML commands: SELECT, INSERT, DELETE, UPDATE etc.

Therefore a, b and c are DML statements.

• A database system provides a data-definition language (DDL) to specify the database schema

Example of DDL commands: CREATE, DROP, ALTER, RENAME, TRUNCATE etc.

• A data control language (DCL) is used to control access (Authorization) to data stored in a database

Example of DCL commands: GRANT and REVOKE

Since p → q = ¬ p ∨ q ≡ p̅ + q

(p V q) ∧ ¬ p → ¬ q

$\equiv \overline{\left( p+q \right).\bar{p}}+\bar{q}$

$\equiv \overline{p\bar{p}+\bar{p}q}+\bar{q}$

≡ p + q̅ + q̅

≡ p + q̅

≡ p ∨ ¬ q

∴ option 1 is correct

Alternate Method:

Truth Table:

From truth table:

(p V q) ∧ ¬ p → ¬ q ≡ p V ¬ q

IPv4 address size = 32 bit

Number of IP address possible = 2³²

Therefore, Class C address consumes 12.5% of the IPv4 address

Data:

x₁ + x₂ + x₃ + x₄ = 8

∴ n = 4 and r = 8

Formula:

Number of ways to place 8 indistinguishable balls in 4 distinguishable bins = ^{n + r - 1} C₈

Calculation:

Number of ways to place 8 indistinguishable balls in 4 distinguishable bins = ^{4 + 8 - 1} C₈ = ¹¹C₈

$=\frac{11!}{8!\times \left( 11~-~8! \right)}=\frac{11\times 10\times 9}{3!}=165$

∴ option 2 is correct

Data:

Available Resources = R = 6 tapes drives

Max need per process = 2 tapes drives

Concepts:

Deadlock can occur If any process gets available resource < needed (requested) resource

Max resource per process to be in deadlock = needed – 1 = 2 – 1 = 1

For n process, max resource to be in deadlock = n× (2 - 1) = n

If one resource (tape drive) is added, any of the 6 processes can take it a finish its execution leaving behind the allocated resource and hence the system will be deadlock free.

Calculation:

For n process, min resource for the system not to be in deadlock state = n + 1 ≤ R

n + 1 ≤ 6

∴ n_max = 5

Tips and Tricks:

n × (m - 1) + 1 ≤ R

where n is the number of processes

m is the maximum resource need per process

R is the available system resources.

• A foreign key means that values in one table must also appear in another table. The referenced table is called the parent table while the table with the foreign key is called the child table. The foreign key in the child table will generally reference a primary key in the parent table.
• A unique key is a set of one or more than one fields of a table that uniquely identify a record in a database table. Unique key can accept null values and there may be many unique key constraints for one table.
• A primary key is a specific choice of a minimal set of attributes (columns) that uniquely specify a tuple (row) in a relation (table). Primary key cannot accept null values and there can be only one primary key constraint for one table.
• 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. Each table may have one or more candidate keys, but one candidate key is unique, and it is called the primary key.
• The check constraint is used to limit the value range that can be placed in a column.

Since primary key is minimal set in relation having unique values with no null value. Therefore, foreign key of one relation referred to primary key of another relation.

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 = 7

Wait operation = 20 P

Signal operation = 15 V

Final counting semaphore = F

Formula:

F = I + 15V + 20P

Calculation:

F = 7 + 15(+1) + 20(-1)

∴ F = 2

the resulting value of the semaphore is 2

Concepts:

• In a full connected network topology, every device has a dedicated point-to-point link to every other device.The term dedicated means that the link carries traffic only between the two devices it connects.
• In a fully connected network network with n nodes, first, consider that each node must be connected to every other node. Node 1 must be connected to n - 1 node, node 2 must be connected to n - 2 (since 1 link is already included in the 1st case) nodes, and so on.
• In mess topology, devices are full connected. Therefore, it will require (n × (n - 1)) ÷ 2) physical links.

Example: n = 6

The number of direct links = $\frac{{n\left( {n - 1} \right)}}{2} = 15$

Page reference: 1,2,1,3,7,4,5,6,3,1

Page replacement algorithm: Least Recently used (LRU)

LRU = 9 miss = 9-page faults

Page reference: 1,2,1,3,7,4,5,6,3,1

Page replacement algorithm: Optimal

Optimal = 7 miss = 7-page faults

LRU – optimal = 9 – 7 = 2

The difference in page faults for the above string using the algorithm of LRU and Optimal page replacement for referencing the string is 2.

1 word = 2 bytes

Maximum Memory = 4GB = 2³² bytes = 2³¹ × 2 bytes

Maximum Memory = 2³¹ word

Important Points:

1 G = 2³⁰

• A thread is a lightweight process that can be managed independently by a scheduler.
• A message queue is a linked list of messages stored within the kernel and identified by a message queue identifier.
• Threads share the code and data segments and the heap, but they don't share the stack and registers. Message queue comes under data and therefore it is shared by thread.
• Threads of the same process don’t share stack and register, hence option 3 is correct

Scheduling Algorithm:

shortest remaining time first

Gantt chart:

0               10               30               60

Process table:

Number of context switches = 2

Important Points:

context switches at time zero and at the end is not considered

Memory capacity =16K × 16 = 2¹⁴ × 2⁴

Memory Capacity is of the form = 2^m × 2ⁿ

Address lines required = m = 14

Data Lines required = 2ⁿ = 16

Option 3 is correct

IPv4 address: 32 bits

IP address = Network ID + Host ID

Network ID + Host ID =32

PREFIX is the part of the Network ID

The address between the range 127. 0. 0. 0 to 127.255.255.255 (exclude 127. 0. 0. 0 and 127.255.255.255) can be used as a loopback address that falls in the range of Class A network. Therefore, the loopback (IP) address is a member of class A network. Therefore, statement P is false.

A loopback address is primarily used to validate that the locally connected physical network card is working properly and the TCP/IP stack installed. A data packet sent on a loopback address, never leaves the host system and is sent back to the source application (to itself). Therefore, statement Q is true.

Hence option 2 is correct

• Relational algebra is a procedural query language, which takes instances of relations as input and yields instances of relations as output. It uses operators (selection, projection, union etc) to perform queries.
• Relational calculus consists of two calculi, the tuple relational calculus and the domain relational calculus, that are part of the relational model for databases and provide a declarative way to specify database queries
• Relational algebra, Domain relational calculus restricted to safe expression and Tuple relational calculus restricted to safe expression have the same expressive power.

Confusion Points:

Relation algebra’s expressive power is not equal to Domain relational calculus or Tuple relational calculus unless they are restricted to safe operation.

• MOD-2 counter followed by MOD-5 it denotes cascading of two counters. Therefore, equivalent counter = MOD (2 × 5) counter = MOD-10 counter
• MOD-10 counter is also called as BCD counter or Decade counter with ten states in its sequence.
• Hence the number of states when a MOD-2 counter is followed by a MOD-5 counter is 10

• The address resolution protocol (ARP) is a protocol used by the Internet Protocol (IP), specifically IPv4, to map IP network addresses to the hardware addresses used by a data link protocol, that is, MAC address.
• DNS is a host name to IP address translation service. DNS is a distributed database implemented in a hierarchy of name servers. It is an application layer protocol for message exchange between clients and servers.
• The Reverse Address Resolution Protocol (RARP) is a computer networking protocol used by a client computer to request its Internet Protocol (IPv4) address from a computer network, when all it has available is its link layer or hardware address, such as a MAC address. RARP protocol broadcast message with its MAC address and receive an IP address in reply.
• The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when communicating with another Host IP address.

Manager_id is foreign Key referring to Employee_ id (primary key) of the same table

(20,40) is deleted, that is, Employee_id = 20 is deleted

Therefore Manager_id = 20 should be deleted to maintain the referential integrity of table.

If Manager_id = 20 row is deleted, then Employee_id = 35 is also deleted

Therefore Manager_id = 35 should also be deleted to maintain the referential integrity of table.

If Manager_id = 35 row is deleted, then Employee_id = 30 is also deleted

Since If Manager_id ≠ 35 we stop here

Table after deletion:

Apart from (20,40), (30,35) and (35,20) also gets deleted to maintain the referential integrity of table.

Hence correct option is 2.

Concept:

Orthographic projection: In orthographic projection, direction of projection is normal to the plane of projection.

Explanation:

Statement P:

Orthographic projection is a type of parallel projection. Parallel projection preserves the parallel lines. While in case of another parallel projection i.e. perspective projection, parallel lines are skewed towards vanishing points.

Statement Q:

Affine transformation is a method for line preserving or mapping. In this also, parallel remains parallel after transformation. In orthogonal projection, all projection lines are perpendicular to the projection plane due to which it appears an affine transformation. So, we can say that orthographic transformations are affine transformation.

Concept:

Software reuse is the use of existing software after doing some changes in the existing software.

Explanation:

Software reuse helps in reducing the cost of software production by using the existing software with some modification. It means creation of new software by reusing the existing software rather than making new software.

A software cannot be easily reused if it is connected in some complex way to other components in an existing system.

Three requirements for a reusable component are:

• It provides a useful service
• It performs a single function
• It has the minimum of connections to other components.

Immediate addressing mode:

It is the simplest form of addressing mode, in which the operand value is present in the instruction. This mode is used to define and use constants or set initial values of variable. In this, no memory reference other than the instruction fetch is required to obtain the operand.

Implied addressing mode:

In this, operands are specified in the definition of instruction. It is used for zero address instructions.

Register addressing mode:

In register addressing mode, the address field refers to a register rather than a main memory address. In this, only a small address field is needed in the instruction and no time-consuming memory references are required.

Index addressing mode:

In this, operand is the address that is sum of index register and displacement. It needs memory reference.

Data:

h(k, i) = (h₁(k)+ih₂ (k)) mod m

Where h​₁​(k)=k mod m, h​₂​ (k)=1+(k mod n)

 n=m-1, m=701 and k = 123456

Calculation:

h₁(k) = 123456 mod 701 = 80

h₂(k) = 1 + (123456 mod 700) = 1 + 256 = 257

1^st probe: when i =1

h(k, i) = h1(k) + ih2(k)

h(k, 1) = h1(k) + h2(k) = 80 + 257 = 337

2^nd probe: when i =2

h(k,2) = h1(k) + 2h2(k) = 80 + 2257

h(k,2) = 80 + 514 = 594

So, difference between first two probes = 594 – 337 = 257

Statement a: G is a CFG with L(G) = ϕ

It means emptiness problem for context free grammar. For context free language, emptiness problem is decidable. So, this statement is correct.

Statement b: There exist two TMs M​1​ and M2​ such that L(M) ⊆{L(M​1​) U L(M​2​)} = language of all TMs

L(M​1​) U L(M​2​) – it means union of two recursive enumerable languages which is also recursive enumerable.

L(M) ⊆{L(M​1​) U L(M​2​)}, this means subset problem for Turing machine (TM). Subset is undecidable property in Turing machines.

Statement c: M is a TM that accepts w using at most 2​^|w|​ cells of tape

It is undecidable, Suppose M accepts w is decidable. Then language is decidable. It means M does not accept w is also decidable. Suppose this complement is decidable by another Turing machine then there comes a contradiction. So, it is not decidable.

• Software validation means “are we building the right product”. Validation means that product meets the customers’ expectations. It goes beyond checking it meets its specification as system specifications don’t always accurately reflect the real need of users.
• Validation refers to the process of evaluating software at the end of its development to ensure that it is free from failures and complies with its requirements. A failure is defined as incorrect product behavior. Often this validation occurs through the utilization of various testing approaches.

There are two ways to perform software validation: internal and external.

1. Internal validation assumes that goals of stakeholders were correctly understood.
2. External validation is performed by asking the stakeholders if the software meets their needs.

Boyce Codd Normal Form (BCNF): 

• A relation is said to be in BCNF form, if it satisfied the following property.
• If there is a functional dependency X → Y, then for relation to be in BCNF, X must be the super key.
• If a relation is in highest normal form, then it automatically also in the weaker normal forms. It means, if a relation is in BCNF then it is also in 1NF, 2NF, 3NF.
• Since the requirement of BCNF is left hand side of functional dependency should be the candidate key. So, there is no possibility of partial dependency and transitive dependency in the relation.

Concept:

Candidate key: It uniquely identifies the tuples in a relation. A candidate key is a super key with no redundant attribute. In a relation, there can be more than one candidate key.

Explanation:

As, candidate uniquely identifies the tuples in a relation. So, first property of the candidate key is its uniqueness. 

Second, candidate key does not contain redundant attribute. We cannot further reduce a candidate key. If a candidate key is reduced, then it can cause partial dependency. Second property is its irreducibility.

Example:

A relation with four attributes: R(A, B, C, D). Function dependencies are:

A → C

B → D

In this, AB is the candidate key.

AB uniquely identifies tuple in relation R also AB cannot be reduced further.

Prim’s algorithm:

It is used to find the minimum spanning tree for a weighted undirected graph. It uses the greedy approach to find the MST for a graph. Unlike the Kruskal’s algorithm, we add vertex to growing spanning tree in this. If there are V vertices and E edges in the graph. Then time complexity to search for MST is O(ElogV).

Dijkstra’s algorithm:

It is used to find the shortest path from source vertex to all other vertices in a graph.  Initially, distance from source to source is considered as 0 and to all other vertices is infinity. It uses the condition “current vertex distance + edge weight < next vertex distance” to find shortest distance. Time complexity for this is O(V²).

Faster all pair shortest path: 

It finds shortest the distance from a vertex to all other vertices in a graph. If there are E edges and V vertices in a graph, then it takes O(V³logV) time to find the shortest path.

Edmond-Karp algorithm: It is used to find the maximum flow in a network. It uses BFS in Ford Fulkerson method. Its time complexity is O(V.E²).

Concept:

The time required to find an item stored in memory can be reduced considerably if stored data is identified for access by the content of the data itself rather than by an address. Memory unit accessed by content is called an associative memory or content addressable memory (CAM).

Explanation:

CAM is accessed simultaneously and in parallel on the basis of data content rather than specific location. When a word is written in CAM, no address is given. Memory is capable of finding an unused empty slot to store the word. When a word is to be read from memory, the content of the word is specified, and memory locates all words which matches the specified content and marks them for reading.

Statement P:

A minimal test set that achieves 100% path coverage will also achieve 100% statement coverage.

This statement is correct. Statement coverage means executing each statement at least once. Whereas Path coverage is in which every distinct entry – exit path through the code is executed at least once in some test. It is a white box technique. It tells about how well the source code has been made. A minimal test set that achieves 100% path coverage will also achieve 100% statement coverage.

Statement Q:  

A minimal test set that achieves 100% path coverage will generally detect more faults than one that achieves 100% statement coverage

Sometimes, during minimal test it can be the possibility that test suite produce 100% statement coverage will miss certain defects related to control structure. So, this statement is correct.

Statement R: A minimal test set that achieves 100% statement coverage will generally detect more faults than one that achieves 100% branch coverage

Branch coverage means, for each branch is chosen at least once in some test. It includes statement coverage. As, in case of statement coverage, test suite sometimes cannot detect all faults. So, this statement is not correct that a minimal test set that achieves 100% statement coverage will generally detect more faults than one that achieves 100% branch coverage.

Concept:

A language is recursive if there exists a Turing machine. For strings that are in the language, Turing machine accepts the language and always halts and for strings not in the language, string will halt in the non-final state.

Explanation:

A language L ⊆ Σ* is recursive if there exists some Turing machine M

suppose w is the string.

So, if w belongs to language, then Turing machine M will halt by reaching at final state and if does not belong to L, then M halts without reaching to final state (acceptable state).

Concept:

Manhattan distance is the distance between two points measured at right angle along both the x-axis and y- axis.

Formula:

It is calculated as: if there is a point P(x₁, y₁) and Q(x₂, y₂). Then Manhattan distance is |x₂- x₁| + |y₂ – y₁|.

Calculation:

C1: {(3,3), (5,5), (7,7)}

C2: {(0,6), (6,0), (3,0)}

C3: {(8,8), (4,4)}

First point is (4,4).

We have to find the Manhattan distance for cluster C1 in 2^nd iteration:

For 2^nd iteration: points will be:

$\left( {\frac{1}{3}\left( {3 + 5 + 7} \right)} \right),\left( {\frac{1}{3}\left( {3 + 5 + 7} \right)} \right) = \left( {5,;5} \right)$

So, Manhattan distance = |5 – 4| + |5 – 4| = 1 + 1 = 2

The correct answer is True, False, False, False

Key Points

• m1.equals(m2) - This will be True. Both m1 and m2 are instances of Good and their m field is equal to 22.
• m1.equals(s2) - This will not compile because the Object s2 is not explicitly cast to Good.
• s1.equals(m2) - This will also not compile because the .equals() method of the Object class is expecting an Object as parameter, but here you're providing it with an instance of Good. Since the equals() method is not overridden in Good class to handle the object class, it is a mismatch.

Reinforcement learning:

It is the learning what to do – how to map situations to actions so as to maximize a numerical reward signal. The learner is not told which actions to take, but instead must discover which actions yield the most reward by trying them.

Two most distinguishing feature of reinforcement learning are: trial and error search and delayed reward. The problem of reinforcement learning means using ideas from dynamical system theory as the optimal control of incompletely known Markov decision process. It starts with a complete, interactive and goal –seeking agent. In this agent initially knows the set of possible states and possible actions.

Concept:

Genetic algorithms are adaptive methods which may be used to solve search and optimization problems. They are based on the genetic process of biological organisms.

Explanation:

Genetic algorithms use a direct analogy of natural behavior. They work with a population of individuals, each representing a possible solution to a given problem. Each individual is assigned a fitness score according to how good a solution to the problem it is. The highly fit individuals are given opportunities to reproduce, by cross breeding. This produces offspring. Before a GA can be run, a suitable coding and fitness function is required.

Phases that are considered in genetic algorithm are:

1. Initialize population

2. Selection

3. Crossover

4. Mutation

5. reproduction

Concept:

Shift reduce parser is based on the idea of predictive parsing with look ahead. It is a bottom up parser.

Explanation:

A shift-reduce parser indeed consists of an input buffer for holding the input string, a stack for temporarily holding the symbols that are not yet reduced, and a parse table to guide the parsing actions -- it helps determine when to shift (push a symbol onto the stack) and when to reduce (pop symbols off the stack and replace them with a nonterminal).

Example:   E → E – E

E → E × E

E → id

We have to parse the string id – id × id:

Statement P: In a scripting language like JavaScript, types are typically associated with values, not variables.

JavaScript is a client side as well as server-side scripting language.  JavaScript data types are:  number, string, Boolean, object, undefined. Basically, the type of a value determines the operations and methods performed on it. Variables are not directly associated with any particular type; any variable can be assigned values of all type.

Statement Q: It is not possible to show images on a web page without the image tag of HTML

This statement is not correct. As, images can be shown on a web page without the use of image tag of HTML. We can use div by giving the URL of the image in that.

Dynamic programming approach:

Dynamic programming approach consider the previous steps solution, save them and then use them in future so as to avoid solving same problem again and again. It uses the bottom up approach. Steps that are take in dynamic programming approach are:

1. Characterize the structure of an optimal solution

2. Using the previous solved values

3. Construct the optimal solution for final result.

Greedy programming approach:

It builds the solution step by step. It chooses each step such as the next step gives the best result. Unlike the dynamic programming approach: greedy algorithm solves the problem in top down fashion.  It also characterizes the structure of an optimal solution.

Expression a:  L'₃ U L₄

L₃ is recursive language and L_4­ is recursive enumerable language. Complement of recursive language is recursive. So, L^’₃ is also recursive. Also, union of recursive and Recursively enumerable language is recursively enumerable language. L'₃ U L₄ is recursively enumerable.

Expression b: L'₂ U L₃

L₂ is context free language. Context free languages are not closed under complement. It is context sensitive. Context sensitive is also considered as recursive language. Union of two recursive languages is also recursive.

Expression c: L₁* ∩ L₂

L₁ is regular language. Regular languages are closed under Kleen closure. So, L₁* is also regular. Intersection of a regular and context free language is a context free language. So, L₁* ∩ L₂ is a context free language.

• In class B addressing: 16-bit network ID and 16-bits for host ID.
• 500 subnets are required and 2⁹ = 512, hence 9 bits are needed from host id part of class B addressing in order to provide 500 subnets.
• Remaining 7 bits number of host possible per subnet is 128 – 2 = 126
  

Subnet mask contains 1’s in subnet id part and the 0's in host ID part. Hence subnet mask is:

11111111. 11111111. 11111111. 10000000
                              

In decimal form it can be represented as:

255. 255. 255. 128

Man-in-the-Middle Attack:

It is an attack where the attacker secretly relays and possibly alters the communications between two parties who believe they are directly communicating with each other.

Three security issues that are particularly applicable to the IP protocol: packet sniffing, packet modification and IP spoofing.

Packet sniffing:

In packet sniffing, an intruder tries to intercept the IP packet and make a copy of it. It is a passive attack, in which the attacker does not change the contents of the packet.

IP spoofing:

In IP spoofing, an attacker can masquerade (pretense) somebody else and creates an IP packet that carries the source address of another computer. An attacker can send an IP packet to a bank pretending that is coming from one of the customers.

NP complete problems:

They are those for which no polynomial time algorithm exists. We can say a problem is NP complete if it is NP and belongs to NP hard.

NP problems:

A problem is a member of NP class if there exists a non-deterministic machine which can solve it in polynomial time.

NP Hard:

A problem is called as NP hard if all the NP class problems are polynomial time reducible to that and as hard as any problem of NP class.

The question asks specifically for in-place sorting algorithms, which means the algorithms in which only O(1) space is used.  

Insertion sort:

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order.  It is in-place sorting algorithms.

In that case the number of comparisons will be like:

\(\mathop \sum \limits_{P = 1}^{N - 1} p = 1 + 2 + 3 + 4 + \ldots + N - 1 = \frac{{N\left( {N - 1} \right)}}{2}\)

This will give Θ (n²) time complexity.

Merge sort:

In Merge sort, the worst-case takes Θ (n log n) time. Merge sort is based on the divide and conquer approach. It is out of place sorting algorithms

Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

T(n) = n + Θ (n)

T (n) = n × logn

Quicksort:

In Quicksort, the worst-case takes Θ (n2) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.

\(\mathop \sum \limits_{P = 1}^{N - 1} p = 1 + 2 + 3 + 4 + \ldots + N - 1 = \frac{{N\left( {N - 1} \right)}}{2}\)

This will give Θ (n²) time complexity.

Recurrence relation for quick sort algorithm will be,

T (n) = T (n - 1) + Θ (n)

This will give the worst-case time complexity as Θ (n²).

It is in-place sorting algorithms

Conclusion:

P needs to be an in-place sorting algorithm, and Q needs to be out of place sorting algorithm, Hence option 4 is correct.

Data:

Bandwidth = BW = 10⁹ bps

Distance = D = 800 km

Speed = V = 2 × 10⁵ km/s

Formula:

${\rm{Propagation;Delay}} = {{\rm{T}}_{\rm{p}}} = \frac{{\rm{D}}}{{\rm{V}}}{\rm{;}}$

Calculation:

${{\rm{T}}_{\rm{p}}} = \frac{{\rm{D}}}{{\rm{V}}} = \frac{{800}}{{2 \times {{10}^5}}} = 4 \times {10^{ - 3}} = 4;ms$

The propagation delay in this link is 4 ms.

Maintenance:

Maintenance can be referred as a process of enhancement in the software product according to the changing requirements of users.

Four types of maintenance:

1. Adaptive: modifying the system to cope with changes in the software environment (DBMS, OS).
2. Perfective: implementing new or changed user requirements which concern functional enhancements to the software
3. Corrective: diagnosing and fixing errors, possibly ones found by users.
4. Preventive: Increasing software maintainability or reliability to prevent problems in the future.

Instruction set architecture:  

• The Absolute minimum number of frames that a process must be allocated is completely dependent on System architecture.
• The Number of pages that could be touched by a single instruction.
• For no indirect addressing, at least two pages in physical memory, that is, one for instruction (code part) and another for if the data references memory.
• If there is one level of indirection, then it will need at least three pages one for the instruction(code) and another two for the indirect addressing and so on.
• Therefore, the instruction set architecture determines the minimum number of page frames that must be allocated to a running process in a virtual memory environment.

Model-View-Controller (MVC):

• MVC refers to three different realms of responsibility in the design of a graphical user interface.
• When the MVC pattern is applied to a component, the model consists of the data that represents the current state of the component.
• The view is simply the visual presentation of the component on the screen.
• The controller is the aspect of the component that carries out actions in response to events generated by the user (or by other sources such as timers).
  

The idea is to assign responsibility for the model, the view, and the controller to different objects.

Statement I:  Correct

Euler's theorem (Fermat–Euler theorem or Euler's totient theorem) states that if ‘n’ and ‘a’ are coprime positive integers, then a^Φ(n) = 1(mod n)

Statement II:  Incorrect

According to Fermat's Little Theorem,

Let ‘p’ be a prime and ‘a’ any integer, then a^p = a (mod p).

Concept:

Fuzzy set: A fuzzy set is that which allows its members to have different value in the set interval [0,1].

Explanation:

Operations that can be performed on fuzzy set are union, intersection, complement.

Union and intersection operation in fuzzy set are equal to conjunction(AND) and disjunction operation(OR) respectively.

We can consider min for conjunction and max for disjunction. Also, there are various other choices also. Such as to calculate product for conjunction and algebraic sum for disjunction operation.

If fuzzy conjunction operator is denoted as t(x, y) and fuzzy disjunction operator is denoted as s(x, y). Then it forms as dual pair if:

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

or 1- s(x, y) = t(1-x, 1-y )

Here, it means choice of fuzzy disjunction operator determines the choice of fuzzy conjunction operator and vice versa.

XML:

XML stands for extensible markup language. It is a meta markup language for text documents/data. It allows to define languages to represent text. It is designed to describe data not to display data. XML tags are not predefined.

Some points in XML are as follows:

• An XML document is well formed it satisfies rule specified by the W3C.
• A well-formed XML have a proper starting and closing tag.
• An XML documented validated against a DTD is both “Well-Formed” and “valid”.
• Purpose of DTD is to define the structure and legal elements and attributed of a XML document.
• XML does not require DTD.
• XML carries the data; it does not represent it.
• XML can be used for offloading and reloading of databases.

XML declaration syntax is:

STRIPS – It stands for Stanford research institute problem solver. It is an action centric representation in which for each action, it specifies the effect of the action.

In strips representation, there are states and goal and operators. Operator is of three parts :

1.  Operator name
2. Precondition: it must occur so that operator can execute.
3. Effect: it means how the state will change after an action.

In STRIPS, there is state base view of time. Actions are external to the logic. Given a state and an action, STRIPS representation is used to find:

a)  Whether the action can be carried out in the state

b) what is true in the resulting state.

Predicates used in STRIPS are primitive and derived. It is used to determine the truth value of primitive predicates based on the previous state and action.

Correct answer is option 4).

Concept:

Defuzzification: It is the reverse of fuzzification in which a fuzzy set is transformed back to crisp set.

Methods:

M​1: mean of maximum

M​2: Centre of area

M​3: Height method

Explanation:

Various defuzzification methods are:

1. centre of sum method: In this method, it covers the area two times , which is the required area.

2. centroid method: It provides crisp value by considering the centre of gravity on fuzzy set. It is also known as centre of gravity method. Total area is divided into sub areas in this. Centre of gravity is calculated for each sub area.

3. centre of area method: It calculates the area under curve. It partitions a region into two regions of same area.

4. weight average method: In this, membership functions are used. Each membership function is weighted by the maximum membership value.

5. maxima methods

a) First of maxima : It finds the smallest value of domain with maximum membership value

b) Last of maxima: It finds the largest value with maximum membership value.

c) Mean of maxima: In this, mean of the values is taken with maximum membership value.

Statement S1: TRUE

Let the mirror image co-ordinate be [x’, y’]

\(\left[ {x',;y'} \right] = \left[ {x,;y;} \right]\left[ {\begin{array}{*{20}{c}} 1&0\ 0&{ - 1} \end{array}} \right]\)

[x’, y’] = [x, -y]

Mirror image of co-ordinate (x, y) is (x, -y)

Therefore, statement I is correct

Statement S2: FALSE

A 2 × 2 matrix which mirrors any 2D point about the X-axis, is not a rotation matrix

Initially consider p = 8, n = 7 and m = 1

Iteration 1:

int x=p; int k=n; int m=1;            // So, x = 8, k =7

while(k< >0)                                   // condition true as k is not equal to zero

if(k is odd) then m=mx;               // as 7 is odd, then m = 18 = 8

x=x*x                                              // x = 64

k=⌊(k/2)⌋;                                      // k = 7/2 = 3

Iteration 2:

while(k< >0)                                   // condition true as k is not equal to zero

if(k is odd) then m=mx;               // as 3 is odd, then m = 864 = 512

x=x*x                                              // x = 4096

k=⌊(k/2)⌋;                                      // k = 3/2 = 1

Iteration 3:

while(k< >0)                                   // condition true as k is not equal to zero

if(k is odd) then m=mx;               // as 1 is odd, then m = 5124096 = 2²¹

x=xx                                              // x = 40964096 = 2²⁴

k=⌊(k/2)⌋;                                      // k = 1/2 = 0

Next while loop false

∴ m = 221

Option 2:  Correct answer

pⁿ = 8⁷ = (2³)⁷ = 2²¹

∴ m = pn

Start from bottom to top:

1. First it finds the minimum value from the given values.

2. At next step, max value is considered.

3. Then again min value is considered.

4. Then at the root, we have to consider the maximum value.

Formula:

Total execution time = time to execute multiplication operation + time for other operations

Calculation:

Total execution time = 100 seconds

Time to execute multiplication operation = 80 seconds.

Then time to execute other operation = 100 – 80 = 20 seconds.

To execute the program four times faster, we have to improve the multiplication operation according to the question.

To execute the program four times faster: Total execution time will become = 100/ 4 = 25 seconds

New time to perform multiplication operation = new total execution time – time for other operations

New time to perform multiplication operation = 25 – 20 = 5 seconds

So, speed of multiplication operation is improved by = 80/5 = 16 times

Speed becomes 16 times fast.

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right)$

Differentiating with respect to x

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right) = \frac{{\left( {1 + {e^{ - 2x}}} \right)\frac{d}{{dx}}\left( 1 \right) - \left( 1 \right)\frac{d}{{dx}}\left( {1 + {e^{ - 2x}}} \right)}}{{{{\left( {1 + {e^{ - 2x}}} \right)}^2}}}$

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right) = \frac{{0 - \left( 1 \right)\frac{d}{{dx}}\left( {1 + {e^{ - 2x}}} \right)}}{{{{\left( {1 + {e^{ - 2x}}} \right)}^2}}}$

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right) = \frac{{ - \left( 1 \right){e^{ - 2x}}\left( { - 2} \right)}}{{{{\left( {1 + {e^{ - 2x}}} \right)}^2}}}$

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right) = \frac{{2{e^{ - 2x}}}}{{{{\left( {1 + {e^{ - 2x}}} \right)}^2}}}$

take x = 0

$\frac{d}{{dx}}\left( {\frac{1}{{1 + {e^{ - 2x}}}}} \right) = \frac{{2{e^{ - 2 \times 0}}}}{{{{\left( {1 + {e^{ - 2 \times }}0} \right)}^2}}} = \frac{2}{{{{\left( {1 + 1} \right)}^2}}} = \frac{2}{4} = \frac{1}{2}$

Concept:

Greatest element:

It is the maximum element i.e. element succeeding all other elements.

Least element:

It is the minimum element i.e. element preceding all other elements.

Explanation:

poset: {3, 5, 9, 15, 24, 45}

Hasse diagram for this poset is:

There are two maximal elements in this Hasse diagram: 24 and 45

Also, there are two minimal elements: 3 and 5

Both the maximal elements are at the same level. They are not dividing each other. So, there is no maximum or greatest element here.

Also, both the minimal elements are at the same level. There is no minimum element.

Matrix: \(A = \left[ {\begin{array}{*{20}{c}} 1&0&1\ 0&1&0\ 1&1&0 \end{array}} \right]\)

Consider, matrix starts from 0

i.e. from 0 to 2

Relation of matrix is: {(0, 0), (0, 2), (1, 1), (2, 0), (2, 1)}

In this we have an edge from 0 to 2 and from 2 to 1. So, there should be an edge from 0 to 1 also.

Also, there is an edge from 2 to 0 and 0 to 2. So, there must be an edge from 2 to 2 also.

Pairs that should be added to make the transitive closure of the matrix: {(2, 2), (0, 1)}.

After adding these pairs, matrix will become:

\(A = \left[ {\begin{array}{*{20}{c}} 1&1&1\ 0&1&0\ 1&1&1 \end{array}} \right]\)

• Risk monitoring and control in software engineering ensures the execution of risk plans and help in reducing the risk in software projects.
• It keeps track of identifies risks. It monitors the already occurring risks and can identify new risks in project execution.

Primary objectives of risk monitoring are:

1. To assess whether predicted risks do occur.
2. To ensure that risk aversion steps defined for the risk are being properly applied
3. To collect information that can be used for future risk analysis.
4. To verify that risk actions are as effective as expected
5. Proper procedures are followed or not.
6. To identify the new risks that were not occurred previously
7. To identify whether the risk has changed or declined.

Risk monitoring helps in identifying the events that has a serious effect in controlling the risks. It can produce alternate path for execution of events. It provides a good quality software after monitoring and controlling all the risks that can occur during the execution of software project.

Concept:

Quadruple representation is the three-address code representation. In this, each instruction is spitted into four fields which are operator, argument1, argument 2, and result.

Explanation:

Expression: (ij)+(e+f)(a*b+c)

T1 = (i * j)

T2 = (e + f)

T3 = (a * b)

T4 = T3 + c

T5 = T2 * T4

T6 = T1 + T5

Table Form:

So, total 6 operations are required.

Concept:

Pipes in Linux/Unix: Pipe is a command which produces an output which serves as input for next command. It works as a pipeline structure in computer.

Explanation:

We have to find the number of lines in all the files having .c and .h as their extension in the current working directory.

wc – in unix/linux , “wc” is used for word count.

cat – it is used to display the content of the file

Option 4:

cat *.[ch]              // it represents the content of files having .c and .h extension

Option 2:

cat *.[c-h] | wc –l      // it also includes the files with .c and . h extension but it also considers the other extensions that come between because it is a range which is not required in this question.

So, cat *.[ch] | wc -l

It will count the number of lines in all the files having .c and .h as their extension in the current working directory.

Concept:

Arbiters:  arbiter is a device used in digital electronics to access the shared memory.

Encoder: Encoder is a combinational circuit that take the binary input in the form of 2n input lines and convert it into the n output lines.

Decoder: Decoder is the reverse process of encoder which takes the n inputs and convert to 2n output lines.

Explanation:

Here, it is given that a parallel arbiter has 5 bus arbiters.

For 5 bus arbiters, 3 bits are required.

For priority encoder:

With 3 bits, number of input lines are 23 = 8

Number of output lines = 3

Size of priority encoder will be: 8 × 3

For decoder:

With 3 bits, number of inputs = 3

Number of output lines = 23 = 8

Size of decoder is: 3 × 8

Sort the integers in the range from 0 to n² -1.

If we take any comparison-based sorting algorithms for this, it will take O(nlogn) time.

Comparison based sorting algorithms are merge sort, quick sort, heap sort etc.

Radix sort is used for sorting this range of integers. Radix sort takes O(n) time for this.

Algorithm:

For any digit in the integer, varies from least significant digit to the most significant digit of the number. Sort the input array using count sort algorithm according to the digit.

Note:

Radix sort depends on digits. It is more flexible than comparison based sorting algorithms. It solve the given problem in linear time.

Depth first search:

Depth first search algorithm is used to traverse the vertices of a graph. It uses the concept of back tracking. Depth first search uses a data structure for its implementation which is known as stack.

Application of depth first search:

1. It is used to find the strongly connected components.

2. It helps in topological sorting.

3. to check the bipartiteness of a graph.

4. It helps in detecting cycles in a graph.

5. To find articulation points in a graph.

Example:

DFS traversal for this: 1 2 4 5 3 6 7

S → XY

X → YaY | a and y →  bbX

Strings that are produced by this grammar are:

S → XY → abbX → abba

S → XY → YaYY

→ bbXabbXbbX → bbaabbabba

S → XY → YaYY

→ bbXabbXbbX  →bb YaY abbXbbX

→ bbbbXabbXabbXbbX → bbbbaabbaabbabba

So, strings that are accepted by this language are in the form of :

{abba, bbaabbabba, bbbbaabbaabbabba,……….}

Smallest string contains two a and all other contains more than two a’s

It means every string must contains at least two a’s. Also, number of b’s in the string is multiple of 2.

Concept:

Raster scan system; In this, electron beam move on the screen from top to bottom covering each row one by one.

Explanation:

Given resolution of the system is: 640 × 480

We have to store 12 bits per pixel.

Frame buffer size = resolution (number of pixels) × number of bits per pixel

Frame buffer size = (640 × 480) × 12 = 3686400 bits

Convert it into bytes.

Frame buffer size = 3686400/8 = 460800 Bytes = 460 .8 KB

It is approximately equal to 450KB which is option 1)

Concept:

Alpha cut in a fuzzy set:

An α cut of a fuzzy set A is a crisp set that contains all elements in U that have membership value in A greater than or equal to α.

Explanation:

A_α0 = α-cut of a fuzzy set A at α₀

If we take α₁ < α₂.

Consider an example for this:

Fuzzy set A on interval x[1, 5], membership function(u_A) is = x/x + 2

Case 1: First find α_0.2

x can be 1, 2, 3, 4 and 5

when x = 1, u_A = 1/1 + 2 = 1/3 = 0.33

When x = 2, u_A = 2/2 + 2 = ½ = 0.5

When x = 3, u_A = 3/3 + 2 = 3/5 = 0.6

When x = 4, u_A = 4/4 + 2 = 4/6 = 0.66

When x = 5, u_A = 5/7 = 0.71

Alpha cut for α = 0.2 is {1, 2, 3, 4, 5}

Case 2: Take α_0.5

Alpha cut for this set is {2, 3, 4, 5}

From here it is clear that set 2 is subset of set 1. i.e. A_α1 ⊇ A_α2

Concept:

Integrity of web application:

Integrity of web application can be found out using the security and threat in that.

Formula:

Integrity = [1 - threat (1- security)]

Calculation:

It is given that, probability or likelihood of repelling an attack = 30%

I.e. probability of security = 0.30

Threat probability is given as 25% or 0.25

So, integrity = [1- 0.25 (1- 0.30)]

Integrity = [1- 0.25 (0.70)]

Integrity = 1 - 0.175 = 0. 825

Concept:

Seek latency: It is the time required to move the disk arm to the required track.

Explanation:

As, seek latency is depending on the movement of the disk arm, when read -write head moves from one track to other track to reach the desired track, there is a change in the speed and direction of read write with every change in the track. This is known as inertia. Due to this inertia, seek latency cannot remain linearly proportional to the seek distance.

Seek time is not linearly compared with seek distance because of start and stooping inertia of disk arm. (acceleration and deceleration of arm).

Regular expression: a * b(a + b)

Language that is accepted by this expression is of type: {ba, bb, bab, aba, abb, abab, aabab, ……..}

Smallest string length is 2, that is, we need at least 3 states for this.

NFA for this regular expression is:

So, number of states required in this NFA are 3.

Concept:

Control unit: It provides control signals for the operation and coordination of all processor components. Traditionally, microprogramming implementation has been used, in which major components are control memory, microinstruction sequencing logic and registers.

Explanation:

Within the computer, a control unit manages the computer’s resources and orchestrates the performance of its functional parts in response to the instructions.

Microprogrammed control unit operates by executing instructions that define the functionality of the control unit. In this, set of microinstructions is stored in the control memory. The control address register contains the address of the next microinstruction to be read. When a microinstruction is read from the control memory, it is transferred to a control buffer register. Next element is sequencing unit that loads the control address register and issues a read command.

Phong reflectance model:

• It is local illumination model. In real world, light is shown with the help of its spectrum. In computer graphics, light color is made of a triplet that is of three colours RGB(red, green and blue).
• The reflectance spectrum is a triple of percentage. The light seen on a surface can be divided into four components such as : emissive component, ambient component, diffusive component, specular component.

Specular component:

This component shows the reflected light in a specific direction. It reflects on the basis of refection of incident light. The specular light depends on the position of observer with respect to the surface.

Specular component finds the strength of specular height by using a formula which is the multiplication of specular surface constant with specular intensity and with dot product of reflection direction and the direction of surface towards the view. It means it is determined by the angle between reflected vector and view vector.

Concept:

Relational algebra: It is a procedure-oriented language. In this, we use relation as values instead of numbers. It works on relational model. Main work is to retrieve data, perform operations such as insert, delete, update etc.

Explanation:

• Basic operations in relational algebra are: Select, project, union, set difference, Cartesian product, rename.
• Other operations are natural join, intersection, division.
• From the above options, operator that are included from mathematical set theory are intersection and Cartesian product.
• In mathematical set theory, intersection is used to find the common elements between two sets. It works same in relational algebra.
• Cartesian product is used to find the multiplication of two sets by including common elements only once.