16-03-2012, 05:02 PM
Sample Questions [Computer Science]
Computer Science
1. Discrete Mathematics: Sets and Relations, Combinatorics (Counting) and Ele-
mentary Probability Theory, Graph Theory, Propositional and Predicate Logic.
2. Formal Languages, Automata Theory and Computability.
3. Data Structures and Algorithms: Arrays, Lists and Trees, Sorting and Search-
ing, Graph algorithms, Complexity of problems and NP-completeness.
4. Fundamentals of Programming Languages and Compilers: Control structures,
Parameter passing mechanisms, Recursion, Parsing and type checking, Memory
management.
5. Operating Systems and Concurrency
6. Switching Theory and Digital Circuits
7. Theory of Databases
Sample Questions [Computer Science]
1. A function f : f0; 1gn ! f0; 1g is called symmetric if for every x1; x2; : : : ; xn 2
f0; 1g and every permutation of f1; 2; : : : ; ng, we have
f(x1; x2; : : : ; xn) = f(x(1); x(2); : : : ; x(n)):
The number of such symmetric functions is:
(a) 2n+1 (b) 2n © 22n=n! (d) 22n (e) n!
2. Let r, s and t be regular expressions. Which of the following is wrong?
(a) (r + s) = (rs) (b) r(s + t) = rs + rt
© (r + s) = (s + r) (d) (rs + r)r = r(sr + r) (e) All are correct.
3. Consider the following program
x:=0; y:=1; z:=1;
while y <= N do
begin
x:=x+1; y:=y+z+2; z:=z+2;
end
Which of the following holds on termination of the program?
(a) (x + 1)2 = N (b) x =
p
N
© x2 = N (d) x2 N < (x + 1)2 (e) x2 < N (x + 1)2.
4. The maximum height of a rooted binary tree (all nodes have either two children
or none) with N nodes is
(a) N (b) logN © (N