ISRO CS 2011
Differential Manchester encoding
Non return to zero
→ The FC(Fiber Channel) -0 standard defines what encoding scheme is to be used (8b/10b or 64b/66b) in a Fibre Channel system – higher speed variants typically use 64b/66b to optimize bandwidth efficiency.Thus, 8b/10b encoding is used for 4GFC and 8GFC variants;
→ The Fibre Channel 8b/10b coding scheme is also used in other telecommunications systems. Data is expanded using an algorithm that creates one of two possible 10-bit output values for each input 8-bit value.
→ Kohonen map or network is self-organizing map
→ Hopfield nets serve as content-addressable ("associative") memory systems with binary threshold nodes. They are guaranteed to converge to a local minimum, but will sometimes converge to a false pattern (wrong local minimum) rather than the stored pattern (expected local minimum). Hopfield networks also provide a model for understanding human memory.
→ Backpropagation is a method used in artificial neural networks to calculate a gradient that is needed in the calculation of the weights to be used in the network
Replacing run time computation by compile time computation
Removing loop invariant computation
Removing common subexpressions
replacing a costly operation by a relatively cheaper one
Example: Exponentiation is replaced by multiplication and multiplication is in return replaced by addition.(x * 2 becomes x + x)
If round-robin scheduling with 5 ms is used what is the average waiting time of the processes in the queue?
→Given scheduling algorithm is round robin with time quantum value is 5ms.
→In the given example, every process will execute for 5ms. process P1 will execute for two times , P2 for one time, P3 for four times , P4 for two times and P5 for three times.
→Waiting time of process P1 = 0+(25-20)=5
→Waiting time of process P2 = 5
→Waiting time of process P3 = 10 + (30-15 )+ (43-35) + (53-48)=10 + 15 + 8 + 5 = 38
→Waiting time of process P4 = 15+(35-20)=15 + 15 = 30
→Waiting time of process P5 =20+(38-25)+48-43= 20 + 13 + 5 = 38
→Average waiting time = 20 + 5 + 38 + 30 + 38 =131/5 = 26.2
In register addressing mode, a register contains the operand. Depending upon the instruction, the register may be the first operand, the second operand or both.
In Immediate Addressing,an immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
It is a depth sort algorithm
No limitation on total number of objects
Comparisons of objects is done
z-buffer is initialized to background colour at start of algorithm
To begin with, a buffer containing the closest depth at each pixel location is created parallel to the image buffer. Each location in this depth buffer is initialized to negative infinity.
Since the algorithm processes objects one at a time, the total number of polygons in a picture can be arbitrarily large.
Floating Point number in Binary = 1100 0001 1101 0000 0000 0000 0000 0000
In 32-bit, single precision floating point IEEE representation, first MSB represents sign of mantissa: 1 is used to represent a negative mantissa and 0 for a positive value of mantissa, next 8 bits are for exponent value and then 23 bits represents mantissa.
Value of exponent = 131-127 = 4
Mantissa = -1.1010000 0000 0000 0000 0000
Floating point number = -1.1010000 0000 0000 0000 0000
Converting the above one into decimal no -(1*20+1*2-1*0*2-2+1*2-2+0* 2-3 +.....)
Decimal value =sign*Exponent*mantissa=1*4*-13/8
What is the efficiency of this precedence graph on S if each of the tasks T1, T2, T3,….T8 takes the same time and the system S has five processors?
I. T1 ,T2
II. T3 and T6
III. T4 and T7
IV. T5 and T8
(T3,T6),(T4,T7) and (T5,T8) will execute parallely.
So total number of processes that can be executed in 4 units time using 5 available processors = 5*4 = 20
Maximum number of tasks are 8
Efficiency = 8/20 * 100 = 40%
So, for 4 distinct nodes, we can have (8C4)/5 = 14 distinct BSTs
→ Reverse Address Resolution Protocol(RARP) is the viceversa case of ARP as it is a protocol by which a physical machine in a local area network can request to learn its IP address from a gateway server.
It is applied to a small part of the code
It can be used to optimize intermediate code
To get the best out of this, it has to be applied repeatedly
It can be applied to the portion of the code that is not contiguous
It basically works on the theory of replacement in which a part of code is replaced by shorter and faster code without change in output.
The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps, and thus is useful where swapping is very expensive.
T1 − T2 − T3
T3 − T1 − T2
T2 − T1 − T3
T1 − T3 − T2
1. A data flow diagram (DFD) illustrates how data is processed by a system in terms of inputs and outputs. As its name indicates its focus is on the flow of information, where data comes from, where it goes and how it gets stored.
2. Context Diagram. A context diagram is a top level (also known as "Level 0") data flow diagram. It only contains one process node ("Process 0") that generalizes the function of the entire system in relationship to external entities.
None of the above
According to question, there is no information regarding children nodes of node “A”. So the degree of A is 0.
Relational Database Management System
Object Oriented Database Management System
An object can be viewed as the set of all its versions.
Object versions can be treated as objects in their own right. Some object databases also provide systematic support for triggers and constraints which are the basis of active databases.
800 x 600
1024 x 768
1280 x 1024
1920 x 1440
Given file size is 8M bytes= 8*1024**1024*8=83,88,608
From the options,
From the above , option A and B are less than file size.
From that two , maximum one is option B.
Read (when it is low)
Read (when it is high)
Write (when it is low)
Read and Write (when it is high)
1 M bytes
2 M bytes
4 M bytes
4 K bytes
→Size of logical address = 32 bits
→Page size = 4K =22210=212 Bytes
→Number of pages = logical address space/ size of each page = 232/ 212= 220
→Page table size = number of pages * size of a page table entry
= 220 * 22
Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise.
Recursive languages are also called decidable.
The number of new processes will arrive per minute = 6
Each process require to complete its task = 7 secs
CPU utilization time within a minute = 6*7 = 42 secs
The percentage of CPU utilization = time which is spent for utilization / total time * 100
= (42/60) * 100
→ There are some tags in HTML which don't have a closing tag.
→ They end within the same tag.
→ is a container tag, it has it's closing tag as .
→Other examples are , ,
→These are called container tags because they contain something, within the two tags.
The above figure represents which one of the following UML diagram for a single send session of an online chat system?
2. A sequence diagram shows object interactions arranged in time sequence. It depicts the objects and classes involved in the scenario and the sequence of messages exchanged between the objects needed to carry out the functionality of the scenario.
3. A class diagram is a type of static structure diagram that describes the structure of a system by showing the system's classes, their attributes, operations (or methods), and the relationships among objects.
First Normal Form
Second Normal Form
Third Normal Form
Third Normal Form
Second normal form (2NF) is a normal form used in database normalization.
To qualify for second normal form a relation must:
→be in first normal form (1NF)
→not have any non-prime attribute that is dependent on any proper subset of any candidate key of the relation.
A non-prime attribute of a relation is an attribute that is not a part of any candidate key of the relation.
(X+Y)(X+Z) = X + XZ + XY + YZ
= X(1 + Z + Y) + YZ // as (1 + A = A)
= X.1 + YZ
= X + YZ
Set to 1
Set to 0
No change in state
Given data is video terminal unit has 80 lines and each line consists of 8 bits
Total number of bits transmitted = 80 * 8 = 640 bits
Horizontal sweep time = 100 us=100x 10-6 seconds
Bit rate = (640 * 106) / 100 =6400000=6.4 Mbps
Boundary condition of the software
Control structure of the software
Functional requirement of the software
Independent paths of the software
Page fault rate is constant even on increasing the number of allocated frames
Page fault rate may increase on increasing the number of allocated frames
Page fault rate may increase on decreasing the number of allocated frames
Page fault rate may decrease on increasing the number of allocated frames
This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm.
So, BTAB = B'.A.B
Taking transpose of B’.A.B
(B'.A.B)' = B'.A'.(B')' = B'.A.B // (B')' = B
So, it is a symmetric matrix.
But here the argument is negative value.
Floor of -7.4 will return the lower limit, i.e. -8.
Each port supports 8 Gbps then all 24 ports have capacity of 24*8 Gbps bandwidth
The aggregate bandwidth is 192 Gbps
INTR & INTA
RD & WR
S0 & S1
HOLD & HLDA
These two signals are used for hand shaked control during DMA operation (Direct Memory Access)
These two signals are used where there is more than one CPU like devices sharing the same system bus
while (x ≤ 500)
What is the value of i at the end of the pseudocode?
After completion of second iteration x and i values are : x = 4 and i = 3
After completion of third iteration x and i values are : x = 16 and i = 4
After completion of fourth iteration x and i values are : x =256 and i = 5
After completion of fifth iteration x and i values are : x = 65536 and i = 6(Condition is false)
Then the value of “i” is 5
20/5 = 4 and 32/8 = 4
Maximum speed up possible is 4
Associative memory makes a parallel search with the stored patterns as data files.
S → AB
A → a
B → b
B → C
int x,y=10; z=12;
x=y++ + z++;
x=22, y=10, z=12
x=24, y=10, z=12
x=24, y=11, z=13
x=22, y=11, z=13
Post increment operator first perform the action and then it increment the value.
First perform addition of ‘y’ and ‘z’ and later increment ‘y’ and ‘z’ values
So, the value of x = 10 + 12 = 22, y = 11 and z = 13.
Convert the above two addresses into binary format and perform the bitwise AND operation
RAID levels and their corresponding functionality as shown below
RAID 0: Stripping
RAID 1: Mirroring
RAID 2: Hamming code for error detection
RAID 3: Byte-level striping with a dedicated parity disk
RAID 4: Block-level striping with block-level striping with two parity blocks parity
RAID 5: Block-level striping with distributed parity
RAID 6: Block-level striping with double distributed parity.
X. Y + X’ Y’
X. Y + X. Y
X + Y
A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list , whether element is found or not
Searching time of TLB(T) is 20ns
Access time(M) is 100ns and four level paging scheme is used.
Effective Memory access Time, EAT = H* T+ (1 - H)[ T+ 4*M] + M]
EAT = (0.98 *20) + 0.02(20 + 400) + 100
= 19.6 + 8.4 + 100 = 128 ns
The amount of time data transferred is = 10 hours = 36000 secs
Total Data transmitted = 2.048 * 106 * 36000 = 2.048 * 36 * 109 bits
The number of Error bits received = 512
Error rate = total number of error bits/ total data transferred per second
= 512 / 73.728 * 109
= 6.944 * 10-9
Warnier Diagram enables the analyst to represent
This method aids the design of program structures by identifying the output and processing results and then working backwards to determine the steps and combinations of input needed to produce them.
The simple graphic method used in Warnier/Orr diagrams makes the levels in the system evident and the movement of the data between them vivid.
Routing the packets
obtaining IP address
domain name resolving
A common use of LDAP is to provide a central place to store usernames and passwords. This allows many different applications and services to connect to the LDAP server to validate users
Reflexive, Augmentation and Decomposition
Transitive, Augmentation and Reflexive
Augmentation, Transitive, Reflexive and Decomposition
Reflexive, Transitive and Decomposition
The axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies when applied to that set
Axiom of Reflexivity:
→If X is a set of attributes and Y is a subset of X, then X holds Y. Hereby, X holds Y ( X -> Y) means that X functionally determines Y.
Axiom of Augmentation:
→If X holds Y and Z is a set of attributes, then XZ holds YZ. It means that attribute in dependencies does not change the basic dependencies.
Axiom of Transitivity:
The axiom of transitivity says if X holds Y, and Y holds Z, then X must also hold Z.
Number of chips needed are = total memory capacity / RAM memory
= 2048 bytes / 128 x 8 =2048x8/128x8
For example, process A with its address space and stack is currently being executed by the CPU and there is a system call to jump to a higher priority process B;
the CPU needs to remember the current state of the process A so that it can suspend its operation, begin executing the new process B and when done, return to its previously executing process A
Only one context switch process happened
O(n log n)
T(n + 1) = 2n + T(n)
By substitution method:
The above T(n) value is always less than n2, Then the function is O(n2)
date and time
2. Nice is used to invoke a utility or shell script with a particular priority, thus giving the process more or less CPU time than other processes. A niceness of −20 is the highest priority and 19 is the lowest priority. The default niceness for processes is inherited from its parent process and is usually 0.
3. The date command is used to print out, or change the value of, the system's time and date information.
4. The time command is used to determine how long a given command takes to run. It is useful for testing the performance of your scripts and commands.
cycle stealing technique
cycle bypass technique
DMA transfers can transfer either one byte at a time or all at once in burst mode. If they transfer a byte at a time, this can allow the CPU to access memory on alternating bus cycles – this is called cycle stealing since the CPU and either the DMA controller or the bus master contend for memory access.
In burst mode DMA, the CPU can be put on hold while the DMA transfer occurs and a full block of possibly hundreds or thousands of bytes can be moved.
nn . n!
(P4, P1, P3, P2)
(P4, P2, P1, P3)
(P4, P2, P3, P1)
(P3, P1, P2, P4)
The combinations are (HHH,HHT,HTH,HTT,TTT,TTH,THT,THH)
The number of combinations with two heads and one tail is HHT,HTH,THH
The the probability is the number of combinations of the event/ total combinations of the event = 3/8
O(n log n)
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
The average depth of a binary search tree is log(n)
What is the output of the following C code?
for(index=1; index<=5; index++)
In the given code, there are no statements after continue statement , So it won’t effect on the output.
The loop will executes for five iterations,For each iteration it will print corresponding value i.e; 12345.
number of electrons increases while that of holes decreases
number of holes increases while that of electrons decreases
number of electrons and holes remain the same
number of electron and holes increases equally
In n-type semiconductors the number of electrons is more than the holes, so electrons are measured as majority charge carriers and holes are referred to as minority charge carriers.
If the temperature or heat energy applied on the semiconductor is further increased then even more number of valence electrons gains enough energy to break the bonding with the parent atom and they jump into the conduction band.
If more number of electrons leaves the valence band and jumps into the conduction band then more number of holes (vacancies) are created in the valence band at the electrons position
It is calculated through a control flow graph which is developed on the basis of source code which measures the number of linearly-independent paths through a program module
The Cyclomatic Complexity of a graph = E − N + 2*P, where
E = represents a number of edges in the control flow graph.
N = represents a number of nodes in the control flow graph.
P = represents a number of nodes that have exit points in the control flow graph.
From the given graph has: E = 7, N = 5 and P = 1
Cyclomatic Complexity = 7 – 5 + 2(1) = 4
Divide and Conquer
Conceptually, a merge sort works as follows:
1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
The arithmetic mean of attendance of Class A is 40%
Arithmetic mean of 49 students attendance of Class A is 49x40
The number of class B students are 53
The arithmetic mean of attendance of Class A is 35%
Arithmetic mean of 53 students attendance of Class A is 53x35
The percentage of arithmetic mean of attendance of class A and B is
= (40x49 + 35x53 )/ (49 + 53)=3815/102
Which of the following sentences can be generated by
S -> aS | bA
A -> d | cA
S -> aS | bA
A -> d | cA
From the given productions, it is not possible to derive the sentence bccdd(two consecutive d’s).So option A is not correct.
In the string “abbcca”, there are two consecutive c’s followed by the letter ‘a’, This can’t be derived from the given productions,
From the given productions, it is also not possible to derive string which consists of the letter ‘c’ followed by ‘a’ , So the option (c ) also not correct
From given productions, we can generate the string “abcd”
→ In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
→ Given HexaDecimal numbers are 0xAA and 0x55.
Decimal equivalent of 0xAA is 170
Binary form of 0xAA is 1010 1010
Decimal equivalent of 0x55 is 85
Binary form of 0xAA is 0101 0101
The two numbers binary length length is 8.
→ If you observe all the bits of above two binary numbers, both numbers have different bits in all positions.
→ So according to definition , the number of positions at which the corresponding symbols are different which is 8.
576000 Kilobytes / sec
9600 Kilobytes / sec
4800 Kilobytes / sec
19200 Kilobytes / sec
Disk drive spins=7200 RPM,
Sector size=512 bytes
Disk drive holds= 160 sectors/track
Step-1: First find the number of rotations for 1 second. They given RPM for minute.
1 sec= 7200 / 60 = 120 rotations
Step-2: Disk Transfer rate =120*160*512
= 98,30,400 Bytes per second
Step-3: Equivalent in kilobytes = 9830400 / 1024
= 9600 KB
Note: The disk spins 120 times per second, and each spin transfers a track of 80 KB. Thus, the sustained transfer rate can be approximated as 9600 KB/s.
→ Suppose, if each vertex is a component, then k=v, then there will not be any edges among them. So, v-k= 0 edges.
→ According to pigeonhole principle, every component have v/k vertices.
→ Every component there will be (v/k)-1 edges.
→ Total k components and edges= k*((v/k)-1)
Step-2: Level-2 has total 8*8=64 output lines. Based on the input, the decoder in level-1 enables one of the Decoders in level-2.
Step-3: The enabled decoder in level-2 selects one of the output lines and keeps that line high and remaining lines low.
→ Pre order properties are root,left and right
→ Based on the given sequence, we will get binary tree is
→ Based upon the inorder traversal, we will get preorder sequence is ABFGCDE.
R ∩ S = (R ∪ S) − [(R − S) ∪ (S − R)]
R ∪ S = (R ∩ S) − [(R − S) ∪ (S − R)]
R ∩ S = (R ∪ S) − [(R − S) ∩ (S − R)]
R ∩ S = (R ∪ S) ∪ (R − S)
R∩S = (R ∪ S) − [(R − S) ∪ (S − R)]
Symbol table length=152,
Number of entries=25,
Step-1: To find Occupation density require number of entries and length of symbol table.
Occupation Density = Number of entries/ Length of symbol table
does not map
Direct memory cache have = 64 block
Block size = 16 Bytes
Block number does the byte address of 1206 map=?
Step-1: To find block number = Byte Address / Block size
Step-2: Byte address 1206 map to 75th block.
Step-3: We have to find the cache block number.
Cache block number = (Block number) mod (Block size in cache)
= 75 mod 16
Step-2: It is given that without pipeline it takes 12ns to execute one instruction. Assuming there are n-instructions, time without pipeline = (12*n) ns.
Step-3: For time with pipeline, when there are k-stages in the pipeline, time taken to execute n-instructions is = (k+n-1) clock cycles.
Step-4: There are six stages in the pipeline, so k=6.
Time with pipeline = (6+n-1) clock cycles
= (n+5) clock cycles.
Step-5: It is also given that very large number of instructions are to be executed. So in the time with pipeline, (n+5) clock cycles, we can ignore 5. So time with pipeline for running large number of instructions = n clock cycles.
Step-6: 1 clock cycle time in pipeline = max. of all stage delays
= max(3, 2, 5, 4, 6, 2)
Now, time with pipeline= (n*6) ns
Asymptotic speedup = (12*n) / (6*n)