UGC NET Paper 2: Computer Science July 2018 Paper (Previous Year Paper)

Concept:

Finite state machine accepts L

L = {a, b, aaab, abbb, aaabbb, baaa, bbba, bbbaaa}

Therefore, finite state machine accepts any string of odd number of a’s and odd number of b’s

Explanation:

Option 1: any string of odd number of a’s

String ‘a’ is not accepted by finite state machine. Therefore option 1 is incorrect

Option 2: any string of odd number of b’s

Since string ‘b’ is not accepted by finite state machine. Therefore option 2 is incorrect

Option 3*:* any string of even number of a’s and odd number of b’s

Since string ‘aab’ is not accepted by finite state machine. Therefore option 3 is incorrect

XML:

XML stands for extensible mark-up 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 has a proper starting and closing tag.
• An XML document having correct syntax is termed as “well-formed “.
• The purpose of DTD is to define the structure and legal elements and attribute of an 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.
• The definitions in an XML document are said to be valid when the tagging system and definitions in the DTD are all in compliance.

Consider the given code :

STEP 1 :

class simple

{

public static void main(String[ ] args)

{

simple obj = new simple( );               // it creates an object of class simple

obj.start( );                                          // then calls the function start

}

STEP 2:

void start( )

{

long [ ] P= {3, 4, 5};          // it creates an array with three integers.

long [ ] Q= method (P);        /* function method P is called here, which is then reflected in  array Q */

System.out.print (P[0] + P[1] + P[2]+”:”);

System.out.print (Q[0] + Q[1] + Q[2]);

}

STEP 3 :

long [ ] method (long [ ] R)

{

R [1]=7;               /*it indirectly change the value of second element of array to 7 which reflects in array Q. Also address of P is passed as an argument, it changes the value of array P second element to 7 */

return R;

}

STEP 4:

Now ,  Array P becomes , long [ ] P= {3, 7, 5};       

Array Q becomes , long [ ] Q= {3, 7, 5};            

System.out.print (P[0] + P[1] + P[2]+”:”);             // it print the sum of elements of array P i.e. (3+7+5 = 15)

System.out.print (Q[0] + Q[1] + Q[2]);             //// it print the sum of elements of array Q i.e. (3+7+5 = 15)

Concept:

Statically typed programming language are those in which variables need not be defined before they are used. It needs explicit declaration of variables.

Explanation:

P: C programming language has a weak type system with static types.

Statement P is correct. C programming language is weakly typed language. In this, variables are not bound to a specific data type. If there is need of type checking in C, it can be done at compile time or at run time. But in case of static type, C has a weak type system.

Q: Java programming language has a strong type system with static types.

Statement Q is correct here. In java, every variable must be declared with a data type. Once variable is declared in java, its data type cannot be changed. In this, each type of data is pre- defined. With static types, java programming language is strongly typed language.

Data:

Period (T) = 100 ms = 100 × 10^-3 sec  = 0.1 sec

Formula:

${\rm{frequency;}}\left( {\rm{f}} \right) = \frac{1}{{\rm{T}}}$

Calculation:

${\rm{f}} = \frac{1}{{\rm{T}}}; = \frac{1}{{0.1}} = 10;Hz$

${\rm{f}} = \frac{{10 \times {{10}^3}}}{{{{10}^3}}} = {10^{ - 2}}{\rm{;KHz}}$

Concepts:

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

Sentence.: B ∨ C

Truth Table:

<br>

12 models are there for given Sentence.

Tips and Tricks:

Number of variables = 4

Statement possible = 2⁴ = 16

Since (B ∨ C) OR operation between two variables ∴ ¾ of total cases will be true.

Therefore, number of modes = ¾ × 16 = 12

S1 : The ‘final’ keyword applied to a class definition prevents the class from being extended

through derivation.           [True]

A variable in java can be declared as final. Doing so prevents its contents from being modified. A final variable is essentially a constant. Methods declared with keyword ‘final’ cannot be overridden. Sometimes, final keyword is used to prevent a class from inheritance. So, final keyword applied to a class definition prevents the class from being extended through derivation.

S2 : A class can only inherit one class but can implement multiple interfaces.       [true]

This statement is correct. An interface in java is a kind of blueprint for a class. It is uses to achieve abstraction. A class that implements an interface can inherit the abstract methods of the interface. A class can only inherit one class but can implement multiple interfaces. Interfaces are not extended by a class, they are implemented by the class. Multiple inheritance is not allowed in java.

S3 : Java permits a class to replace the implementation of a method that it has inherited. It

is called method overloading.             [false]

When a class has more than one method with same name, then it known as method overloading while arguments are different. When java permits a class to replace the implementation of a method that it has inherited, it is known as method overriding. So, given statement is incorrect.

Data:

Frame buffer width = 640 pixels

Height = 480 pixels

Color depth = 1 bit per pixel

Access time for each pixel = 200 ns

Calculation:

Frame buffer size (in bits) = 640 × 480 × 1 = 307200 bits

Access time for 307200 bits (1 frame) = 307200 × 200

= 61440000 ns = 0.06144 seconds

As, 0.06144 seconds makes = 1 frame

1 seconds makes = 1/0.06144 = 16.27604166 frames

So, refresh rate = 16. 27604166 frame per sec (approx. 16 frames per sec)

Statement S1: The Painter’s algorithm sorts polygons by depth and then paints (scan - converts) each Polygon on to the screen starting with the most nearest polygon.

This statement is not true. Painter’s algorithm is used while projecting a 3D view on a 2D screen to ensure that which polygons are visible, and which should not.

Painter algorithm sorts polygons by depth, and then paints the farthest polygon first.

Statement S2:  Backface Culling refers to eliminating geometry with backfacing normals.

This statement is true. 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.

Backface curling don't render the curves, which are backface, and not visible. So, it enhances the rendering time.

Concept:

Scaling:

In this, the size of an object is increased or decreased by changing the dimension. Representation of the scaling matrix is:

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

Translation:

It moves an object from its original position to a new position by adding a translation factor with the original coordinates. It does not change the size. Translation matrix is represented as :

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

Explanation:

Given scalar matrix

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

Translation matrix will be:

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

If we do, first translation of (1,1), then scaling of a vector (2,1), then we get the original matrix. So, multiply scalar matrix with translation matrix of the specified vector and finally, we get the matrix M.

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

Concept:

Chomsky normal form

S → AB

A → a

B → b

Length of string = n

Length of the derivate of string n in context free grammar:

2|n| – 1

Example:

If we need to generate ab (string of length 2)

S → AB

S → aB

S → ab

Number of steps = 2 × 2 – 1 = 3

Concept:

Endianness: it refers to the bytes order in which data stored in memory and tells about the order of byte transmission. Two types are there: little endian and big endian

Little endian: In this case, LSB byte stores first (at lower address) and then MSB (at high address).

Big endian: In this, MSB byte stores first, it means at lower address and LSB at higher address. It is reverse of little endian.

Explanation:

m.two [0] = 5;                // in print function, it prints 5

m.two [1] = 2;              // it prints 2 as value of m.two[1]

Now, it is given that

union saving

{

short int one;                  /*as short int occupies 2 bytes, we have to arrange m.two[0] and m.two[1] into m.one by using little endian method. */

char two[2];

};

So, while doing this, value 5 is stored in lower address and 2 will be stored in higher address. In binary representation, it will become: 00000010 00000101

It decimal notation is: 517

Consider CASE (a) :

Initially p =0 and q = 1;

When swap (p, q) is called.

void swap (int a, int b)

{

int temp;             // a variable temp is declared

temp = a;             // temp = a = 0

a = b;             // a = b i.e. a = 1

b = temp;        // b = temp i.e. b = 0

}

Here, values are changing in the function, But as function call is “call by value” here. So, changes will not reflect back to the main function. Contents of p and q are not swapped here.

CASE b:

Initially p = 0 and q = 1

When swap (p, q) is called.

void swap (int &a, int &b)                      

/* it is call by reference, function parameters are as reference types. Final changes will get back to main function. */

{

int temp;                

temp = a;                 

a = b;                       

b = temp;                 

}

In this case, values get swapped .

CASE c:

Initially p = 0 and q = 1

Swap function is :

void swap (int *a, int *b)

{

int *temp;

temp = a;

a = b;

b = temp;

}

Here, it is pass by pointer.  Values get swapped but there are two calls to swap function. So, final value of p and q remain same at the end of the program.

Concept:

In Javascript, this keyword holds the reference to an object. It may be different each time the function is called. In global execution context (outside of a function), “this” refers to the global object whether in strict mode or not. Inside a function, value of “this” keyword depends on how function is called.

Explanation:

Given code :

var y= ’’12”;

function f( ) {

var y=’’6”;

alert (this.y);

function g( ) {alert (y); }

g( );

}

f( );

In this Javascript code, alert box appear two times. So value of m becomes .

First alert box will show the value of y as 12, as it takes the global value which is outside from the function. So, d₁ becomes 12.

Second alert box show the value of y as 6. It takes the local value which is inside the function. So, d₂ becomes 6.

Concepts:

Shortest remaining time first (SRTF), is a scheduling method that is a pre-emptive version of shortest job first (SJF).

In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute.

Explanation:

At t = 0:

Only Process P₁ is available and hence P₁ is executed for 1 ms.

At t = 1:

Process P₁ and Process P₂ are available, between them P₂ has least burst time. Therefore, P₁ gets pre-empted and hence P₂ is executed for 1 ms.

At t = 2:

All three process are available. Since P₂ is having least burst time it executes till its completion followed by Process P₁ and process P₃ respectively

Gantt chart:

 

Preemptive SJF scheduling is equal to SRTF

Concept:

Estimation is the process of finding how much time, money and effort will be used to develop a software. So, main terms are development effort, time, and development cost.

Data:

Size of code = 33480 LOC (lines of code)

Average productivity for P = 620 LOC per person-month

Number of software developers = 6

Average salary of a software developer = 50,000 per month

Formula:

Development effort = $\frac{{{\rm{size}}}}{{{\rm{productivity}}}}$

Development time = $\frac{{{\rm{development;effort}}}}{{{\rm{number;of;developer}}}}$

Development cost = development time × persons to develop software × salary of each developer

Calculation:

Development effort = $\frac{{33480}}{{620}} = 54{\rm{;person}} - {\rm{month}}$ 

Development time = $\frac{{54}}{6} = 9{\rm{;months}}$

Development cost = 9 × 6 × 50000 = 2700000 = 27 lacs

Product complexity:

• Product complexity is related with software complexity. Complexity of any software is measured in terms of software cost estimation.
• There are various cost estimation models used to estimate the complexity of the software. One such model is COCOMO. Product complexity is described as a determinant of software development time.

<br>

Structured system analysis:

• It is a software requirement definition. The primary objective of this is to deliver the requirements as specified in the feasibility report.
• It involves accuracy, timeliness and comprehensiveness of the system output. More clearly defined logical method for developing system that meet user requirements has led to new techniques that can improve productivity of analysts and programmers.

<br>

Coupling and cohesion: These two are related to software design.

• Software coupling defines that how two modules interdependent on each other. Low coupling is desirable in the system.
• Cohesion describes the intra - dependence of modules. High cohesion is desirable.

<br>

Symbolic execution:

• Symbolic execution is a validation technique, or we can say that it is a software testing technique.
• In this, data is represented as symbolic values with expressions. It tests the program by using a flow graph. When testing is done at the end of completion of software then that is known as validation testing.

Source code management is used to control or track the modification done in a software. When software grows, lines of code increases with it and then to manage that complex software becomes difficult. At that time, source code management is required to manage all the counts and lines of code. It is the part of software configuration management. It is also known as revision control.

Main points of source code management:

1. It provides synchronization by managing the complex code.

2. Complex point is that there is possibility of multiple versions.

3. It is related with team workflow that defines how source code management will be done and which type of tools should be used

4. It controls project forking. Project forking is when other developers takes copy of a source code and then used it for any other development.

5. it provides versions to the program. Each version has a timestamp.

6. It allows only authenticated access for commits.

7. It revise history of files so that changes can be tracked.

Concept:

Ambiguous grammar:

A grammar in which there exists a string for which two derivation trees are possible, then it is known as ambiguous grammar.

Explanation:

G₁: S → SbS|a

String: “ababa”

Two derivation trees (parse tree) is possible. So, grammar G₁ is ambiguous

G₂ : S → aB|ab, A → AB|a, B → ABb|b

String: “ab”

Two derivation trees (parse tree) is possible. So, grammar G₂ is ambiguous

Concept:

A grammar G = (V, T, S, P) is said to be context sensitive if all productions are of the form x → y where x, y, belongs to (V U T)⁺ and |x| ≤ | y|.

Languages that are generates from context sensitive grammar is known as context sensitive languages.

Relation between languages and their automaton.

Explanation:

• Context sensitive languages are recognized with the help of linear bounded automata. A linear bounded automaton has an unbounded tape, but usable part of the tape is restricted as compared to Turing machine.
• In linear bounded automata, there are two end markers [ left end marker, right end marker ]. Read write head cannot move to the left or right of these markers.

Language L = {aⁿ bⁿ cⁿ: n > = 1}

• It is accepted by linear bounded automata. It is a context sensitive language. A push down automata cannot accept this language.

As, it requires more than one stack which is available in linear bounded automata. In this, each a, b and c are replaced by x, y and z respectively. At the end, original symbols are checked if they are rewritten or not.

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

Statement S₁ is correct.

Reason:

• The equivalence of two Turing machines is undecidable. There exists no algorithm that can find if two Turing machines accept the same language or not.
• There exists a machine M₂ that accepts the same language as accepted by Turing machine M₁ but, if two Turing machines are equal or not, is not decidable. This is a non-trivial property in Turing machines.

Statement S₂: The problem of determining whether a Turing machine halts on any input is undecidable.

Statement S₂ is correct.

Reason:

It is related to the halting problem of Turing machine. A recursive language is decidable if there exists a Turing machine that either halts or rejects an input. But it cannot be decided whether it halts on any input. According to the concept of rice theorem, it is undecidable.

Language A = {0ⁿ 1ⁿ 2ⁿ | n = 1, 2, 3, .........}

It is context sensitive language.

• This language cannot be a context free grammar. Since all 0, 1 and 2’s is equal in number.

Reason:

If we take the case of push down automata. Then first push all the 0’s into the stack then with each 1 pop all 0’s. But at the end, there is no symbol at the stack and input is remaining. So, it is not accepted by push down automata and cannot be context free grammar.

• It is accepted by linear bounded automata with the help of forward and backward movement of tape.

Machine that accepts Language A:

Concept:

In slotted aloha, there are time slots for the stations to transmit the data. Stations can transmit data in time slots. Stations have to wait for their time slots to transmit the data.

Formula:

Throughput of slotted aloha = G× e^-G

Calculation:

Bandwidth = 200 kbps

It transmits 200 frames using shared channel

Frame transmission rate $= \frac{{200}}{{200}} = 1;ms$

System produces 250 frames per second

So, in 1 second frames are = 250

In 1 ms frames are = 250 × 1 ms = (250) × 10^-3 = ¼

So, G= ¼

${\rm{S}} = {\rm{;}}\frac{1}{4} \times {\rm{;}}{{\rm{e}}^{ - \frac{1}{4}}} = 0.195$

Throughput of system = 250 × 0.195 = 49 frames

Concept

Range of each octet (8 bit) of decimal notation of an IPv4 address is from 0 to 255.

Explanation:

10000001 .00001011. 00001011 .11101111

1^st Octet → (10000001)₂ = 2× 2⁷ + 1×2⁰ = (129)₁₀

2^nd Octet → (00001011)₂ = 2× 2³ + 1 × 2¹ + 2 × 2⁰ = (11)₁₀

3^rd Octet → (00001011)₂ = 2× 2³ + 1 × 2¹ + 2 × 2⁰ = (11)₁₀

4^th Octet → (11101111)₂ = 1× 2⁷ + 1 × 2⁶ + 1 × 2⁵ + 2 × 2³ +1× 2² + 1 × 2¹ + 2 × 2⁰ = (239)₁₀

Decimal representation is 129. 11. 11. 239

Statement a:

Advanced Mobile Phone System (AMPS) is a second-generation cellular phone system.

This is statement incorrect

Reason:

• An advanced mobile phone system is an analog cellular system. It uses FDMA to separate channels in a link. It operates in ISM 800 MHz band.
• It uses two separate analog channels one for forwarding communication and one for reverse communication.
• It is a first-generation cellular phone system. So, the given statement is incorrect.

Statement b:

IS - 95 is a second-generation cellular phone system based on CDMA and DSSS.

This statement is correct

Reason:

• IS – 95 is a second-generation cellular phone system.
• It is based on CDMA and DSSS. It uses two bands for duplex communication. IS 95 has two different transmission techniques: one for use in the forward direction and another in a reverse direction.
• In this, each voice channel is digitized. It uses FDMA to separate channels in the link.

Statement c:

The Third-generation cellular phone system will provide universal personnel communication.

This statement is correct

Reason:

The third generation of cellular telephony refers to a combination of technologies that provide a variety of services. Using a small portable device, a person should be able to talk to anyone else in the world with a voice quality similar to that of an existing fixed telephone network. It provides universal personal communication.

DES:

• DES stands for data encryption standard is a block cipher technique to encrypt the data.
• It encrypts the data in blocks of size 64 bits each, that is, 64 bits of plain text goes to input to DES which produces 64 bits of cipher text.
• DES uses key of size 56 bits but actual size of key is 64 bits. Before the DES process, every eighth bit of key is discarded to produce 56 bits key.
• DES is based on two fundamental attributes of cryptography: substitution and transposition.

IDEA:

• IDEA stands for international data encryption algorithm. It is a block cipher.
• It also works on 64-bit plain text blocks. In IDEA, key size is larger which is of 128 bits.
• 64- bit plain text block is divided into four portions of plain text (each of size 16 bits). There are 8 rounds and in each round six sub keys are generated. These subkeys are applied to each of portion. Finally, output transformation is done and four blocks of 16 bits comes as cipher text (64 bits).

Blow Fish:

• It is a symmetric key cryptographic algorithm. It works on 64-bit plain text and key size is variable in blow fish.
• It ranges between 32 bits to 448 bits long. First part of encryption is key expansion in which process converts the key up to 448 bits long to subkeys. Second part is data encryption in which the iteration of simple function 16 times. Each round contains a key dependent permutation and data dependent substitution.

AES:

• It is a symmetric block cipher. It is capable of using key of sizes 128, 192 and 256 bits and decrypt the data in blocks of 128 bits each.
• It encrypts the data faster than DES. Number of rounds are not fixed in AES, there are 10 rounds for 128 bit keys, 12 rounds for 192 bit keys and 14 rounds for 256 bit keys.
• Encryption process includes byte substitution, shifting of rows, adding of round keys.

Concept:

A network consists of two kind of elements:

1. Network nodes known as actual computing end system

2. connection between these along which data transmission travel.

There must be some method to switch data flows between these network nodes.

Explanation:

There are three basic type of switching.

Circuit switching:

• It occurs when a physical link is made between two network nodes for duration of session along which data can flow under the control of end systems.
• In circuit switching, a route and its associated bandwidth is reserved from source to destination, making circuit switching relatively inefficient since capacity is reserved whether or not the connection is in continuous use.

Message switching:

• It is a network switching technique does not establish a physical connection. It relies on the network to deliver a message successfully once sent.
• Message is routed entirety from the source node to the destination node, one hope at a time.
• During message routing, every intermediate switch in the network stores the whole message. If the entire network's resources are engaged or the network becomes blocked, the message-switched network stores and delays the message until ample resources become available for effective transmission of the message.
• It is low cost network.

Packet switching*:*

• Individual message is divided into packets each of which travels independently through the network.
• Packets are dispatched from source and reassembles at the point of exit for the destination.
• There is no resource allocation for packets in packet switching. With this technique, faster transmission rate is achieved.

Concept:

In challenge-response authentication, one entity authenticates to other entity providing the knowledge

of a secret. Three protocols used in challenge-response authentication are random numbers, sequences, timestamp.

Explanation:

In the challenge-response authentication mechanism, one entity challenges another entity for their answer and other entity response with the correct answer.

It means, when a user wants to login into the system, the system asks for his/her login and password. When data is found to be correct by the system, only then the user can access the system.

Concept:

Caesar cipher:

It is a substitution cipher. In this, characters of plain text are replaced by other character.

In this, each alphabet in a message is replaced by an alphabet with some places up or down according to the key size.

Explanation:

Here, we have to decrypt the message “WTAAD”. So, we need to decrease the count according to the Key size.

Here, key size is given as 15. So, for every alphabet of cipher text, replace it with alphabet which is available at 15 places down to it.

As alphabet series is from A to Z (1 to 26).

W is replaced by 23 – 15 = 8 i.e. H

T is replaced by 20 – 15 = 5 i.e. E

A is replaced by 1 – 15 = - 14 (as, negative number comes, add 26). (-14 + 26 = 12 i.e. L)

D is replaced by 4 – 15 = -11 + 26 = 15 i.e. O

SO, plain text will be “HELLO”.

Concept:

It is one of the concepts in coding for error control. Hamming distance between two words of the same size is the number of differences between the corresponding bits. It can be calculated by applying the XOR operation.

Explanation:

Minimum Hamming distance is the smallest hamming distance between all possible pairs in a set of words. There are three parameters in this: codeword size, data word size, and minimum Hamming distance. When a codeword is corrupted during transmission, the hamming distance between the sent and the received codeword is the number of bits affected by the error.

Points regarding hamming distance:

1. To guarantee the detection of up to s errors in all cases, the minimum hamming distance in a block code must be d_min = s + 1.

2. To guarantee the correction of up to t errors in all cases, the minimum hamming distance in a block code must be d_min = 2t + 1

Example:

A coding scheme has a hamming distance d_min = 4

Then code can detect up to 4 -1 = 3 errors and can correct up to 1 error.

Concept:

Transposition cipher:

In this type, plain text alphabets position is shifted according to some key.

Transposition cipher perform some permutation over the plain text alphabets.

Explanation:

Message: HELLO MY DEARZ

Break the message into blocks of size 4. “HELL OMYD EARZ”

 

Now, get cipher text according to 2413.

Cipher text will be “ELHL MDOY AZER”

Concept:

A semaphore S is an integer variable that apart from initialization is accessed only through two atomic operations: wait and signal. These are termed as wait (P) and signal (V).

Semaphore operation

Wait(S): S.value = S. value – 1;

 If S. value < 0,

then add this process to S.L and block;

End;

Signal (S): S. value = S. value + 1;

If S. value = 0, then begin

remove process from S.L;

Wakeup(P);

End;

Explanation:

counting semaphore: 10

12 P operations are performed, value will be decreased by 1 with each P operation.

x V operations are performed, value will be increased by 1 with each V operation.

Final value of semaphore = 7

So, 10 – 12 + x = 7

-2 + x = 7

x = 7 + 2 = 9

it means 9 V operations are performed on this semaphore.

Statement P: Common coupling occurs when one module controls the flow of another module by passing it information on what to do.

This statement is incorrect. When one module controls the flow of another module by passing it information on what to do, it is known as control coupling. Common coupling is when two or more modules access same global data. When several modules access same data, then there can be difficulty in controlling the data access.

Statement Q: In data coupling, the complete data structure is passed from one module to another through parameters.

This statement is correct. Data coupling is when complete data structure is passed from one module to another through parameters. In this, there is communication between modules only through data. Data coupling involves all global and local variables to be passed between different modules.

Statement R: Stamp coupling occurs when modules share a composite data structure and use only parts of it.

Code:

Given statement is correct. Stamp coupling occurs when modules share a composite data structure and use only parts of it. In this, data is passed by parameters among different modules. In this complete data structure is passed from one module to another, it depends on modules whether they use complete or part of it.

Software design pattern specify the structure of useful software at the architectural level. In terms of object-oriented programming, it means structure expressed in terms of classes and their relationship. Design patterns speeds up the development process.

In order to design a pattern for software, several things should be kept in mind:

1. Embark on a new design with an awareness of pattern

2. recognize the need for one of the established patterns

3. consult the catalog to check the availability of the pattern

4. use the catalog for information on how to use the pattern

5. use the pattern as part of design

Structural design patterns have different ways to compose objects so that they can achieve new functionality. These are adapter, bridge, composite, decorator, façade, delegation, factory method, immutable, pipe and filter, proxy.

A proxy object acts instead of some other objects. Its fields requests, passing them on as necessary. A software design pattern often used to restrict access to an object that is known as proxy. The proxy either handles requests itself or passes a request on to an available server.

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

<br>

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:

Master’s theorem:

It is used to solve the recurrence relation of form: T(n) = aT(n/b) + f(n) where n is the size of input, a is number of sub-problems and b is the size of each sub-problem. We have to find out n raised to the power log_ba, then compare it with given function.

If it is less than f(n), then f(n) is answer. If greater than f(n), then complexity will be the n raised to the power log_ba, and if it comes equal to the f(n), then append log n with it.

Explanation:

Recurrence relation: T(m) = T(3m/4) + 1

a = 1, b = 4/3, f(n) = 1

\({m^{{{\log }b}a}} = ;{m^{{{\log }{\frac{4}{3}}}1}} = {m^0} = 1 = f(n)\)

$T(m) =\theta({m^{{{\log }_b}a}}log\ m) = \theta(log\ m)$

Concept:

Hashing is used to uniformly distribute key values into the table using a hash function. In linear probing, when allocating location to the key values, if there occurs a collision, then we linearly probe for the next vacant location and allocate that to the key.

Explanation:

Hash function: h(key) = key mod 7

Keys are 44, 45, 79, 55, 91, 18, 63

Table size = 7( 0 to 6)

 

Step 1: key is 44 , h(44) = 44 mod 7 = 2,

Key 44 will move into index 2.

 

Step 2: Next 45, h(45)= 45 mod 7 = 3

45 will move to index 3.

 

Step 3: key 79, h(79) = 79 mod 7 = 2 (collision as, there is already a key value at index 2).

So, 79 will go for the next empty location, i.e. 4

 

Step 4: next key is 55, h(55) = 55 mod 7 = 6,

Key 55 will go into index 6.

 

Step 5: key 91, h(91) = 91 mod 7 = 0

 

Step 6: key 18, h(18) = 18 mod 7 = 4 (collision , move to next empty location i.e. 5)

 

Step 7: key 63, h(63) = 63 mod 7 = 0 (due to collision, it will move into index 1)

 

Therefore, the location of 18 elements is 5

Concept:

Single source shortest path problem finds the shortest path from a source node to all other nodes in a graph.

Explanation:

Dijkstra’s algorithm is used to solve the single source shortest path problem.

Key points for this:

• It is used for both directed and undirected graphs.
• All edges must have non - negative weights.
• Graph must be connected

 

Algorithm of dijkstra’s algorithm is:

1. dis[s] <- 0 // distance to source node is 0

2. for all vertices v except source vertex

3. do dist[v] -> infinity

4. s -> empty // initially there are no visited nodes, set is empty

5. while Q <- v // queue contains all nodes

6. while Q is not empty

7. do u -> mindistance (Q, dist) // select node from queue having minimum distance

8. S-> S U {node} // add that selected node to the set (list of visited nodes)

9. for all vertices that are neighbours of node

10. do if dist[v] > dist[node] + w(u, v)

11. then d[v] -> d[node] + w[u,v] // new value for shortest path is set

12. return dist

8 - queen’s problem:

• In this, 8 queens are placed on a 8 × 8 chessboard such that none of them can take same place.
• It is the backtracking approach. In backtracking approach, all the possible configurations are checked and check whether result is obtained or not.
• A queen can only be attacked if it is in the same row or column or diagonal of another queen.

 

Single source shortest path:

• It is used to find the shortest path starting from a source to the all other vertices.
• It is based on greedy approach.
• Example of single source shortest path algorithm is Dijkstra’s algorithm which initially consider all the distance to infinity and distance to source is 0.

 

Strassen’s matrix multiplication:

• It is a method used for matrix multiplication. It uses divide and conquer approach to multiply the matrices.
• Time consumption is improved by using Strassen’s method as compared to standard multiplication method.
• It is faster than standard method. Strassen’s multiplication can be performed only on square matrices.

 

Optimal binary search tree:

• It is also known as weight balanced binary tree. In optimal binary search tree, dummy key is added in the tree by first constructing a binary search tree.
• It is based on dynamic programming approach. Total cost must be as small as possible.

Concept:

Radix sort: It is a sorting technique which sort the integer values by grouping individual digits. It is not based on comparisons. When key values that are sorted are short, then it works faster. But sometimes it is not flexible as required. Because it depends on digits or letters.

Explanation:

Number of items = 9

Each item is assumed to be octal number of 5 digit.

Base of octal number system = 8

Maximum number of comparisons required to sort these 9 items:

= number of items × number of digits × base of number system

= 9 × 5 × 8

= 360

Concept:

Finite state machine cannot recognize all context free languages because of finite memory. So, there is a need of another machine that has auxiliary memory and can accept all the context free languages.

Relation between grammars and their automaton.

 

Explanation:

Consider an example: Language L = {aⁿ bⁿ: n> = 0}

• Here n is not bounded, counting is not possible with finite memory, in this case there is a need of unlimited counting ability. we use push down automata having an auxiliary memory i.e. stack to accept the context free languages or grammar.
• All the languages that are accepted by finite automata are known as regular language. Grammar that generates regular languages is regular grammar. So, a push down automata accepts both regular and context free languages.

Concept:

Memory-mapped i/o is a way to exchange the data and instructions between CPU and peripheral devices attached to it. Memory-mapped i/o is one where the processor and i/o device share the same memory location.

Explanation:

Normally user programs are prevented from handling i/o directly by i/o instructions in them. For CPU having explicit i/o instructions, such i/o protection is ensured by having the i/o instructions privileged. But in a CPU with memory-mapped i/o, there is no explicit i/o instruction, in that case, i/o protection is achieved by operating system routines. Memory-mapped i/o improves CPU performance. I/O can be performed simply by accessing bytes of memory and relying on the OS kernel to ensure that changes are propagated to the mapped i/o device.

Performance benefits:

1. A normal read or write() call involves two transfers. One between i/o and kernel, other between buffer cache and user buffer. Memory-mapped i/o eliminates the second.

2. Memory mapping lowers memory requirements. It uses less memory to store data.

Concept:

A push down automata is like a finite state machine but with one auxiliary memory such as stack so that it can recognize the strings.

Explanation:

• A push down automata if contains more than one stack i.e. two or more stack or auxiliary memory than it is known as Turing machine.
• Push down automata can only access top of its stack, it cannot access an infinite tape whereas Turing machine can be used to access an infinite tape. Turing machine can move backward or forward both.
• A Turing machine can both write and read. It halts when the string is accepted or rejected.
• A Turing machine consists of 7- tuples (set of states, input alphabet, tape alphabet, start state, final state, reject state, transition function).
• A language is known as Turing recognizable if there is a Turing machine that accepts it.
• If Turing machine halts on every input of the language, then it is known as recursive.

Concept:

Hit ratio:

When a page is found in the main memory, then it is known as hit.

Hit radio is defined as the ratio of total number of hits to the sum of total number of hit and misses.

In miss, when a page is not in main memory, it is found in secondary memory.

Formula:

Effective average access time = hit ratio × access time for main memory + miss ratio × access time for secondary memory

Explanation:

Hit ratio = 0. 40

Access time for secondary memory = 120 ns

Access time in primary memory = 15 ns

Effective average access time = 0.40 × 15 + 0.60 × 120

= 6 + 72 = 78 ns

Concept:

A Poisson process is a stochastic process that counts the number of events and time points at which these events occur in a given time interval. Formula for poisson distribution:

${\rm{P}}\left( {{\rm{x}},{\rm{\lambda }}} \right) = {\rm{}}\frac{{{{\rm{e}}^{ - {\rm{\lambda }}}}{{\rm{\lambda }}^{\rm{x}}}}}{{{\rm{x}}!}}{\rm{;for;x}} = 0,1,2, \ldots ..$

Explanation:

30 requests are sent in 1 hour.

i.e. in 60 min, 30 requests are sent

in 40 min, number of requests sent are 20.

λ = 20.

x = 0

$P\left( {0,20} \right) = ;\frac{{{e^{ - 20}}{{20}^0}}}{{0!}} = ;{e^{ - 20}}$

Probability that no requests are made in 40 minutes = e^-20

Concept:

Software availability:

It means the software is present at the time it is required to do some tasks.

Explanation:

Software availability can be calculated as :

A system crashed 20 times in the year 2017 and takes two minutes every time to restart .

Crash time = 20 × 2 = 40 minutes

As 2017 is not a leap year. So the total days are 365.

There are 1440 minutes in a day.

So, total time = 365 × 1440 = 525600 minutes

Working time of system = 525600 – 40 = 525560 minutes

So, availability of software (in %age) = $\frac{{525560}}{{525600}} \times 100 = ;99.9924\%$

Concept:

CMM (capability maturity model) is a set of structured levels that describes how well the behaviour, processes of an organization are and can produce reliable software. There are predefined process areas in maturity model.

Explanation:

Five levels are there in maturity model, these are initial, repeatable, managed, defined, and optimized.

Initial

It is starting of a new process.  There may not exist a plan . These does not provide a stable environment. Organizations have difficulty in making commitments that staff can meet with an orderly engineering process and can result in a crisis. Capability is a characteristic of individuals not the organization.

Repeatable

At this level, policies for managing a software project and procedures to implement the policies are established. Process capability is enhanced by establishing disciplines for a project. Processes may differ between projects. There is a plan and people to stick to it. Tracking of software project is stable in this level.

Defined

At this level, standard process for developing and maintaining software across the organization is documented. There is a group that is responsible for organization’s software process activities. Software process capability is standard and consistent in this level.

Managed

At this level, organization sets quantitative goals for both software product and processes. Projects achieve control over their products. Capability of software process at this level is quantifiable and predictable. Plan uses processes that can be measured quantitatively.

Optimized

Entire organization is focused on continuous process improvement. In this, team analyse defects to determine the causes. Software processes are evaluated to prevent known defects. Processes are improved quantitatively and continuously.

Concept:

Software reengineering is defines as the examination and alteration of a subject system to reconstitute it to a new form and the subsequent implementation of new form. It consists of reverse engineering and then forward engineering.

Explanation:

Reengineering a system involves not only the process or procedure side but also the data side of an application. It includes CASE (computer aided software engineering) to perform system reengineering.

Reengineering a software retains the software’s value to an organization. It also reduce maintenance costs of software. There are certain reasons to reengineer a software :

1. It allows legacy software to quickly adapt to the changing requirements.

2. Upgrade to newer technologies/platforms/paradigm (for example, object-oriented).

3. It allows change in the functionality and architecture of the software

4. Extends the capabilities of software to meet business needs.

Activities that are involved in software reengineering are:

• Inventory analysis
• Reverse engineering
• Code restructuring
• Process reengineering
• Data reengineering
• Forward engineering

Refactoring:

Refactoring is the process of changing a software system in such a way that it does not alter the external behaviour of the code yet improves the internal structure. It is a disciplined way to clean up code that minimizes the chances of introducing bugs. It improves the design of the code. It can balance the work changes. 

Some points about refactoring:

• Before start of refactoring, there must have a solid suite of tests. Test must be self- checking.
• Refactoring changes the program in small steps.
• It needs decompose and redistributing of statement method.
• It can remove duplications in the program

<br>

Refactoring methods are extract method, move methods, rename, replace temp with query, self-encapsulate field, replace type code with state. Refactoring improves the under-standability and maintenance of software.

Concept:

Max- heap: In max - heap, root node is always is greater than or equal to the other nodes of the tree.

Explanation:

A = <4, 1, 3, 2, 16, 9, 10, 14, 8, 7>.

STEP 1

Now, As 2 is greater than 1, there is need of rearrangement of nodes.

STEP 2:

Again exchange 16 with 2. Insert remaining nodes as per the property of max- heap.

STEP 3:

STEP 4:

STEP 5:

After inserting all the nodes in this way, final max - heap is:

As, root is at level 0, So, there are total 3 levels in this max - heap. Also, right child of root node is 10.

Concept:

Optimal coding technique merge the probabilities one by one starting from the lower one.

Explanation:

Characters are: A, B, C, D and E with probabilities 0.08, 0.40, 0.25, 0.15, 0.12 respectively.

Step 1: Merge 0.08 (A) and 0.12, (E)

Step 2: Merge 0.20 with 0.15(D)

Step 3: Merge 0.35 and 0.25 (C)

Step 4: Merge 0.60 with 0.40 (B), then assign 0 to all left edges and 1 to all right edges.

Code for A (0.08) = 1110 (length 4)

Code for B (0.40) = 0 (length 1)

Code for C (0.25) = 10(length 2)

Code for D (0.15) = 110 (length 3)

Code for E (0.12) = 1111 (length 4)

Average code length = [(0.08 × 4) + (0.40 × 1) + (0.25 × 2) + (0.15 × 3) + (0.12 × 4)] / 1 = 0.32 + 0.40 + 0.50 + 0.45 + 0. 48 = 2.15

Formula:

L = I (n - 1) + 1

where, L = number of leaf nodes

I = number of internal nodes

n = n - ary tree

Explanation:

L = 19

n = 2 (as given tree is strictly binary tree)

19 = I (2 - 1) + 1

I = 18

Number of internal nodes = 18

Number of leaf nodes = 19

Total number of nodes = 18 + 19 = 37

Tips and Trick:

Number of internal node in a binary tree = number leaves - 1 = 19 - 1

Total nodes = number of leaf nodes + internal node = 19 + 18 = 37

Important Point:

Root node is also a internal node.

Formula:

L = I (n - 1) + 1

L =number of leaf nodes

I = number of internal nodes

n = n - ary tree

Calculation:

I = 8

n = 5

L = 8(5 - 1) + 1

L = 32 + 1 = 33

Number of leaf nodes = 33

Number of internal nodes = 8

Total number of nodes = 33 + 8 = 41

Concept:

Boolean function: In Boolean function, each argument is represented in form of only 0 or 1.

Explanation:

Given, n Boolean variables.

If there are n Boolean variables, then number of Boolean functions possible are 2ⁿ.

Suppose we have 4 Boolean variables, so number of Boolean functions are = 2⁴ = 16

Here, we have to find the order of algorithm which determines whether Boolean function produces an output 1.

For this, we need to check each Boolean function one by one in worst case.

As, there are 2ⁿ Boolean functions, we have to check all of these in worst case.

As, it is in exponential form. So, order of the algorithm is also in exponential form.

Diagram representation of Boolean function with n Boolean variables:

 

As, each Boolean variable is mapped with either 0 or 1, that’s why Boolean function are 2ⁿ.

Concept:

Finite state automata is a machine that can be used to solve computer programs and other sequential logics and have finite number of states at a given time. There are 6 tuples in a finite state machine.

Explanation:

Two finite state machines are said to be equivalent if they recognize the same set of tokens.

Consider two automata M₁ and M₂, these are called equivalent for an input sequence if they produce the same output result.

Example:

Regular expression: baa*b

NFA: M₁

Number of states in NFA: 4

DFA: M₂

Number of states in DFA: 5

Above two finite automata are having different number of states and edges, but they are equivalent.

They are said to be equivalent only when they accept same regular language (same set of tokens) whether they have different number of states or edges.

The correct answer is Operations on the database are speeded up as the authorization procedure is carried out at the operating system level.

Concept:

Operating system authentication is a method for identifying a connection with credentials supplied by the operating system of the connecting computer.

Explanation:

OS authenticated logins are the default logins for SQL databases. This is the only type of login allowed when SQL server is created. Database server uses a digital certificate along with user-name and password to authenticate a user. For this reason, using operating system authorization can be more secure than using database accounts.

Database systems that store each relation in a separate operating system file may use the

operating system’s authorization scheme, instead of defining a special scheme themselves. Authentication may be performed by the database itself in some cases or setup may be changed to allow either the operating system. Some points while using operating system authentication:

• When database system stores each relation in separate operating system file, then it becomes difficult to update, delete and insert authorizations.
• Control on grant options becomes difficult
• It can-not store more than one relation in a file
• Operations on database performed more fast using authorization process.

Concept:

A foreign key in a table refers to the primary key of another table. It contains subset of entries of primary key of other table. It specifies the referential integrity constraint.

Explanation:

a is the foreign key of R₁ that refers to the primary key of R₂

(a) Insert into R₁

It will cause violation. As a is the foreign key referring to the primary key of R₂. If we insert values in R₁, then that value must also be present in the primary key of R₂ and which is not necessary as while inserting in R₁ we are not aware of R₂.

(b) Insert into R₂

It will not cause violation. Because inserting element in R₂ will not effect R₁. Values present in R₂’s primary key may or may not present in foreign key of R₁.

(c) Delete from R₁

It has no effect on the relation. It will not cause violation. Values that are deleted from R₁ need not be deleted from R₂. As R₁ contains the foreign key.

(d) Delete from R₂

It will cause violation. If we delete tuples from R₂ relation, then if that tuple is present in R_1­ which is referring to the primary key of R₂ must also be deleted.

Concept:

Hashing is used to uniformly distribute key values into the table using a hash function. In linear probing, when allocating location to the key values, if there occurs a collision, then we linearly probe for the next vacant location and allocate that to the key.

Explanation:

Given hash function:

h(x) = (7x + 3) mod 4

Hash table size is seven starts from zero.

0              1             2               3             4             5              6

 

Step 1: Insert 3

h(3) = (21 + 3) mod 4 = 24 mod 4 = 0

location of 3 is at index 0

0              1             2               3             4             5              6

 

Step 2: insert 1

h(1) = 10 mod 4 = 2

it will go to index 2

0              1             2               3             4             5              6

 

Step 3 : Insert 8

h(8) = 59 mod 4 = 3

it will go to index 3

0              1             2               3             4             5              6

 

Step 4 : Insert 10

h(10) = 73 mod 4 = 1

It will go to index 1.

0              1             2               3             4             5              6

In artificial intelligence, environment is that surrounds an agent. Environment is where agent lives, do its work or we can say that surrounding in which agent is present.

Environment is clearly distinguishable from the agent, it is not the part of the agent. An environment can have various attributes from the point of view of the agent. These are :

1. Observable and partially observable: An agent is considered to be an agent only if it has the ability to observe its environment. In some cases, environment may be partially observable. Uncertain environment is not fully observable.

2. Deterministic and stochastic: A deterministic environment is one where any future state of the environment can be completely determines from preceding state and actions of agent. It is stochastic if there is some element of uncertainty.

3. Episodic and sequential: If each of agent’s tasks do not rely on past performance than episodic otherwise it is sequential.

4. Discrete and continuous: A discrete environment has finite number of possible states whereas number of states in continuous environment is infinite.

Concept:

Agent represent the most important new paradigm for software development. An autonomous agent is a system situated within and a part of an environment that senses the environment and acts on it.

Explanation:

An agent is situated in environment and makes its own decisions. it perceives the environment through sensors and acts on the environment through actuators.

Simple reflex agents selects actions based on the agents current perception or the world and not based on past perceptions. They work when environment if fully observable. It is based on condition action rule which means it maps a state with an action.

Diagram:

Concept:

Heuristic search refers to a search strategy that attempts to optimize a problem by iteratively improving the solution based on a given heuristic function or cost measure. Several commonly used heuristic search methods include hill climbing, best first search, A* algorithm, simulated annealing.

Explanation:

Real valued hash function are used as a means for constraining search in combinatorial large problem spaces. A strategy is considered to be a function which for a given state in some problem domain returns sequences of states over the problem domain.

A heuristic function h(n) finds the cost of cheapest path from a node to the goal node.

• The function h(n) is an underestimate if h(n) is less than or equal to the actual cost of a lowest cost path from a node to the goal node
• The heuristic value of a path is the heuristic value of the node at the end of the path.
• Two ways are there to use the heuristic function: one is for heuristic depth first search and another for best first search
• If heuristic function h(n) = max{h₁(n),....,h_m(n)}, then a collection of admissible heuristics h₁.......h_m is available for a problem and none of them dominates any of the others.
• Composite heuristic function dominates all of its component functions and is consistent if none of the components overestimates.

A* search algorithm finds the shortest path from a node to the goal node. It combines the value of heuristic function h(n) and cost to reach the goal node.

Evaluation is done as : f(n) = g(n) + h(n)

It first goes to the node having the minimum f(n) value. It can be seen as optimal search algorithm.

Some properties of A* search algorithm are mentioned here:

1. A* generates an optimal solution if h(n) is admissible heuristic and search space is a tree. A function is admissible if it never overestimates the cost to reach the goal node.

2. A* generates an optimal solution if h(n) is a consistent heuristic and search space is a graph. H(n) is consistent if for every node n and for every successor node n’ :

h(n) <= c(n, n’) + h(n’)

3. A* expands no nodes with f(n) /C*. Pruning is selectively removing the branches of a tree that are unwanted.

(a) False ? True

It can be rewritten as : False V True

Truth table for OR:

 

So, false ? true results in true.

(b) If α ? (β ∧ γ) then α ? β and α ? γ.

It can be rewritten as : α V (β ∧ γ) , (α V β ) ∧ (α V γ)

Truth table for this:

 

Here if α V (β ∧ γ) is true then (α V β ) ∧ (α V γ) is true.

And if α V (β ∧ γ) is false then (α V β ) ∧ (α V γ) is false.

So, given statement is true.

Concept:

Many to one relationship:  When more than one instance of an entity is associated with a single instance of another entity is called many to one relationship.

Explanation:

There exists many to one relationship between two entities r₁ and r­₂.

PK(r₁)- primary key of relation r₁

PK(r₂) – primary key of relation r₂

Consider attributes of relation r₁ are (employee id, employee name)

Consider attributes of relation r₂ are (address, department)

From here, employee id can clearly tell us about the employee, it can uniquely identify a person.  But the department cannot uniquely identify the employee.

So, option 1:  Pk(r₁) → Pk(r₂)

i.e. primary key of r₁ can identify each attribute of r₂ because it is given that one element of r₂ is referring to more than one element of r_1.

Concept:

2NF: There should not be any partial dependency in the relation.

3NF: There should not be any transitive dependency and right side of functional dependency is a prime attribute

BCNF: Left side of functional dependency is a key

If a functional dependency is in BCNF, then it will also be in lower normal forms (1 NF, 2NF, 3 NF). Also, if any one functional dependency is in the weaker normal form, then relation will be in weaker normal form

Explanation:

Functional dependencies are:

a → c

b → d

Candidate key for the relation R is  {ab}

Because (ab)+ = {a, b, c, d}

1. a → c

This is not in BCNF, because left side is not the candidate key. Also, not in 3NF because right side is not the prime attribute. It is in not in 2NF, because there exists partial dependency in this functional dependency, as a non-prime attribute is dependent on prime attribute. It is in 1NF.

2. b → d

Similar case as that of 1^st functional dependency. It is in 1NF

So, given relation R (a, b, c, d) is in 1NF.

Command used to make all files and sub- directories in the directory “progs” executable by all users

is: chmod – R a + x progs

chmod – in unix, it is the command and system call which is used to change the access permissions of file system objects such as files and directories.

-R: it is for recursive directory traversal option. Read all the files under each directory recursively.

+x – it is symbolic representation of executable mode that chmod command used to set the executable permission of a file. In this “+” sets the permission and “-” reset the permissions.

File permission are represented in rwx form in UNIX. There are three sections in which permission are assigned which are user, group and others. User is the owner of the file. A user group can contain multiple users.  Three permissions are read, write and execute.

(a) External Fragmentation exists when there is enough total memory space to satisfy a

request but the available space is contiguous.

This statement is incorrect. As process are loaded and removed from memory, the free memory space is  broken into little pieces. External fragmentation exists when enough total memory space exists to satisfy a request but it is not contiguous; storage is fragmented into large number of small holes.  External fragmentation is also known as checker boarding. Suppose we have memory blocks available of size 400KB each. But if request come for 600Kb then it cannot be allocated.

(b) Memory Fragmentation can be internal as well as external.

This statement is correct. There is an important issue related to the contiguous multiple partition allocation scheme is to deal with memory fragmentation. There are two types of fragmentation: internal and external fragmentation. Internal fragmentation exists in the case of memory having multiple fixed partitions when the memory is allocated to a process is not fully used by the process.

c) One solution to external Fragmentation is compaction.

Given statement is correct. To get rid of external fragmentation problem, it is desirable to relocated some or all portions of the memory in order to place all the free holes together at one end of memory to make one large hole. This technique of reforming the storage is known as compaction.

The essential content in each entry of a page table is the page frame number.

Explanation:

In paging, physical memory is divided into fixed-size blocks called page frames and logical memory is divided into fixed-size blocks called pages which are of the same size as that of frames. When a process is to be executed, its pages can be loaded into any unallocated frames from the disk.

In paging, mapping of logical addresses to physical addresses is performed at the page level.

• When CPU generates a logical address, it is divided into two parts: page number and offset
• Page size is always in the power of 2.
• Address translation is performed using the page table (mapping table).
• It stores the frame number allocated to each page and the page number is used as an index to the page table.

 

When the CPU generates a logical address, that address is sent to the MMU (memory management unit). MMU uses the page number to find the corresponding page frame number in the page table. Page frame number if attached to high order end of page offset to form physical address that is sent to the memory.

The mechanism is shown here:

Concept:

LRU (Least recently used) page replacement algorithm is based on the assumption that the page that has been used in the last few instructions will be referenced in the next few instructions. It replaces the page that has not been referenced for the longest time.

Explanation:

Reference string: 1, 2, 3, 2, 4, 2, 5, 2, 3, 4

Number of frames = 3

 

Here, total page faults = 3 + 1 + 1 + 1 + 1 = 7

Concept:

Transferring the control of CPU from one process to another demands saving the context of currently running process and loading the context of another ready process. This mechanism of saving and restoring the context is known as context switching.

Explanation:

Round robin scheduling:

It is pre-emptive scheduling algorithm which considers all the processes as equally important and treats them in favourable manner. Each process in ready queue gets a fixed amount of CPU time known as time quantum. If the process does not execute completely till end of time quantum, it is pre-empted and CPU is allocated to the next process in the ready queue. Context switching is needed in round robin scheduling.

Preemptive SJF:

It is also known as shortest remaining time first scheduling. Scheduler always chooses the process for execution that has the shortest remaining processing time. While a process is being executed, CPU can be taken back from it and can be assigned to some newly arrived process is burst of new process is shorter than its remaining burst time.

Non – preemptive SJF:

It is also known as shortest process next. In this, at any point of time among all the ready processes, the one having the shortest CPU burst time is scheduled first. There is no context switching in this algorithm.

Preemptive priority:

If the newly arrived process has the higher priority than the currently running process, the pre emptive priority scheduling algorithm pre-empts the currently running process and allocated CPU to the new process. It involves context switching.

Concept:

A data model is a collection of concepts that can be used to describe the structure of a database and provides the necessary means to achieve the abstraction.  Types of data model are : hierarchical data model, network data model and relational model.

Explanation:

Hierarchical data model: In this data model, data is organized in the form of tree in which nodes represent the records and branches of tree represent the fields. Parent node or root of three have connection with its child nodes.

During search operation in this data model, search takes place from root and then moves to the children to reach the specific record. That means, searching always starts from root. If we use hashing function for the search operation than hashing function will locate the root of the model.

Diagram for hierarchical database model:

Concept:

ER model describes data as entities, relationships, and attributes. It is a high-level conceptual data model. This model is used to define the data elements and relationships for a specified system.

Entity:

The entity is a thing in the real world with an independent existence. An entity may be an object with physical existence. For example particular person, car or it may be an object with a conceptual existence For example company, job, etc.

Attributes:

Each entity has attributes – the particular properties that describe it.

Relationship:

It is used to describe the relation between two entities.

Explanation:

E-R Diagram is design level task and Relational model is implementation.

The relational model is implemented from E-R Diagram and in this, it gets rid of the multivalued attributes.

Relations produced from the E - R Model will always be in 1NF, that is, Simple atomic values with non-multivalued attributes.

NOTES:

The relation is also referred to as a table.

Concept:

Join operation is used to combine related tuples from two relations into single tuples. Join operation can be stated in terms of Cartesian product followed by SELECT operation.

Join condition form: <condition>AND<condition>AND……AND<CONDITION>

Explanation:

There are various variations of join operations such as equi-join, natural join, theta join, inner join, outer join.

• Natural join is performed by equating all attributes pairs that have the same name in the two relations.
• Join operation with equality condition is known as equi-join.
• Join operation which is used to combine data from multiple relations so that related information can be presented in a single table is known as inner join. Inner join is a type of match and merge operations defined as combination of Cartesian product and selection.
• Outer join can be used when we want to keep all the tuples in the result of join regardless of whether or not they have matching tuples in other relation.

no two books have the same price

Assume table BOOK B :

 

Book T:

               

One record is compared with all the records of another table. I.e. if we consider A (10) in Book T, then it is compared against all the records of book B. it is not greater than any record.

Now compare B(20) of book T with all records of book B. So, it is greater than 1 record.

Compare C(30) of book T with all records of book B. So, it is greater than 2 record.

Compare D(40) of book T with all records of book B. So, it is greater than 3 record.

Compare E(50) of book T with all records of book B. So, it is greater than 4 record.

Compare F(60) of book T with all records of book B. So, it is greater than 5 record.

Compare G(70) of book T with all records of book B. So, it is greater than 6 record.

Compare H(80) of book T with all records of book B. So, it is greater than 7 record.

 

So, it will result in title of seven most expensive books.

Concept:

Draw the precedence graph for the above two schedules: 

1. If precedence graph contains cycle, then that schedule will not be conflict serializable

2. If graph does not contain any cycle, then schedule will be conflict serializable.

Explanation:

S₁: r₁(X); r₁(Y); r₂(X) ; r₂(Y) ; w₂(Y) ; w₁(X)

There are two transaction involved.

 

Precedence graph:

S2: r₁(X) ; r₂(X) ; r₂(Y) ; w₂(Y) ; r₁(Y) ; w₁(X)

 

Precedence graph :

From here, it is clear that S₁ is not conflict serializable and S₂ is conflict serializable.

Given statement is “Agra and Gwalior are both in India”.

Predicate In(x, y) means x is in y.

So,

1. In(Agra, India) – It represents Agra is in India.

2. In(Gwalior, India) – It represents Gwalior is in India.

Given predicate logic means

In(Agra, India) ∨  In(Gwalior, India) : It represents Agra is in India or Gwalior is in India.

It is not representing that both Agra and Gwalior are in India.

So, we can say that It is syntactically valid but does not express the meaning of the English sentence.

(a) The planning graph data structure can be used to give a better heuristic for a planning

problem.

This statement is correct.

Reason:

• The task of coming up with a sequence of actions that will achieve a goal is called planning.
• A special data structure known as planning graph can be used to give better heuristic estimates. A planning graph consists of a sequence of levels that correspond to time steps in the plan where 0 is the initial state.
• A planning graph once constructed is a rich source of information about the problem. A literal that does not appear in the final level of the graph cannot be achieved by any plan.
• We can estimate the cost of achieving the goal literal as the level at which it first appears in the planning graph. Planning graph allow several actions at each level whereas heuristic counts just the level and not the number of actions.

<br>

(b) Dropping negative effects from every action schema in a planning problem results in a

relaxed problem.

This statement is correct.

Reason:

• In planning, logical based description of the environment is included. Two possible developments in layered graph are: positive effects which generate facts that are positive and negative effects which are used to mark conflicts.
• Negative effects should be removed such that we only left with positive preconditions. Negative effects put restrictions on the actions due to which time increases. Dropping of negative effects from every action schema increases the number of actions and results in a relaxed problem.

Concept:

Predicate logic deals with predicates which are propositions, consists of variables. Two quantifies in predicate logic are there exist (∃) and for all (∀).

Explanation:

Given statement is:

∃x AsHighAs (x, Everest).

It is comparing one element with other element. It means, there exists a element x which is as high as Everest. So, for comparison we have x and Everest should be different.

(a) AsHighAs (Everest, Everest)

After applying existential quantifies, this statement becomes.

∃Everest AsHighAs (Everest, Everest) : it means there exist an Everest which is as high as Everest. There is no meaning of this sentence. As we are comparing same elements. It does not sounds good.

(b) AsHighAs (Kilimanjaro, Everest)

After applying existential quantifies, this statement becomes.

∃Killimanjaro  AsHighAs (Killimanjaro, Everest) : it means there exist a Killimanjaro which is as high as Everest. It is comparing Killimanjaro with Everest which does not have any problem. It sounds good.

Concept:

A joint probability distribution shows a probability distribution for two or more random variables. It looks for a relationship between two variables say x and y. It gives the probability that each x and y falls in a particular range of set of values specified for that variable.

Explanation:

Here, given:

Total cards = 52

We have to deal with 5 cards.

In this question, atomic events possible can be find in the number of ways they can be combined.

Which is represented as C (n, r) = (n!)/ (n-r)! r!

Here n = 52

r = 5

C (52, 5) = (52)! / (5)! (52 - 5)!

C(52, 5) = $\frac{{52 \times 51 \times 50 \times 49 \times 48 \times 47!}}{{5 \times 4 \times 3 \times 2 \times 1 \times 47!}}$ 

C(52, 5) = 2, 598, 960

Concept:

In graph theory, a flow network is defined as a directed graph involving a source and sink and other nodes ,all connected with edges. Each edge has an individual capacity which is the maximum limit of flow that edge could allow.

Explanation:

Some conditions about flow:

1. Incoming flow and outgoing flow should be equal.

2. Flow should be between 0 and capacity of the edge.

3. Net flow follows skews symmetry i.e. F(u, v) = - F(v, u) where u and v are the vertices.

Ford Fulkerson algorithm:

1. Initially flow in all edges is 0

2. while there exists an augmenting path between source and sink, augment flow between source and sink along that path

3. Update the remaining graph

4. return

Augmenting path is a simple path from source to sink which do not include any cycle and pass through positive weighted edges. If, no augmenting path, then flow is maximum between source and sink.

In ford Fulkerson algorithm, if E is the number of edges and f is the maximum flow with capacities in integer form, then time complexity for such algorithm is O (E * f).