D-Go

Entrance Examination (2013)
PhD in Computer Science


Time: 2hrs. Max. Marks: 75
Hall Ticket N umber: I


INSTRUCTIONS

1.
Write your hall ticket number in the box above and on the OMR sheet.

2.
rrhis test is for 2 h0.!1rs duration carrying 75 marks.

3.
All answers should be marked clearly in the OMR sheet only.

4.
Every correct answer gets 1 mark. There is negative marking of 0.33 mark for every wrong answer.

5.
Do all the rough work only in the pages provided in the question booklet, nowhere else.

6.
Use of non-programmable calculator and log-tables is allowed.

7.
Hand overthe OMR answer sheet to the Invigilator before the examination hall.

8.
The use of cellphones is strictly prohibited in the examina­tion halL All cellphones must be switched off when in the examination hall.




This page intentionally left blank. You may use it for rough work.


Entrance Examination (2013) PhD in Computer Science
1. The adjacency matrix of a graph is non-symmetric. The simplest conclusion that may be drawn is
A. The graph is directed.
B. The graph is undirected.
C. The graph is a disconnected.
D. The graph has cycles.

2. What is the radix of the numbers if the solutions to the quadratic equation
x2 -lOx 31 0

are x 5 and x
A. 11
B. 13
C.I0

D. None of the above.

3. Agile software development is NOT based on
A. Incremental Development
B. Cross Functional Teams
C. Detailed Project Plan
D. Iterative Development

4. Consider the following SQL Schema for a database about schools in a university and departments in the schools. Data types are omitted for brevity.
create table School (schoolName primary key, dean) create table Dept (deptName primary key, schoolName references School on delete cascade)
Write a single SQL statement that deletes all schools with more than 10 departments and also deletes all'departments in those schools.
A. delete from School
where 10 (select count from School
where Dept.schoolName School.schoolName)

B. delete fronl School
where 10 (select count from Dept
vvhere Dept.schoolNarne School.schoolNanle)

C. delete from School
where 10 (select count froln Dept
where Dept.schoolNarne School.schoolName)



Entrance Examination (2013) PhD in Computer Science
D. None of the above.
5. A machine uses a 16-bit two's complement representation for integers and little­endian byte ordering, that is, the least significant byte of an integer is stored at the lower address. Show what the following program will print out:
int 16-bit signed integer char (char
x Ox0013;
printf("x is %d
ll
Il n °/fi
" nr11,.
IV-IV-66 .." .... L .......


A. x 9<NEWLINE>19 0
B. x 19<NEWLINE>9 0
c.
x 9<NEWLINE>9 0

D.
None of the above.


6. The phases in the software development process are listed below in arbitrary order:

Design


Test


Code


Requirements Analysis


Maintenance


Deployment



The correct ordering is
A.
B.
C.
D.
7. Which of the following is NOT true about design patterns?
A. They are templates that can be used in different situations
B. They are formalized best practices
C. They can be directly transformed into code
D. None of the above.
8. Data items grouped together for storage purposes are called
A. Title
B. List

Entrance Examination (2013) PhD in Computer Science
c.
String

D.
Record



9. Testing which is perfofIned after lllodiflcation to the existing system is known as
A. Regression testing
B. Acceptance testing
C. Integration testing
D. Black-box testing

10. In DBMS, two files may be joined into a third file if
A. they have a row in common
B. they have a field in common
C. they have no records with the same value in common field
D. bot4 Band C

11. The correct recurrence relation for computing the time-complexity of the Towers of Hanoi problem is
A. 2T(n
B.
C. 1
D. 1
where is the number of steps to solve the· problem of size n.

12. An example of a consumable resource is
A. signal
B. text file
C. memory
D. printer

13. Given the declarations: int and int a [12J which of the following is illegal in
A. a
B. a
C. *p
D. p NULL

14. What does the following code do? a=a

a




-bo
Entrance Examination (2013) PhD in Computer Science
A. make a a band a
B. makea =0andb=a
C. make band a-b
D. swap the values of a and b
15. Which of the following transitions between process states is generally disallowed in operating systems?
A. From run to ready state
B. From ready to run state
C. From wait to run state
D. From run to wait state
16. Which of the following memory management schemes is the best in luinimising internal fragmentation?
A. Fixed Partition allocation
B. Segmented Memory allocation
C. Paged Memory allocation
D. Demand Paging
17. Which of the following is-usually a result of code?
A. Segmentation fault
B. Page fault
C. Cache fault
D. None of the above.
18. Which of the following is valid return value for a function in in which is declared
as
void in(int, char

A. NULL
B. 0
C. -1
D. None of the above.
19. Quick sort program is used to sort the input numbers in ascending order. If the first element is chosen as the pivot eleIllent, what is the total number of swaps (excluding swapping of the same element) the program is going to make in order to sort the input data in ascending order?
A. a
B. 4
C. 3
4/15



Entrance Examination (2013) PhD in Computer Science
D.2
20. Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behaviour in O(nlogn)?
A. Quicksort and Radix sort
B. Heap sort and Merge sort
C. Bubble sort and Selection sort
D. None of the above.
Answer Questions 21 -22 using the following Finite Automaton where S is the start state and T is the ending state:

b

21. The language accepted by the FA is:
A. (a
B. (a
C. (a
D. a*b
22. In order to make the automaton shown above accept the string of length zero, the language of all words not ending with letter b (and also the null string), the following minor changes will suffice:
A. Make right-hand state the start state and left-hand state the final state
B. Make right-hand state both the start and final state
C. Make left-hand state both the start and final state
D. Delete the left-hand state's self-loop labelled with b

23. The term "aging" refers to:
A. Keeping track of the time a page has been in memory for the purpose of LRU replacement
B. Keeping track of the total time a job has been in the system since it was first submitted
C. Letting jobs reside in memory for. a certain amount of time so that the number of pages required can be estimated accurately
D. Gradually increasing the priority of jobs that wait in the system for a long time to remedy indefinite blocking


Entrance Examination (2013) PhD in Computer Science
24. Which conclusion "logically follows" from the premises given below?
Prices are high.
If prices are high, one should sell bonds.
If interest rates are not low, one should not sell bonds.


A. Do not sell bonds
B. No conclusion can be drawn since the relationship between prices and interest rates has not been explicitly deijned.
C. Interest rates are high
D. Interest rates are low
25. Choose the best answer from the following if A E9 B (the symbol E9 is used for Exclusive OR
A. A EB C
B. B E9 C
C. A EB BEB C
D. All of the above.
26. The logical expression (fA A By A is:
A. A contradiction (always false)
B. A regular expression
C. A tautology (always true)
D. None of the above.
27. Software that measures, monitors, analyzes, and controls real-world events is called:
A. Real-time Software
B. System Software
C. Business Software
D. Scientific Software
28. A one-dimensional array A has indices 1 ... 75. Each element is a string and takes three memory words. The array is stored starting at location 1120 decimal. The starting address of is:
A. 1169
B. 1264
C. 1267
D . None of the above.
29. As an ordered group of homogeneous elements, a stack is more like
A. Record Entrance Examination (2013) PhD in Computer Science

B. File
C. Array
D. All of the above.

30. A die is tossed 7 times. What is probability that all six faces appear at least once?
A. 63/64
B.2/9

C. 5/54
D. 5/324

31. Ethernet belongs to the
A. Physical Layer
B. Application Layer
C. Session Layer
D. Medium Access Layer
in the ISO/OSI Network architecture.

32. In the Linux operating system, which important components needed for connectiv­ity to the Internet are found in the file named letc/resolv. conf?
A. Gateways
B. Firewalls
C. Domain Name Servers
D. None of the above.

33. Which of the following is NOT a string matching algorithm?
A. Knuth-Morris-Pratt
B. Graham-Kruskall
C. Boyer-Moore
D. Rabin-Karp

34. Which of the following is a protocol for sending email?
A.IMAP
B. POP3
C. SMTP
D. None of the above.

35. Which of the following is the world's first graphical browser'?
A. Mosaic
B. Internet Explorer


Entrance Examination (2013) PhD in Computer Science
c.
Opera

D.
Netscape


36. Which of the following could be a valid IPv4 address?
A. Ox3425
B. Ox34256721
C. Ox34
D. None of the above.
where indicates that the addresses are specified in hexa-decimal notation.
37. Which of the following is false about Greedy algorithms?
A. They never re-visit a choice made earlier.
B. They always run in time.
C. They always make the best choice possible given the information available at that time.
D. None of the above.
38. An undirected graph with n nodes is represented by its adjacency matrix A. It was found that An has only along its diagonal. Which of the following is then true about the graph represented by
A. The graph is acyclic.
B. The graph is planar.
C. The shortest path between any two nodes is longer than n hops.
D. None of the above.
39. The correct way to show that a new problem is NP-Complete is
A. Reduce a known NP..:Complete problem into the new problem in P time.
B. Reduce the new problem into a known NP-Complete problem in P time.
C. Show that there exists an algorithm for the problem which is equivalent to a known NP-Complete problem.
D. None of the above.
40. Which of the following graph problems is solved using a dynamic programming ,approach?
A. Shortest Path between any pair of nodes.
B. Maximum Clique Problem.
C. Colouring Problem.
D. All of the above.
8/15





Entrance Examination (2013) PhD in Computer Science
Questions 41 -44 are based on the following paragraph. Please read it carefully and then answer the questions.
Over the last two decades, stochastic resonance has continuously attracted consid­erable attention. The term is given to a phenomenon that is manifest in nonlinear systems whereby generally feeble input information (such as a weak signal) can be be amplified and optimized by the assistance of noise. The effect requires three basic ingredients: an energetic activation barrier or, more generally, a form of threshold; a weak coherent input (such as a periodic signal); a source of noise that is inherent in the system, or that adds to the coherent input. Given these features, the response of the system undergoes resonance-like behavior as a function of the noise level; hence the name stochastic resonance. The underlying mechanism is fairly simple and robust. As a consequence, stochastic resonance has been ob­served in a large variety of t)yt)LeIIlt), including bistable ring lasers, semiconductor devices, chemical reactions, and mechanoreceptor cells in the tail fan of a crayfish. In this paper, the authors report, interpret, and extend much of the current derstanding of the theory and physics of stochastic resonance. They introduce the readers to the basic features of stochastic resonance and its recent history.
41. Which of the following best defines stochastic resonance?
A. Changes in probabilities of occurrence of certain signals based on random pro­cesses

B. Amplification of a signal by the addition of noise
C. Attenuation of a signal by the addition of noise
D. Resonance caused by random processes

42. Which of the following is not required for stochastic resonance?
A. A threshold type barrier
B. Noise within the signal
C. Weak signal
D. Strong signal

43. In the last sentence, the word "they" refers to
A. Authors
B. Weak signals
C. Reporting, interpreting and extending the understanding of signals
D. None of the above.

44. What is the reason for stochastic resonance to be observed in a large variety of systems?
A. There is noise everywhere
B. There are signals everywhere
C. The basic mechanism is simple and robust
D. Resonance occurs all the time



Entrance Examination (2013) PhD in Computer Science
Questions 45 -48 are based on ..the following paragraph. Please read it carefully and then answer the questions.
The following text is from the 'lUring Award Lecture by the great computer scientist,
C. A. R. Hoare.
"Around Easter 1961, a course 011 ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. I attended this course with my colleague in the language project, Jill Pym, our divisional Technical Manager, Roger Cook, and our Sales,Manager, Paul King. It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining. It was there that I wrote the procedure, .immodestly named QUICKSORT, on which my career as a computer scientist is founded. Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world. I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed."

45. From the above paragraph, which of'the following statements is true?
A. A course on ALGOL 60 was offered to Edsger W. Dijkstra and others by C. A.
R. Hoare
B. QUICKSORT is invented by C. A. R. Hoare
C. C. A. R. Hoare was-a divisional Technical Manager
D. None of the above.

46. Where did C. A. R. Hoare first learn about recursive procedures?
A. In a course on ALGOL 60
B. During discussions with Jill Pym, Roger Cook and Paul King
C. From the designers of ALGOL 60
D. None of the above.

47. Why does C. A. R. Hoare say QUICKSORT is "immodestly" named?
A. It is not easy to explain QUICKSORT
B. Giving the adjective "quick" in the name is not modest
C. QUICKSORT is not possible without the recursive procedures of ALGOL 60
D. None of the above.

48. What, in C. A. R. Hoare's opinion, is the main aspect to aim for in designing programming languages?
A. Having QUICKSORT procedure
B. Enable elegant expression of ideas
C. Easy to program sorting routines
D. Having recursion



Entrance Examination (2013) PhD in Computer Science
49. Two algorithms A and B take n2 days and 2n seconds respectively to solve a problem on an instance of size n. What is the size of the smallest instance for which algorithm A outperforms B in the given choices?
A. 10
B. 20
C.30
D.40

50. Suppose that a list of n sorted integers is given. Which of the following algorithms can detect that the input is sorted in time?
A. insertion sort only
B. selection sort only
C. bubble sort and selection sort
D. bubble sort and insertion sort

51. The following statements are about Prim's and Kruskal's algorithnls to find Mini­mum Spanning 'free in a weighted connected graph of n vertices. Which of them is not true?
A. Kruskal's algorithrn starts by finding an edge with the least weight
B. At any intermediate-stage, the output of Prim's algorithm is a tree
C. Kruskal's algorithm terminate once the output has edges
D. Prim's algorithm needs to check at each step if a cycle is formed

52. for
A. nlogn and 210
B. 2n and
C. 210gn and n
D. n2 and n3

53. A tree has x vertices of degree 2 vertices of degree 4 vertices of degree 3 and 3 vertices of degree 4. What is the value of
A. 12
B. 10
C. 8
D. Cannot be computed
54. Given the following grammar,
AB
A a
A BaB
B bbA

which of the statements below is false?



Entrance Examination (2013) PhD in Computer Science
A. The length of every string produced by the grammar is even
B. No string produced by the grammar has an odd number of consecutive
C. No string produced by the grammar has three consecutive
D. No string produced by the grammar has four consecutive
55. Which of the following programming language features requires stack-based storage allocation rather than static allocation?
A. Recursive procedures
B. Call by Reference parameters
C. Arbitrary goto's
D. Two dimensional arrays
56. What is the postfix form of the expression in prefix form
A.
B.
C.
D. AB**CD­
57. The initial configuration of-a queue is is at the front). To get the config­uration one needs a minimum of
A. 2 deletions and 3 insertions
B. 3 deletions and 2 insertions
C. 3 deletions and 3 insertions
D. 3 deletions and 4 insertions
58. In the following binary sea:rch tree if we delete the node 14, then the preorder traversal of the tree after deletion is


A. 12,6,3,30,85,67,95
B. 6,3,12,30,85,95,67
C. 12,3,6,85,30,95,67
D. 30,6,3,12,85,67,95

Entrance Examination (2013) PhD in Computer Science
59. The running time of an algorithm is given by
if n 3
+T·(n
otherwise
Then
A.
B. O(logn)
C.
D. 0(n2)

60. If a graph G(V iR flo eomplete graph; time required to reach any node in the graph using breadth first search is
A.
B.
C.
D. O(V x

61. If an array is used to implement a tertiary tree, the positions of children any node i can be found at the -locations
A. 2i,2i 1,2i+2
B. 3i,3i 1,3i 2
C. 3i-1,3i,3i 1
D. 3i 3,3i 3i 5

62. In which of the following variables are created at the time of a function call and destroyed when the function returns?
A. integer variables
B. parameters to the function
C. static variables declared within the function
D. extern variables

63. Which of the following methods is used for accessing disk blocks in an operating system?
A. Linked list
B. Indirect Access
C. Hashing
D. All of the above.

64. Which of the scheduling algorithms does not result in starvation?
A. FCFS




Entrance Examination (2013) PhD in Computer Science
B. Multilevel queues

C. Shortest Job First
D. Priority scheduling

65. Waterfall model in software engineering is an example of
A. Linear
B. Rapid
C. Iterative
D. Interactive

66. A system has a 24-bit processor and uses a page size of 2KB. Considering that all the registers in the processor are limited to 24 bits, how many entries may be expected in the page table?
A. 8192
B.4096

C. 2048
D. None of the above.

67. A sequence d d2, ... dn) is called graphic if there is a simple undirected graph with degree sequence d. Which of the following are not valid graphic se­quences?
A.
B.
C.
D.

68. What is the maximum number of edges in a simple undirected bipartite graph of n nodes?
A. nC2
B. Ln2/4J
c.
Ln2/2J

D.
In/2J



69. Component level design metric includes
A. Cohesion metric
B. Complexity metric
C. Coupling metric
D. All of the above

70. Fault tolerance in software applications can be ensured through
A. Self-checking facility


-bO
Entrance Examination (2013) PhD in Computer Science
B. Redundant modules
C. Recovery blocks
D. All of the above
71. Simplify the following Boolean function using four-variable Karnaugh maps.


A. CD+ABC+ABD
B. ACD BCD ABC ABD
C. ABC'D ABC CD
D. None of the above.
72. A new child process is required for
I. A login shell
II. Webserver
III.
Device driver for disks

A.
I only

B.
II only

C.
III only

D.
II and III only


73. Which of the following is not related to static testing?
A. Code Review
B. Code Walkthrough
C. Code Inspection
D. Code Execution
74. A square matrix is stored either in row-major or in column-major order. Which of the following statements is necessarily true?
A. The diagonal elements are stored in the same locations in either order
B. The elements in locations where i and j are both odd are stored in the saIne locations
C. All the elements in the last row are in the same locations
D. None of the above.
75. uinta is used in a programming language to represent 8-bit unsigned integers from oonwards. If there is either an under-or an over-flow, the nurnbers cycle around. What is the result of adding 210 and 56.
A. -16
B. 15
C. 10
D. None of the above.