UGC NET Paper 2: Computer Science 20th Dec 2018 Paper (Previous Year Paper)

The correct answer is 245.248.136.0/21 and 245.248.128.0/22

Since Half of 4096 post addresses must be given organization A, we can set the 12th bit to 1, include that bit into the network path of organization A. So the valid allocation of address to A is 245.248.136.0/21.

The 12th bit is set to 0, but we need only half of the 2048 address, 13th bit can be set to be 0 addresses to B is 245.248.128.0/22.

Hence the correct answer is 245.248.136.0/21 and 245.248.128.0/22.

Data:

Available Resources = R = 12

Max need per process = 4

Concepts:

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

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

For n process, max resource to be in deadlock = n × 3 = 3n

If one resource (tape drive) is added, any of the n 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

3n + 1 ≤ 12

3n ≤ 11

∴ n_max = 3

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.

In Readers-Writers problem, more than one Reader is allowed to read simultaneously but if a Writer is writing then no other writer or any reader can have simultaneous access to that shared object. So, Writers are given exclusive access to shared objects.

Hence option 1 is correct

Concepts:

Number of models is nothing but number of TRUE in final statement.

Using De Morgan’s Law

(¬ ​A ∨​ ¬ B ∨​ ¬ C ∨​ ¬ ​ D) ≡ ¬ (A ∧ B ∧ C ∧ D)

Truth Table:

15 models are there for given statement

Important Points:

(¬ ​A ∨​ ¬ B ∨​ ¬ C ∨​ ¬ ​ D) ≡ ¬ (A ∧ B ∧ C ∧ D)

Number of variables = 4

Statement possible = 2⁴ = 16

Since (A ∧ B ∧ C ∧ D) AND operation will give true statement only when all are TRUE

Therefore, number of models in (A ∧ B ∧ C ∧ D) = 1 and

number of models in ¬ (A ∧ B ∧ C ∧ D) = 16 – 1 = 15

Concepts:

A mutual exclusion (mutex) is a program object that prevents simultaneous access to a shared resource.

A critical section is a code segment that accesses shared variables and has to be executed as an atomic action. The critical section problem refers to the problem of how to ensure that at most one process is executing its critical section at a given time.

PROCESS:

Since process ‘Q’ is in the critical section then other processes P and R cannot be in the critical section. Therefore neither ‘P’ nor ‘R’ executes in their critical section.

Data:

1 word = 32 bits = 4 bytes

Memory size = 256K word = 2¹⁸ word

Indirect bits = 1

Number of registers = n = 64

Formula:

Number of bits needed to present a register = ⌈log₂ n⌉

Calculation:

Number of bits needed to present a register = ⌈log₂ 64⌉ = 6

Binary Instruction (32 bit):

1 + x + 6 + 18 = 32

∴ x = 7

Therefore 7,6 and 18 bits are there in operation code, the register code part and the address part respectively.

Scheduling Algorithm: Round-Robin

Time Quantum: 4 milliseconds

Gantt chart:

0 4 8 12 16 17 20 22

Process Table:

Therefore, the waiting time for P4 is 12 milliseconds.

Formula used:

TAT = CT – AT

WT = TAT – BT

Important Points:

Since arrival time is not given of processes is not given consider all the process arrive at time = 0 and by convention, the process with lowest id associated with it executes first, that is, P₁ followed by P₂ and so on.

Concepts:

A substring is a contiguous sequence of characters within a string.

Example:

String: “GATE”

Substring: G, A, T, E, GA, AT, TE, GAT, ATE, GATE and Λ (empty string or null string)

Therefore, number of substrings = 11

Formula:

If character is not repeated, then

${\rm{number;of;substring}} = \frac{{{\rm{n}} \times \left( {{\rm{n}} + 1} \right)}}{2} + 1$

Calculation:

String: “a d e f b g h n m p”

∴ number of characters = n = 10

Repetition is not present in a string

${\rm{number;of;substring}} = \frac{{10 \times \left( {10 + 1} \right)}}{2} + 1 = 56;$

• In computers, subtraction is generally carried out by 2’s complement.
• In two's-complement representation, positive numbers are simply represented as themselves, and negative numbers are represented by the two's complement of their absolute value;

Example:

Consider a 4-bit numbers

Range: (–2^4-1 to 2^4-1 – 1) → (–8 to 7)

Perform: 6 – 4 = 6 + (– 4)

(6)₁₀ = 0110

(4)₁₀ = 0100, 2’s complement of 4 = (–4)₁₀ = (1100)₂

0110 + 1100 = 10010 (discard the carry)

∴ 0110 + 1010 = 0010

(0010)₂ = (2)₁₀

A̅⋅B + A.B̅ + A.B

= A̅ . B + A(B̅ + B)

∵ B̅ + B = 1

= A̅.B + A

∵ x + yz = (x + y).(x + z)

= (A + A̅).(A + B)

= (A + B)

A̅⋅B + A.B̅ +A.B is equivalent to (A + B)

Data:

Number of Surfaces = 32 = 2⁵

Tracks per surface = 64 = 2⁶

Sectors per surface = 512 = 2⁹

bytes per sector = 512 = 2⁹

Formula:

number of sectors = s= no. surfaces × tracks per surface × sectors per track

bits required to specify a particular sector = ⌈log₂ s⌉

Calculation:

s= no. surfaces × tracks per surface × sectors per track

s = 2⁵ × 2⁶ × 2⁹ = 2²⁰

bits required to specify a particular sector = ⌈log₂ 2²⁰⌉ = 20

Data:

T₁ = 0.5 ns, T₂ = 5 ns and T₃ = 100 ns

H₁ = 0.7, H₂ = 0.8

Average access time = T_avg

Formula:

T_avg = H₁T₁ + (1 - H₁) H₂ (T₁ + T₂) + (1 - H₁) (1 - H₂) (T₁ + T₂ + T₃)

Since search time within cache is ignored

T_avg = H₁T₁ + (1 - H₁) H₂ (T₂) + (1 - H₁) (1 - H₂) (T₃)

Calculation:

T_avg = 0.5 × 0.7 + 0.3 × 0.8 × 5 + 0.3 × 0.2 × 100

T_avg = 0.35 + 1.2 + 6 = 7.55 ns

Notes:

1 ns = 10 ^{- 9} s

(153) ₂ → 1001 1001

NEG → 1’s complement of (153) ₂ → 0110 0110

Therefore AL = 0110 0110 since it is a positive number and no carry occurs

∴ SF = 0 and CF = 0

Therefore option 1 is correct.

Page Replacement Algorithm: FIFO

Reference to pages: 1, 2, 4, 5, 2, 1, 2, 4.

Page 1 and 2 are present in order: 1 and 2 in page frame:

Miss = page fault = 5

Important Points

M → miss

H → hit

• Self - relocating code takes always some address in memory and hence auto - increment addressing mode is not used for self - relocating code.
• In auto - increment addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store.
• Additional ALU is not required for effective address calculation if auto addressing mode is included in an instruction set architecture.
• Within a loop, auto - increment addressing mode can be used to step through all the elements of an array or vector.

Since statement (iii) is correct, therefore option 1 is correct.

Concepts:

After inserting each element, we will apply MAX-Heapify operation to get the MAX-Heap.

Insert: 42, 25 and 30

Insert: 40 apply MAX-Heapify

New order: 42, 40, 30, 25, 22

Insert: 35 apply MAX-Heapify

New order: 42, 40, 35, 25, 22, 30 and 26

Diagram:  resultant MAX_Heap

Concepts:

If there is match, A[i, j] = A[i – 1, j  – 1] + 1

If not match: max(A[i – 1, j], A[i, j – 1])

Table of longest common subsequence:

Therefore, length of longest common subsequence = x = 4

• Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph and time complexity is O(V​²).
• Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.
• A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v.
• Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices.

Concept:

In a symmetric key cryptographic system, both parties have access to the key. So, the first person has N-1 keys with other N-1 people, the second one has another N-2 with N-2 people (since 1 is already considered) and so on till 1.

Formula

$\sum_{i =1}^{i=n} =\frac{n(n+1)}{2}$

Calculation

Total number of keys required = 1 + 2 + 3 + … + (N – 2) + (N – 1)

where n = N – 1  

$\sum_{i =1}^{i=N-1}=\frac{N -1((N -1) +1)}{2} = \frac{N(N-1)}{2}$

Statement I: TRUE

Firewall is a device installed between the internal network of an organization and rest of the internet. It is designed to forward some packets and filter others.

It screens traffic going into or out of an organization. It filters all incoming packets destined for a specific host. It is a packet filter firewall or proxy-based firewall.

Statement II: TRUE

Virtual private network uses the global internet for both intra and inter-organization communication but require privacy in their internal communication.

It allows sharing of resource and privacy both at the same time. It can simulate an old leased network to provide certain desirable properties.

AND- OR search algorithm:

AND OR search algorithm is different from other algorithms in the way that it finds goal node at each state in order to reach the final goal state. It works in non-deterministic environment.

And OR search algorithm works in the following way:

1. It has to find a solution tree of subtrees.

2. Solution tree contains the root of the subtrees.

3. If a non-terminal AND node is in subtree and solution tree then all its children are in solution tree.

4. If a non-terminal OR node is in subtree and solution tree then exactly one of its children are in solution tree.

AND OR search tree may contain nodes that root identical subtrees (sub problems with identical optimal solutions) which can be unified. When unifiable nodes are merged, search tree becomes a graph and its size becomes smaller.

To transform figure on left side into figure on right side, two things must be done in this.

1. It requires anticlockwise rotation by 90 degree.

2. It requires translation along x-axis and y-axis.

In case of 2-D, rotation is done by:

\(P = ;\left[ {\begin{array}{*{20}{c}} {\cos \theta }&{ - ;sin\theta }\ {sin\theta }&{cos\theta } \end{array}} \right]\)

In case of 3-D rotation, also rotation is with respect to 2 on y-axis

\(P = ;\left[ {\begin{array}{{20}{c}} {\cos 90}&{ - sin90}&0\ {sin90}&{cos90}&0\ 0&0&1 \end{array}} \right] = ;\left[ {\begin{array}{{20}{c}} 0&{ - 1}&0\ 1&0&0\ 0&0&1 \end{array}} \right]\)

So, final matrix after rotation = \(\left[ {\begin{array}{*{20}{c}} 1&{ - 2}&0\ 1&0&0\ 0&0&1 \end{array}} \right]\)

Next step is translation, along x-axis translation factor is 6 units and along y- axis translation factor is 1 unit.

Translation matrix = \(\left[ {\begin{array}{*{20}{c}} 1&0&{tx}\ 0&1&{ty}\ 0&0&1 \end{array}} \right]\)

By putting t_x = 6 and t_y = 1

Final matrix will be = \(\left[ {\begin{array}{{20}{c}} 1&{ - 2}&{tx}\ 1&0&{ty}\ 0&0&1 \end{array}} \right] = \left[ {\begin{array}{{20}{c}} 0&{ - 2}&6\ 1&0&1\ 0&0&1 \end{array}} \right]\)

Concept:

Agent: An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. Example: human agents, robotic agents etc.

Agent is also equal to architecture and program combination.

Explanation:

Factors that are considered in agents are its performance measure, environment, actuators, sensors.

• Performance: safe, fast, legal, maximize profits.
• Environment: Roads, pedestrians, customers
• Actuators: steering wheel, accelerator, brake.
• Sensors: Cameras, speedometer, GPS, keyboard.

Environment types: fully observable, deterministic, static, dynamic, single agent, semi dynamic.

• Fully observable: It means to check everything is available to it via its sensors.
• Deterministic: It depends only on current state and agent’s action.
• Static: agent is deliberating over what to do
• Dynamic: agent should consult the world when choosing actions

Semi-dynamic: If the environment itself does not change with the passage of time but the agent’s performance does.

P: Software Reengineering is preferable for software products having high failure rates, having poor design and/or having poor code structure

This statement is correct. Reengineering is the examination, analysis, and alteration of an existing software system to reconstitute it in a new form and the subsequent implementation of the new form. This process encompasses a combination of other processes such as reverse engineering, reverse documentation, restructuring, translation and forward engineering. Software reengineering is preferable for software products having high failure rates, having poor design and having poor code structure.

Q: Software Reverse Engineering is the process of analyzing software with the objective of recovering its design and requirement specification.

This statement is correct. Software reverse engineering is the process of analysing software with the objective of recovering its design and requirement specification. In reverse engineering, it starts from implementation, then design phase, then analysis phase and then requirements phase.

Concept:

Coupling: It means interaction between components. It is the degree of interdependence between software modules.

Explanation:

Types of coupling are common coupling, control coupling, content coupling, data coupling, stamp coupling.

• Common coupling: It occurs when two modules share the same global data. It is the most undesirable because if we wish to change the shared data, all the procedures accessing this shared data will need to be modified.
• Content coupling: It occurs when one module modifies or relies on the internal working of another module.
• Control coupling: When modules communicate by passing control information. In this one module decides the function of other module or changes its flow of execution.

There are three generations in cellular telephony.

• First Generation: It was designed for voice communication using analog signals. Example: AMPS (Advanced mobile phone system) is one of the leading analog cellular system. It uses FDMA to separate channels in a link. AMPS operates in the ISM 800 MHz band.
• Second Generation: To provide higher quality mobile voice communication, these generation of cellular phone are required. These are used for digital voice communication. Example: D- AMPS, CDMA, GSM. The product of evolution of analog AMPS into a digital system is digital AMPS. D-AMPS uses TDMA and FDMA. GSM stands for global system for mobile communication. It provides duplex communication by using two digital bands.
• Third generation: It refers to a combination of technologies that provide a variety of services. It can provide both digital data and voice communication. Main goal of third generation cellular telephony is to provide universal personal communication. These are based on broadband CDMA. Example: IMT-DS, IMT-MC etc

Answer: Option 1

Explanation:

If y = 8 and |y| = 2^|x| then |x| = 3 since it finite it will be finite automaton.

If y = 8 and |y| = |x| then |x| = 8 since it finite it will be finite automaton.

Statement says for some y and hence L​₁​ and L₂ both are accepted by finite automata. Therefore, they are regular language

Concept:

Software requirement specification (SRS) is the starting point of the software development activity. Requirement specification phase consists of two basic activities: problem or requirement analysis and requirement specification.

Explanation:

In problem or requirement analysis, it deals with understanding of problem, goals and constraints. In second, the focus is on clearly specifying what has been found during analysis. Issues such as representation, specification languages and tools and checking the specification are addressed during this activity. Requirement phase terminated with the production of validate software requirement specification document.

Main purpose of SRS:

• To bridge the communication gap. It is the medium through which clinet and user needs are accurately specified.
• It forms the basis of software development.
• Helping the clients to understand their own needs.

The Software Requirement Specification (SRS) is said to be consistent if and only if no subset of individual requirements described in it conflict with each other.

Frame buffer has 10 bits per pixel and 8 bits are allocated for each R, G and B components.

As frame buffer has 10 bits. So, entries in color lookup table = 2¹⁰

8 bits for each component. Collectively 24 bits for all three components.

It means 24/8 = 3 bytes are for R, G and B component collectively.

Size of color look up table = number of entries in look up table × size of each entry

Size of look up table = 2¹⁰ × 3 = 3072 = (2¹⁰ + 2¹¹) Bytes

< td style = " text − align : center; vertical − align : middle; " > BASH < / td >

The above code of the following HTML5 codes will affect the horizontal as well as vertical alignment of the table content because:

• The text-align-align property determines the horizontal alignment of the content in or, such as left, right, or center.
• The vertical-align-align attribute determines the vertical alignment (such as top, bottom, or center) of the content in or.

BFS:

Breadth first search in artificial intelligence is implemented as FIFO. Path is find out by considering the number of edges in that path. Start from the root node, it considers all the nodes. But at the end, selects the path having lowest number of edges. If b is the branching factor and d is the depth. Then overall cost of BFS is O(b^d).

DFS:

It is based on the concept of LIFO as that of stack procedure. It considers the nodes one by one from root node to the leaf as a single path. If it does not terminate it can go to the infinity. If b is the branching factor and m is the depth. Then cost of DFS is O(bm).

Depth – Limited Search

In this, depth is specified first, and all the nodes are traversed till that depth then it goes on to next level. If b is the branching factor. Then overall cost of depth limited search is O(bl).

Iterative – deepening search:

It starts from root node i.e. depth 1, expands all the nodes and then goes on to the depth 2, expand all the nodes of that depth. In this way, it expands all the nodes. If b is the branching factor and d is the depth, then overall cost is O(bd).

Data warehousing:

It is a phenomenon that grew from huge amount of electronic data stored in recent years and from the urgent need to use that data to accomplish goals that go beyond the routine tasks linked to daily processing. Data warehousing is used in various applications such as: Trade, craftsmanship, financial services, transport industry, telecommunication etc.

Data warehouse architecture contains following points:

• Source system
• Source data transport layer
• Data quality control and profiling layer
• Metadata management layer
• Data integration layer
• Data processing layer
• End user reporting layer

Developing a data warehouse is no different from any other project. It requires complete planning, requirements, design, implementation. Data warehouse contains summary data that is not found in operational environment. Developing strategy of data warehouse is to establish virtual data warehouse. It is simply to build a copy of operational data from a single operational system and enable the data warehouse from a series of information access tools.

Diagram:

In ISO-OSI architecture, there are seven layers in this model. Starting from physical layer (layer 1), then data link layer, network layer, transport layer, session layer, presentation layer, application layer (layer - 7) respectively.

In this layer our main focus is on work of session layer.

Session layer:

Session layer is the network dialog controller. It establishes, maintains and synchronizes the interaction among communicating system. It is responsible for dialog control, token management and synchronization in the network.

• Dialog control: Session layer allows two systems to enter into a dialog. It allows the communication between two processes to take place in either half-duplex or full – duplex.
• Synchronization: It allows a process to add checkpoints to a stream of data.
• Token management: It prevents two parties from attempting the same critical operation at the same time

Clean room software engineering model is an incremental software paradigm for the development of zero defect and high reliability software using box structure specification, statistical quality control and certification.

It is a practical development and certification approach that uses statistical quality control to reduce software defects, to overcome unconscious copying of copyrighted code.

Characteristics of cleanroom software engineering approach:

• Incremental development process model
• Formal methods for specification and design
• Correctness verification
• Statistically based, independent testing

The development life cycle starts with a specification that not only defines function and performance requirements but also identifies operational usage of software and nested sequence of user function subsets that can be developed and tested as increments which accumulate into the final system.

Concept:

Loop invariant: It states that a desired property is maintained in the loop. Three parts are in this : implementation (it should be true before the loop runs), it must be true before and after each iteration of the loop and must terminate successfully after execution.

Explanation:

Given in the pseudo code: initially k = 0 and p = 0

After 1^st iteration:

For k = 0, p = p + 2^k = 0 + 2⁰ = 1

After 2^nd iteration:

For k =1, p = 1 + 2¹ = 3

After 3^rd iteration:

For k = 2, p= 3 + 2² = 7

Now , check which option gives same value of p when k = 0, 1 ,2 ,3….

Option 1: incorrect

p = 2^k - 1 and 0≤k < m

When k = 0, p = 2⁰ - 1 = 0

Option 2: correct

p = 2^k+1 - 1 and 0≤k < m          

When k = 0, p = 2⁰⁺¹ – 1 = 1          

When k = 1, p = 2¹⁺¹ – 1 = 3

When k = 2, p = 2²⁺¹ – 1 = 7

Option 3: incorrect

When k = 0, p = 2^0-1 = 0.5         

Option 4: incorrect

It is also giving same values, but it is not true in the case as k<=m in that, which should be k<m.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning V = V₁ U V₂ U V₃ ………… U V_k into at most k independent sets of G.

Properties of K- colourable graph are:

1. A cycle of length n>=3 is – chromatic if n is even and 3- chromatic if n is odd

2. A graph is bi- colourable (2- chromatic) if and only if it has no odd cycles.

3. A non - empty graph G is bi colourable if and only if G is bipartite.

S1: ​A heuristic is admissible if it never overestimates the cost to reach the goal        [correct]

A heuristic search carries the additional knowledge about the problem which helps in reaching the goal. A heuristic function is considered for finding the cost of the path. Cost is estimated if there is a path from a given node to goal node. When it reaches goal state, then at that instant cost will be zero. Heuristic search is admissible if it never overestimates the cost to reach the goal.

S2: ​A heuristic is monotonous if it follows triangle inequality property.              [Correct]

Heuristic search is a minimum cost solution to find the best path for a problem. A heuristic search is monotonous if it follows triangle inequality property. First, we visit a node to find an optimal path to it.  Triangle inequality problem: h(n₁) <= c (n₁ -> n₂) + h(n₂).

Statement i: Decidable

A language is decidable when there is a machine which halts for every string in that language and goes to non-final state for string not in the language. A finite automaton is a special case of a Turing machine which halts on all inputs that are in the language, so it is decidable.

Statement ii: Undecidable

Regular property of context free languages is undecidable.  This can be proved by taking regular language as Σ^*. Assume both G and R as part of input problem. For any family of languages, whether it is equal to other language is decidable if both L₁ and L₂ are subset of each other.

Statement iii: Undecidable

Turing machine is for recursive enumerable languages (for type 0 problems). Type 0 problems are undecidable. If we do not know about the Turing machine, it could possible that result for any two numbers will go into infinite loop and never halt. If it happens, then problem is undecidable.

S1: TCP handles both congestion and flow control          [Correct]

• TCP (Transmission control protocol) is a connection oriented reliable transport protocol. It provides process to process communications using port numbers.
• It provides services like flow control, error control, congestion control. A packet that is sent is known as segment in TCP.
• In TCP, transmission requires three phases: connection establishment, data transfer and connection termination. It uses three way handshaking mechanism for connection establishment and termination.

S2: UDP handles congestion but not flow control       [incorrect]

• UDP (User datagram protocol) is called a connectionless, unreliable transport protocol.
• It does not add anything to the services of IP except providing process to process communication.
• There is no flow control, error control and congestion control mechanism in UDP. To send a message from one process to another,
• UDP protocol encapsulates and decapsulates messages in an IP datagram.

Blow fish: 

• Blow fish is a symmetric or private key block cipher.
• It has a variable key length maximum up to 448 bits.
• Block size in blow fish mechanism is 64 bits. This algorithm is divided into parts: key expansion, data encryption and data decryption.
• It is fast than other algorithms. It simply uses addition, XOR, look up table with 32- bit operands. It requires less memory to run.

DES:

• It stands for data encryption standard.
• It is a symmetric key block cipher to encrypt the data.
• It operates on a 64 bit of plain text and uses a key of 56 bits. 48 bits of key is used in each round of DES.
• It divides the process in 16 rounds with an initial permutation and final permutation. 8 substitution boxes are uses in which each s-box map 6 bits to 4 bits.
• Permutation box is used. Then a final permutation is applied from right to left to yield cipher text.

IDEA:

• It stands for international data encryption algorithm. It is also a symmetric key block cipher.
• It takes 64 bits blocks as input and uses 128 bit key to encrypt the data. This algorithm runs eight and a half round for encrypting the data. It avoids substitution boxes and table lookups used in the block ciphers. It uses various key sub blocks and operates in XOR which is used for addition and subtraction purpose. It is divided into four parts each of which is divided into 16 bits.

RC5:

In RC5, number of keys are not of fixed size (all can be of variable length). Also, plain text can be of 32, 64 or 128 bits. Number of rounds are in between 0 – 255. Also, key size can be in between 0 to 255 bits or 1 to256 bits.

Hamiltonian graph:

A Hamiltonian graph is one which contain a Hamiltonian cycle. A Hamiltonian cycle is a cycle in which each vertex is visited exactly once.

Properties of Hamiltonian graph:

1. A graph has a Hamiltonian circuit if each vertex has degree >=3

2. If G= (V, E) has n>=3 vertices and every vertex has degree >=n/2, then G has a Hamilton circuit

3. If G is a graph with n vertices and n>=3, also deg(u) + deg(v) >=n, if u and v are not connected by an edge, then G has a hamiltonion circuit.

4. E(G) = ½(n - 1)(n - 2) + 2

State diagram:

State diagram is a behavioural model which contains states, actions and transition between states. They are used in object oriented modelling. It tell about the states that an object can visit. It is used to describe the dynamic behaviour of objects and could also be used to describe the entire system behaviour.

Use case diagram:  

It displays the relationship among actors and use cases. It describes how external entities interact with the system. A use case is a set of scenarios that describes an interaction between a user and system. Two main components in use case diagram are actor and usecase.

Class diagram:

It describes the structure of a system by showing the system’s classes, their attributes and the relationship among classes. It is used to describe the structural view of the system. It also displays relationships such as containment, inheritance, associations and others.

Activity diagram:

It displays a special state diagram where most of the states are action states and most of the transitions are triggered by completion of the actions in the source states. It is used to show the flow of business process or the logic of an object behaviour.

Suppose we have a string:  w = “TESTBOOK”

Length of the string = 9              // including null string in array w

int x = strlen(w);                                  // x= 9

this string is in the form of an array w.

where w[0]= T, w[1] = E, w[2] = S, w[3] = T, w[4] = B, w[5] = O, w[6] = O, w[7]= K, w[8]= null string

Iteration 1:

For (int i = 0; i < x; i++)                // condition becomes true as, 0< 8

c = w[i];                                        // c = w[0] = T

w[i] = w[x - i - 1];                        // w[0] = w[8-0-1]= w[7] = K

w[x - i - 1] = c;                            // w[8- 0 -1 ] = w[7] = T

Iteration 2:

For (int i = 0; i < x; i++)                // condition becomes true as, 1< 8

c = w[i];                                        // c = w[1] = E

w[i] = w[x - i - 1];                        // w[1] = w[8-1-1]= w[6] = O

w[x - i - 1] = c;                            // w[8- 1 -1 ] = w[6] = E

Iteration 3:

For (int i = 0; i < x; i++)                // condition becomes true as, 2< 8

c = w[i];                                        // c = w[2] = S

w[i] = w[x - i - 1];                        // w[2] = w[8-2-1]= w[5] = O

w[x - i - 1] = c;                            // w[8- 2 -1 ] = w[5] = S

Iteration 4:

For (int i = 0; i < x; i++)                // condition becomes true as, 3< 8

c = w[i];                                        // c = w[3] = T

w[i] = w[x - i - 1];                        // w[3] = w[8-3-1]= w[4] = B

w[x - i - 1] = c;                            // w[8- 3 -1 ] = w[4] = T

After this array becomes:

w[0]= K, w[1] = O, w[2] = O, w[3] = B, w[4] = T, w[5] = S, w[6] = E, w[7]= T, w[8]= null string

Iteration 5:

For (int i = 0; i < x; i++)                // condition becomes true as, 4< 8

c = w[i];                                        // c = w[4] = T

w[i] = w[x - i - 1];                        // w[4] = w[8-4-1]= w[3] = B

w[x - i - 1] = c;                            // w[8- 4 -1 ] = w[3] = T

Iteration 6:

For (int i = 0; i < x; i++)                // condition becomes true as, 5< 8

c = w[i];                                        // c = w[5] = S

w[i] = w[x - i - 1];                        // w[5] = w[8-5-1]= w[2] = O

w[x - i - 1] = c;                            // w[8- 5 -1 ] = w[2]= S

Iteration 7:

For (int i = 0; i < x; i++)                // condition becomes true as, 6< 8

c = w[i];                                        // c = w[6] = E

w[i] = w[x - i - 1];                        // w[6] = w[8-6-1]= w[1] = O

w[x - i - 1] = c;                            // w[8- 6 -1 ] = w[1]= E

Iteration 8:

For (int i = 0; i < x; i++)                // condition becomes true as, 7< 8

c = w[i];                                        // c = w[7] = T

w[i] = w[x - i - 1];                        // w[7] = w[8-7-1]= w[0] = K

w[x - i - 1] = c;                            // w[8- 7 -1 ] = w[0]= T

After this final array will be:

w[0]= T, w[1] = E, w[2] = S, w[3] = T, w[4] = B, w[5] = O, w[6] = O, w[7]= K, w[8]= null string

So, it outputs the content of the array in original order.

DATA SCRUBBING:

• Data scrubbing also known as data cleansing deals with detecting and removing errors and inconsistencies from data in order to improve the quality of data.
• Data quality problems are present in single data collections such as files and databases. It is a process to upgrade the quality of data before it is moved into a database warehouse.
• No matter how data are collected there will be some level of error in that. Error prevention methods can reduce the errors but cannot eliminate them.

Data scrubbing process:

1. It involves repeated cycles of screening, diagnosing, treatment and documentation of this process.
2. As patterns of errors are identified, data collection and entity procedures should be adapted to correct those patterns and reduce future errors.

Steps that are involved in this process are:

a) Screening:

It involves systematically looking for suspect features in assessment questionnaires, databases.

b) Diagnosis: 

It identifies the nature of defective data Treatment: It means deleting, editing or leaving the data as it is. It requires an in-depth understanding of all types and sources of errors possible during data collection and entry processes.

c) Documenting:

It changes entails leaving an adult trail of errors detected, alterations, additions and error checking and will allow a return to the original value if required.

Concept:

In mathematical logic, a statement is a sentence which is either true or false. It may contain words or symbols. In general, it has two parts: 1) assumption 2) conclusion.

A mathematical sentence is a sentence that states a fact and it becomes statement when it results in either true or false.

Explanation:

Statement (i): There will be snow in January

It is a mathematical statement because either there will be snow in January or there will not be snow in January. It has only two possible values either true or false.

Statement (ii): What is the time now?

In this case, there is no meaning of true or false. It is only asking the current time and you can answer that but not in true or false.

Statement (iii): Today is Sunday

It is a statement. As, it is true of Sunday and false on any other day. So, there are two possibilities of either true or false.

Statement (iv): You must study Discrete Mathematics.

It is not a statement. It is not giving meaning in true or false sense.

Statement I: Correct

L₁​ = {a^n+m bⁿ a^m | n, m ≥ 0} = {a^m aⁿ bⁿ a^m | n, m ≥ 0} 

The above language is accepted by Deterministic Pushdown Automaton (DPDA)and hence it is a context-free language (CFL)

Explanation:

• Push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack
• When again a’s come as input pop-up all the remaining a’s (“m” number of a’s) from top of the stack for “m” number of a’s coming as input.

Since we can have a Deterministic Pushdown Automaton (DPDA) for L₁​ so we can say L​₁​ is a CFL.

Statement II: Incorrect

L₂​ = {a^n+m b^n+m a^n+m |n, m ≥ 0} = {a^p b^p a^p | p ≥ 0} where n + m = p

The above language is not accepted by Pushdown Automaton (PDA)and hence it is a not context-free language (CFL)

Sequence in which the given packets are transmitted on the network by a host when a browser requests a web page from a remote server.

STEP 1:

DNS query is sent to Domain name server to convert the Domain name into its IP address.

Step 2:

TCP SYN request packet is sent by sender to establish a connection for data transmission.

Step 3:

HTTP GET request is used to request data from a specified IP address.

• In perspective projection, objects that are far away appear smaller, and objects that are near appear bigger.
• A perspective projection of an object is often considered more realistic than a parallel projection, since it more closely resembles human vision and photography
• Parallel projection is equivalent to a perspective projection where the viewer is standing infinitely far away
• Perspective projections preserve straight lines.

Query: SELECT * FROM Students S, Performance P WHERE S.Roll-No = P.Roll-No

Let R be the output relation of the above query:

R:

Query: SELECT S.Name, Sum (P.Marks) FROM R GROUP BY S.Name

Output:

S:

The number of rows returned by given query are 2.

Expression i: wx + w(x + y) + x(x + y)=x+wy

 LHS = wx + w(x + y) + x(x + y)

        = wx + wx + wy + x + x.y

        = x(w + w + 1 + y) + wy

        = x + wy  = RHS

Expression ii:  wx’(y+xz’)+w’x’)y = x’y

LHS = (wx’(y+xz’)+w’x’)y

       = (wx’y + wx’xz’ + w’x’)y

       = wx’yy + w’x’y

       = wx'y + wx’y

       = (w + w’)x’y = RHS

Both (i) and (ii) are true

De Morgan’s’ Law

$\overline {X + Y} = \bar X.\bar Y$

$\overline {XY} = \bar X + \bar Y$

Let P be the output of 1- NAND gate

${\rm{P}} = \overline {{\rm{A}}.{\rm{B}}}$

Let Q be the output of 1- NAND gate

${\rm{Q}} = \overline {\bar A + B}$

${\rm{Y}} = \overline {{\rm{P}} + {\rm{;Q}}} = \bar P\bar Qa$

${\rm{Y}} = {\rm{;}}\overline {\overline {{\rm{A}}.{\rm{B}}} ;} .;\overline {\overline {\bar A + B} } ;;$

Y = (A.B). (A̅ + B)

Y = A.B.A̅  + A.B.B

∵ A.A̅  = 0 and B.B = B

Y = AB

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

In IEEE-754 format, 32-bit (single precision)

(-1)^s × 1.M × 2^{E – 127}

Calculation:

Convert: 40.1 to binary

Step 1: convert 40

(40)₁₀ = (101000)₂

Step 2: convert .1 to binary

0.1 × 2 = 0.2           (0)

0.2 × 2 = 0.4           (0)

0.4 × 0.2 = 0.8        (0)

0.8 × 0.2 = 1.6        (1)

0.6 × 0.2 = 1.2        (1)

0.2 × 0.2 = 0.4        (0)  and so on

Given binary number is

(40.1)₁₀ = (101000.000110011001100…)₂

(40.1)₁₀ = 1.0100 0000 1100 1100 … × 2⁵

Signed (1 bit) = 1 (given number is negative)

Exponent (8 bit) = 5 + 127 = 132

∴ Exponent = (132)₁₀ = (1000 0100)₂

Mantissa (23 bits ) = 0100 0000 1100 1100 1100 110

(1100 0010 0010 0000 0110 0110 0110 0110)₂ = (C2206666)₁₆

(C2206666)₁₆ = 0xC2206666

Concept:

• In Unix like operating system, the fork system call is used for creating a new process where a process is a copy of itself, which is called the child process.
• The fork system call is usually a system call, implemented in the kernel.
• After a new child process is created, both processes will execute the next instruction following the fork() system call.
• If n times fork then total number of process create is 2ⁿ in which number of child processes created is 2ⁿ – 1

Example:

If 5 times fork system call is called then,

Total number of processes = 2⁵ = 32

Total number of child processes created = 2⁵ - 1 = 31

Data structure used is Queue, implement using linked list where processes are kept

From the above game tree, it is clear the value propagated at the root is 5.

Concept:

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

Example of DDL commands: CREATE, DROP etc.

Explanation:

DROP TABLE command:

The DROP TABLE command is used to drop an existing table in a database.

SYNTAX:

DROP TABLE table_name;

Important Point:

UPDATE command:

The UPDATE command is used to modify the existing records in a table

SYNTAX:

UPDATE table_name

SET column1 = value1, column2 = value2, ...

WHERE condition;

DELETE command:

The DELETE command is used to delete existing records in a table.

SYNTAX:

DELETE FROM table_name WHERE condition;

Notes

Remove table is not a command in SQL.

Given language is : L = {2^nk | k > 0, and n is non − negative integer number}

Case 1:

Consider n = 1,

Then k can be 1, 2 ,3,….

Strings possible in this case : {2, 2², 2³, 2⁴,…………}

DFA for this:

States possible with n = 1 are 2.

Case 2:

When n = 2

Then k can be 1, 2, 3….

Strings possible in this case : {2², 2⁴, 2⁶, 2⁸,……}

DFA for this:

States possible when n = 2 are 3.

So, in general we are getting n + 1 states in DFA

c- It represents country

∃c – it means there exists a country

Border(c, India) – it means border between India and c

Border(c, Nepal) – it means border between Nepal and c

Variables are two: India and Nepal

Given statement: “There is a country that borders both India and Nepal.”

AND is true only when Border(c, India) and Border(c, Nepal) is 1.

Country must have border with both India and Nepal. So, and operation supports it.

AND is denoted by ∧ in proposition logic.

Correct option is:

∃c Country(c) ∧ Border(c, India) ∧ Border(c, Nepal)

It means there exists a country c and it borders both India and Nepal.

Maximize z = -2x₁ – 3x₂

Check all the options one by one and put the value and find in which we are getting the maximum value which is also satisfying the given equations form.

Option 1: x​₁​ = 6, x₂​ = 2 and z = -18

Here, z is -18

x₁​ + x₂​ ≥ 2                      // 6+ 2 ≥ 2 or 8 ≥ 2 [true]

2x​₁​ + x₂​ ≤ 10                 // 2*6 + 2 <=10 or 10<=10  [true]

x​₁​ + x₂​ ≤ 8                     // 6 + 2 <=8  or 8<=8     [true]

Also, x₁ and x₂ are >= 0

Option 2:  x₁​ = 2, x₂​ = 6 and z = -22

Z = -2x​₁​ -3x₂             // z = -4 – 18 = -22

x₁​ + x₂​ ≥ 2                      // 2+ 6 ≥ 2 or 8 ≥ 2 [true]

2x​₁​ + x₂​ ≤ 10                 // 2*4 + 6 <=10 or 10<=10  [true]

x​₁​ + x₂​ ≤ 8                     // 2 + 6 <=8  or 8<=8     [true]

Also, x₁ and x₂ are >= 0

When we check option 3) and option 4), they are also satisfying these conditions. But maximum value of z is in option 3 i.e. -4.

Statement P: For a line with slope m>1, we should change the outer loop in line (4) to be over y.

Line 4) for x = x₁ to x₂ should be changed to be over y and slope m > 1

Slope of a line m = (y₂ – y₁)/ (x₂ – x₁). Because now it depends on x coordinates, to be over y it should depend on y coordinates.

Statement Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f.

It is clearly shown in the algorithm, that line (10) and line (12) are changing the values of d through incremental evaluation. i.e. adding d with itself.

d = d + (y₁​ - y₂) + (x₂​ - x₁)       ---- line (10)

d = d + (y₁ - y₂)                       ---- line (12)

R: The algorithm fails if d is ever 0

Algorithm does not fail when d is 0. because when d becomes greater than or equal to zero then it goes to line 12 and compute the value of. So, this statement is false.

T(n) = 2 T(sqrt(n)) + log n      ------------- (1)

Put n = 2^m

Take logarithm both sides,

Log n = m

Put value of n in (1)

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

Let, S(m) = T(2^m)

So, S(m) = 2 S (m/2) + m

Use master’s theorem:

Here a = 2, b = 2

${m^{{{\log }_b}a}} = ;{m^{{{\log }_2}2}} = m$

Now both the m^loga  and value of function are equal. So, complexity will be O(m log m)

Put value of m in terms of n.

So, complexity of given recurrence relation will be: O(logn log(logn))

Concept:

Cloud computing provides a flexible environment to use resources at low cost. Cloud computing is a web based, distributed computing using which information, resources and software are distributed among different users. All the resources are on web, so this is the reason that there come various ways to provide services.

Explanation:

Cloud computing is internet-based computing where customers do not own the physical infrastructure. All services are on internet. Various services in cloud computing model are as follows:

SaaS – It stands for software as a service. In this, application is hosted as a service to customers who access it via internet. It provides packaged business process offerings that live in cloud. In this, cloud contains stack such as operating system, application software etc.

IaaS – It stands for infrastructure as a service. It is responsible for providing virtualized computing resources, network resources with IaaS users assemble their own virtual cluster on which they are responsible for installing, maintaining, and executing their own software stack.

PaaS – It stands for platform as a service. It supplies all the resources required to build applications and services completely by using internet without having to download or install software. It includes application design, development and hosting.

Concept:

Linux is a version of Unix operating system. Linux has open source code.

It has three main components: kernel, system library and system utility.

It is portable, multi-programmed and secure.

There are various commands in Linux operating system which helps in performing various operations.

Explanation:

To print a file in Linux operating system, lp command is used also followed by the name of the file that is to be printed.

From given options, lpr is the command that is used to print a file in Linux.

Diagram of Linux:

Concept:

A grammar is LL(1) and LR(1) only if it is free from ambiguity and left recursion.

Ambiguous grammar: A grammar is known as ambiguous grammar when there is more than one derivation tree for a string.

Explanation:

Given grammar:

S ➝ A | B

A➝ a | c

B➝ b | c

Suppose we have to generate string “c”.

In this case we have two right most derivations possible for this string.

Case 1:

S -> A

S -> c                 // A-> c

Case 2:

S -> B

S - > c                 // B -> c

So, given grammar is ambiguous grammar. It cannot be LL(1) and LR(1).

Concept:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1: (L₁ ∪ L₂)’ – R

As context-free languages are closed under union and set difference but not under complementation. Therefore (L₁ ∪ L₂)’ is not a context-free language and hence (L₁ ∪ L₂)’ – R is also not a context-free

Option 2: L₁ – R is context-free

Every regular language is also closed under context-free language and the set difference of a context-free language from Regular Language is context-free. So, it is correct.

Option 3:  L’₁ is context-free

L₁ is a context-free language. According to the property, its complement can’t be context-free.

Option 4: L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect.

Concept:

Branch coverage:

It means each branch in a statement must be executed at least once during testing of program.

Statement coverage:

It means all the statements of the program code must be executed at least once during testing.

Explanation:

To achieve full statement coverage, all the statements must be executed.

Statement coverage = (number of statement executed)/ total number of statements

In above code, there are three test cases required to achieve full statement coverage.

Case 1: when if condition becomes true,

int f(int m, int n, boolean x, boolean y)

{

int res=0;

if(m<0) {res=n-m;}

return res;

}

These statements will be executed.

Case 2: when other two cases of else will execute, then all remaining statements will also execute. By, three tests, full statement coverage is achieved.

Branch coverage: It is decision coverage and covers both true and false conditions.

Decision coverage = (number of decisions exercises)/ total number of decision outcomes.

It checks for true and false cases. In the above given code, there will be 4 tests required to achieve full branch coverage.

So, value of (P, Q) = (3, 4)

Data:

red balls = 6  

green balls = 4

To Find:  The probability that two of the selected balls will be red and two will be green

Calculation:

Total balls = 6 + 4 = 10

4 balls from 10 balls can be selected in ¹⁰C₄

2 red balls can be selected in ⁶C₂ ways.

2 green balls from 4 green balls can be selected in ⁴C₂ ways.

Probability that two selected balls will be red and two will be green = $\frac{{^6{{\rm{C}}_2}{ \times ^4}{{\rm{C}}_2}}}{{^{10}{{\rm{C}}_4}}} = ;\frac{{15 \times 6}}{{210}} = ;\frac{3}{7}$ 

Important Point

Since red and green ball is asked, we have multiplied

Agile software development has a major influence for a number of changes in how software developers plan and coordinate their work , how they communicate with customers and stakeholders , how software development is organized in small , medium sized and large companies from telecom and health sectors.

It basically focus on adapting to change and delivering products of high quality through simple work processes.

In agile software development model, a large product is broken into small incremental builds. These are then solved in various iterations. In agile method, every build is treated differently.

Principles of agile software development model:

• Customer involvement: During the development of a software, we are not aware of all of its requirements initially. So, customer involvement is required in this to tackle all the necessary requirements so that product is development in an efficient manner and time.
• Embrace change: It is responsive to any change in the development process
• Incremental delivery: as in agile method, product is broken into small parts and each part of that is solved iteration wise. So, it is an incremental delivery process of software development.

Some other principles are working software, interaction between individuals etc. But following the plan is not in the principles of agile software development method.

Concept:

Software maintenance:

Any changes done in the software during its execution such as error correction, optimization etc. is software maintenance. Its objective is to preserve the value of software over time.

Explanation:

Types of software maintenance are:

Perfective maintenance: when there are new requirements from user side, then at that time changes made in the software is known as perfective maintenance. It makes the software more enhanced, clean structured, better than previous.

Adaptive maintenance: Changes done in the software environment that includes any work initiated as consequence of moving the software to different hardware or software is known as adaptive maintenance.

Preventive maintenance: It prevent software from future problems.

Corrective maintenance: It is related with fixing the errors. Changes done when there is defect or error in the software is known as corrective maintenance.

Function call: f(2, 3)              // m = 2 and n = 3

STEP 1:

float result = (float) m / (float) n;         // result = 2.0/ 3.0 = 0. 66

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66 + f (4, 9)

STEP 2:

float result = (float) m / (float) n;         // result = 4.0/ 9.0 = 0. 44

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66 + 0.44 + f (8, 27)

STEP 3:

float result = (float) m / (float) n;         // result = 8.0/ 27.0 = 0. 296

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66+ 0.44 + 0.296 + f (16, , 81)

STEP 4:

float result = (float) m / (float) n;         // result = 16.0/ 81.0 = 0. 197

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66+ 0.44 + 0.296 + 0.197 + f (32, 243)

STEP 5:

float result = (float) m / (float) n;         // result = 32.0/ 243.0 = 0. 131

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66+ 0.44 + 0.296 + 0.197 + 0.131 + f (64, 729)

STEP 6:

float result = (float) m / (float) n;         // result = 64.0/ 729.0 = 0. 087

if (m < 0 || n < 0)                      // condition is false, else part will execute

result += f(m2, n3);           // result = 0.66+ 0.44 + 0.296 + 0.197 + 0.131 + 0.087 + f (128, 2187)

STEP 7:

result = 1.813 + 0.058 + f (256, 6561)

STEP 8:

result = 1.871 + 0.039 + f (512, 19683)

STEP 9:

result = 1.91 + f (1024, 59049)

STEP 10:

result = 1.91 + 0.017 + f(2048, 177,147)

Therefore the best approximates the value of f(2,3) is 2.

Concept:

PERT (project evaluation and review technique) and CPM (critical path method) are two techniques to solve project scheduling problems. These are based on network-oriented techniques.

There is a slight difference between these two. It is that time estimation in case of CPM is deterministic and in case of PERT, it is probabilistic.

Explanation:

PERT/CPM consists of four parts:

1. Planning: In this step, project is divided into small projects. Then these are again divided into activities.
2. Scheduling: It prepares a time chart to show the start and finish of each activity.
3. Allocation of resources: To complete a project, resources are required which is the work of this phase.
4. Controlling: progress report from time to time is examined and a technical control should be implied over the project.

Networking representation of PERT/CPM includes activities, events, sequencing.

• Activities: Any operation which has some start and end, that is known as activity. Types are predecessor activity, successor activity, dummy activity.
• Events: Event specifies the completion of some activity and start of new one. Events are classified as merge event, burst event, merge and burst event. Merge event represents joining of two or more activities of an event (or completion of two or more events), while burst event is when one activity is leaving the event.

Statement P*: Back-face culling is an example of an image-precision visible-surface determination.*

This statement is incorrect. Back face culling is a technique used to eliminate invisible back facing polygons (which are not facing viewer) from further processing.  Principle behind back face culling is that if a polygon on a 3D model is facing away from you, then it cannot be seen.

Statement Q: Z-Buffer is a 16-bit, 32-bit, or 64-bit field associated with each pixel in a frame buffer that can be used to determine the visible surface at each pixel.

This statement is correct.  Z buffer is a visible surface detection method. This is also known as depth buffer method. In this, depth values are stored for each position (x, y) during the surface processing. Each surface is processes separately in this. Depth values for pixel are compared and smallest z value determines the color or surface to be displayed. Z- buffer is a 16 – bit, 32 – bit or 64 – bit field associated with each pixel in a frame buffer that can be used to determine the visible surface at each pixel.

Truth Table:

From the above truth table,

Equivalence means p ⇔ q

Contrapositive means p ⇒ q : ¬ q ⇒ ¬ p

Converse means p ⇒ q : q ⇒ p

Implication means p ⇒ q

Important Point:

p ⇒ q ≡ ¬ q ⇒ ¬ p

(i) Every logic network is equivalent to one using just NAND gates or just NOR gates.

This is true. As NAND and NOR are universal gates. Every logic network is equivalent to using just NAND or NOR gate. NAND or NOR are complement of AND and OR gate respectively. Individually they are a complete set of logic as they can be used to implement any other Boolean function or gate.

(ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs.

This statement is true. Boolean functions can be represented with the labelled acyclic graph.

Example:

(iii) No two Boolean algebras with n atoms are isomorphic.

Every finite Boolean algebra is isomorphic to an algebra of sets. Every finite Boolean algebra has 2ⁿ elements with n generators. In Boolean algebra, the immediate successors of minimum element are called as atoms. All Boolean algebra of order 2ⁿ are isomorphic to each other.

(iv) Non-zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms.

As explained in option 3). All Boolean algebra of order 2ⁿ are isomorphic to each other. If there is a set A = {a₁, a₂, ….., a_n} contains set of all atoms of B where B = [and, or, not], then every non zero element of Boolean algebra can be expressed uniquely as join of subset of A. So, this given statement is incorrect.

Concept:

Decidable language: A language is decidable if there exists a Turing machine which halts or accepts it.

Explanation:

A recursive language L is given.

Statement 1: Is L = ф?

This is emptiness property. Recursive languages are not decidable for emptiness problem. Problem whether a recursive language is empty cannot be solved.

Statement 2: Is w ∈ L, where w is a string?

It means membership property of recursive language. Recursive languages are decidable for membership property. If any string is in the language than either it halts in final state or accepted by Turing machine. So, it is decidable.

Statement 3: Is L = R, where R is given regular set?

Whether a recursive language is regular, is undecidable.

Statement 4: Is L = Σ?*

As, language is decidable when there is Turing machine which halts in final state. There no algorithm which can decide this property of recursive language. So, it is undecidable.

Greedy best – first search:

It selects that path which appears best at the time when it is needed. It uses both the depth first and breadth first search algorithm to find the best path. It selects a code for expansion if optimal path to that node has been found.  Expand the nodes by considering the nodes closest to the goal node. Disadvantage of this search algorithm is that it can go into infinite loop using DFS.

A search:*

It is also used for best first search. It also find the best path by using heuristic function h(n) and start from the first node, it reaches the goal node. It has the features of greedy best first search algorithm. In this , f(n) = g(n) + h(n), where h(n) is the heuristic function , f(n) is the estimated cost to reach the goal node and g(n) is the cost to reach a node from the start state. In this , time complexity depends on the heuristic function.

Recursive best – first search:

It is a search algorithm that is linear with respect to the maximum search depth. It can visit the same node multiple times. It is similar to the recursive implementation of depth first search algorithm. It works by maintaining on the recursion stack the complete path to current node being expanded as well as immediate nodes on that path. That’s why it suffers from excessive node generation.

Iterative deepening A search:*

It finds the shortest path between start node and any member of goal nodes. It is similar to iterative deepening depth first search algorithm. It does not go to same node again and again. It just explores the most promising node. It avoids substantial overhead associated with keeping the sorted queue of nodes.

IP address that is 4 bytes long is known as IPv4 address. IPv4 address uniquely and universally defines the connection of a device to the internet. IP addresses are unique.  There are two notations of an IP address:

Binary notation and decimal notation.  An IP address consists of both host and network address.

Two types of classification of IP addresses are: classful addressing and classless addressing

Classful addressing:  In this address space is divided into five classes: class A, B, C, D and E.

• In class A, one byte is for network ID and three bytes are for host ID.
• In class B, two bytes are for network ID and two bytes are for host ID
• In class C, three bytes are for network ID and one byte for host ID.

Diagram:

Concept:

Candidate key: it is the set of attributes which uniquely identifies a relation. It is also known as superkey with no repeated attributes.

Explanation:

Given relation R = {A, B, C, D, E}

A ➝ B

B, C ➝ D

E ➝ C

D ➝ A

Find the closure of keys given. If all the attributes of relation are present in the closure, then it will be the candidate key of that relation.

Option1: AEF, BEF and DEF

(AEF)⁺ = {A, E, F, B, C, D}

(BEF)⁺ = {B, E, F, C, D, A}

(DEF)⁺ = {D, E, F, C, A, B}

These are the candidate keys of given relation.

Option2: AEF, BEF and BCF

(AEF)⁺ = {A, E, F, B, C, D}

(BEF)⁺ = {B, E, F, C, D, A}

(BCF)⁺ = {B, C, F, D, A}        // E is not present in the closure. Not the candidate key

Option3: AE and BE

(AE)⁺ = {A, E, C, B, D, }       //F is not present, not a candidate key

(BE)⁺ = {B, E, C, D, A}        //F is not present, not a candidate key

Option4: AE, BE and DE

(AE)⁺ = {A, E, C, B, D, }       //F is not present, not a candidate key

(BE)⁺ = {B, E, C, D, A}        //F is not present, not a candidate key

(DE)⁺ = {D, E, A, C, B}        //F is not present, not a candidate key

Concept:

Kruskal’s algorithm: It is used to find the minimum spanning tree of a graph. It uses the make set procedure. First, all the edges are sorted in ascending order and then added into the set. If the vertices corresponding to that edge are already in the set than that edge will not be considered.

Explanation:

Edges in sorted order :

BI = 1                                     

CD = 1

HG = 1

BC= 2

HI = 2

GI = 2

HA =2

AI = 3

GF = 3

AB = 4

FI = 4

EI = 4

CI = 4

DI = 5

DE = 5

FE = 6

Set of edges: {A} {B} {C} {D} {E} {F} {G} {H} {I}

= {A} {B, I} {C} {D} {E} {F} {G} {H}          // edge BI is taken

= {A} {B, I} {C, D} {E} {F} {G} {H}          // edge CD is taken

= {A} {B, I} {C, D} {E} {F} {G, H}            // edge GH is taken

= {A} {B, I, C, D} {E} {F} {G, H}             // edge BC is taken

= {A} {B, I, C, D, G, H} {E} {F}                 // edge HI is taken

= {A, B, I, C, D, G, H} {E} {F}                 // edge HA is taken

= {A, B, I, C, D, G, H, F} {E}                  // edge GF is taken

= {A, B, I, C, D, G, H, F, E}                  // edge EI is taken

Now, all the vertices are covered, no need to consider remaining edges.

Spanning tree is: 

weight of this spanning tree = 2 + 1 + 3 + 2 + 4 + 1 + 2 + 1 = 16

Concept:

Dirty bit: Dirty bit is associated with a block of cache memory and it is used to show the page that is modified after being loaded into cache memory.

Explanation:

During write back police in cache, dirty bit concept is used.

Write back means updates are written only to the cache. When line is modified it’s dirty bit is set and when the line is selected for replacement, the line needs to be written to main memory only if it’s dirty bit is set.

In write back, we first write the cache copy to update the memory. Number of write backs can be reduced if we write only when cache data is different from memory. It is done by dirty bit or modifying bit. It writes back to the cache only when dirty bit is set to 1. Thus, write back cache requires two bits one is valid bit and another is dirty bit.

Diagram:

Concept:

Software maturity index: It is used to determine the readiness for release of a software system. It is useful when changes, like addition or deletion of modules in the software system taken place.

Formula:

Software maturity index (SMI) = [M_t – (F_c + F_a + F_d)]/M_t

Where, M_t = number of modules in current release of software

F_c = number of modules that are changed

F_d  = number of modules that are deleted

F_a = number of modules that are added.

Calculation:

Given M_t = 940

F_c = 90

F_a = 40

F_d = 12

SMI = [940 – (90 + 40 + 12)]/ 940

SMI = [940- 142]/ 940

SMI = 798/ 940

SMI = 0.8489 (approx.. 0. 849)

Consider all the options one by one:

1. If x ≤ y and y ≤ z, then x ≤ z

This is true by transitive property. As x ≤ y and y ≤ z, then x should be less than or equal to z.

2)  If x ≤ y and y ≤ x, then x=y

 As x<=y, it means x ∨ y = y         //given in question

Y<=x, means x ∨ y = x

Here, x ∨ y = y = x

So, this is true.

3. If x < y and y < z, then x ≤ y

In this, it says that x< y which means

1. x< =y where,
2. x should not be equal to y.

But in this only first condition is given, second is not present. So, it is false.

4. If x < y and y < z, then x < y

This statement is true. As x< y, then x < y which is same in both the cases.

Data:

Number of internal nodes of degree 1 = 4

Number of internal nodes of degree 2 = 3

Number of internal nodes of degree 3 =3

Formula:

Number of leaf nodes = sum of degree of all internal nodes – total internal nodes + 1

Calculation:

Total number of internal nodes = 4+ 3 + 3 = 10

Sum of degree of all internal nodes = (4 × 1) + (3 × 2) + (3 × 3) = 4 + 6 + 9 = 19

Number of leaf nodes = sum of degree of all internal nodes – total internal nodes + 1

= 19 – 10 + 1 = 10

Alternate Method:

In the question only out-degree is given for a node:

Since it is a tree every node will have 1 in-degree (except root node and the root node is also an internal node)

Four nodes with out-degree 1 and one root is definitely a root

The root will have 0 in-degree and 1 out-degree ∴ total degree of the root node is 1

other 3 nodes will have 1 in-degree each and 1 out-dree

Similarly, other nodes degree will be increased by 1

and  each leaf node will have 1 in-degree

By handshaking lemma:

Total number of node (n) = internal node(10) + leaf node(L)

2(n - 1) = (1× 1 + 3 × 2) + 3× 3 + 3× 4 + L× 1

2((10 + L) - 1) = 28 + L

20 + 2L - 2 = 28 + L

L = 10

Let B = people travelled by bus

T = people travelled by train

A = people travelled by automobile

B = 30