Part - I (Algorithms, DS, Automata, Engg. Maths) & Part - II(Systems - OS, Networks, COA, Compilers, DBMS)

1. Give the tightest Asymtotic Notation for the recurrence : T(n) = T(n^1/2) + O(1) -

2. There are 16072016 users in Facebook. A graph is formed where an edge(u,v) is defined when a male is friend to a female and vice versa. Estimate the number of simple cycle of length 1607 formed in the graph?

3. If p is a prime number and 0<= a <= p^1/2, find a^((p^2)+1) mod p ?

4. There does not exists a pushdown automata for language L. Which of the following are correct:

a. TM does not exist

b. TM exits

c. DFA exists

d. NFA does not exists

5. There are 3 processes with CPU times of 15, 12 and 5 ms each which arrive at 0, 5 and 8 ms respectively. Scheduler uses Shortest remaining time first scheduling algorithm. Which processes finish first to last?

6. For Fibonnaci numbers, F(n) = F(n-1) + F(n-2) which of the following are correct :

a. Iterative solution has an exponential time complexity

b. Iterative solution has a linear time complexity on n

c. Iterative solution has a linear time complexity on input size

d. Recursive solution has exponential complexity

7. There are two sorted arrays of size n each having distinct elements. What is the maximum no. of comparisons req. in the worst case?

8. | a a2 a3 || b b2 b3 || c c2 c3 | matrix is non invertible (where a,b,c are non-negative integers) if and only if

9. In Huffman Coding, there are 4 characters with frequencies as 1, 0.5, 0.25 and 0.25. Average number of bits for encoding these characters?

10. Question on basics of DAG.

1. A floating point number is represented with 36 bits. The exponent is 8 bits plus a sign bit. The remaining bits consists of the mantissa including the sign bit. -32.25 decimal value is represented in floating point Normalized format(leading 1 is missing). Write the bitwise value of the EXPONENT part?

2. Page Fault for a series of pages when there are only 3 physical pages available using OPT replacement algorithm.

3. 255.255.255.240 is subnet mask, what is the maximum number of hosts allowed in the subnet?

4. Order of operations in Compiler ? (Lexical analysis, sematic, syntax .... machine code generation)

5. A processor has 6 stages of a pipeline with S1, S2, S3, S4, S5, S6. Maximum frequency of the processor is 2 GHz. S4 takes the longest amount of time to complete. What is the latency time?

6. There are 100 processes that can run concurrent.Each process requires 1KB of physical memory. Page Size is 64 B. Page table entries take 16 bits. What is the total amount of memory(in Bytes) required to store the page tables?

7. precondition and postcondition : (precondition) x <-x +5, y <- x - y, x <- x+y (postcondition :(x==15 and y==5)), what is the precondition?

8. Counting semaphore has value 10, wait and signal have there usual meanings. How many processes can concurrently access the critical section?

9. There are Insert and Retrieve_Max operations on a set {}. for n such operations what is the time complexity of the efficient algorithm possible?

a. n^2 b. nlogn c. n d. logn

10. There are 3 processes with run time 10,20 and 30. All arrive at 0. Scheduler knows the time taken for each. What is the avg waiting time for the processes?

Programming Test:

1. Implement a^b mod m where a,b and m can be huge. (Hint : O(log n))

2. Ms. Dany wants to clean the house having many rooms. She moves from one room to the next which takes 1 time unit. Each room has only one exit door. After some time she is bound to reach a room which she has cleaned already. Let the time taken to reach the already traversed room be 't' from the start. After that shes enters a cycle, let the length in the cycle be 'k'. Print 't' and 'k'.(do not condiser time taken to clean the room) (Hint : DFS)

3. Longest Increasing Subsequence with the help of 1-D array for dynamic programming. (Hint : MaxTill 1-D array)