1. Two motorists set out at the same time from A to a distance of 100 miles. They both followed the same route and travelled at different though uniform speeds of integral number of miles/honr. The difference in their speeds was a prime number of miles/hour. After they had been driving for 2 hrs, the distance of the slower car from A was five times that of the faster car from B. How fast did the motorists drive?

30 and 37 miles/hour

40 and 42 miles/hour

47 and 49 miles/hour

None of the above

2. A job is done by M men in D days. Then M+N men can do the same job in

MD/M+N ays·

D/M days

days

D N days .

3. An academic institute starts a class at 10:00 A.M. and ends at 1:47 P.M. It has 4 periods of equal distribution of time. After each period there is a gap of 5 minutes to start another period. What is the exact duration of period?

51

52

53

57

4. A contractor estimated that one of his bricklayers would take 9 hrs to build a certain wall and the other 10 hours. However, he knew from experience that when they worked together, 10 fewer bricks got laid per hour. Since he was in a hurry, he put both men on the job and found it took exactly 5 hours to build the wall. How many bricks did it contain?

18

90

900

It can not be determined from the given data

5. The number of ways in which 3 men and 2 women can sit in a row so that no two men are adjacent is

12

24

72

9

6. Given the statement, "1 always cut the top-right comer of a milk packet for opening it", a milk packet with its top-right corner cut is

a necessary condition for the packet to have been opened by me

a sufficient condition for the packet to have been opened by me

both Ii necessary and a sufficient condition for the packet to have been opened by me

sometimes a necessary condition and sometimes a sufficient condition for the packet to have been opened by me

7. A common problem in Computer Science research is to minimise an equation of the form



where A is a parameter, Et, Em and Ed are the total, model and data errors. Model error reflects the mismatch between predicted and actual values, while data error is the error due to noise in the data. For noisy data, the value of A should be

Close to 0

Close to 1

Nearly 0.5

None of the above

Using general knowledge about Computer Science and by reading the fol­lowing paragraph carefully, answer the Questions 8 -12 below:

Princeton asked me to develop a course in automata theory. Since there were no courses or books on the subject, I asked McCluskey to recommend some materials for a course on automata theory. He gave me a list of six papers and told me that the material would probably give students a good background in automata theory. McCluskey's list included works by Warren McCulloch and Walter Pitts, Michael Rabin and Dana Scott, John Backus and Peter Naur, Noam Chomsky, Juris Hartmanis and RichardStearns, and, of course, Alan Turing. In 1943 McCulloch and Pitts. working in neurophysiology, published a paper on a logical calculus for describing events in neuron nets. The paper had a notation for describing how these strings of zeros and ones combine in neurons to produce new strings of zeros and ones. This notation was subsequently developed into the language of regular expressions for describing sets of strings. Rabin and Scott were mathematicians who developed a model of a computer with a finite amount of memory. They called this model the finite-state automaton, and showed that the possible behaviors of finite-state automata were precisely those behaviors that could be described by the regular expressions that grew out of the work of McCulloch and Pitts. The work of Hartmanis and Stearns attracted researchers and focused· attention on the topic of complexity. Among the more significant advances that resulted were the classification of the complexity of most major mathematical theories, the reducibility of many combinatorial problems, the concept of NP-completeness, and a deeper understanding of concepts such as randomness. Also, through this course I met Jeffrey Ullman and Alfred Aho, with whom I subsequently collaborated for many years. Formal Languages and Automata Theory, which I wrote with Ullman, also evolved from this course.

8. Who is in the passage?

McCluskey·

Jeffrey Ullman

John Hopcroft

Edsger Dijkstra

9. denotes some missing sentences in the passage. What are the most likely missing sentences?

Sentences about Hopcroft's early work in the course

Sentences about work by Hartmanis and Stearns

Sentences about work by Backus, Naur and Chomsky

Sentences about Princeton university

10. Who invented the finite state automaton?

Hopcroft and Ullman

Chomsky

McCulloch and Pitts

Rabin and Scott

11. What was the difficulty in offering the course on Finite Automata Theory at Princeton?

There were no textbooks for the subject

There were no teachers for the subject

There were no students for the subject

None of the above

12. Which of the following did not grow out of the work by Hartmanis and Stearns?

Regular expressions

Reducibility of combinatorial problems

Classification of complexity

NP-Completeness

13. Which plots show the relationship between two or three variables when comparing data sets consisting of multiple observations?

Histograms

Scatter Plots

Probability Plots

All the above

14. Variability in groups of observations with widely differing means can be compared using the following measure

Coefficient of variation

Mean deviation

Measure of skewness

None of the above

15. Features attributes of patterns, which can be measured, are called

Qualitative measure .

Data

Variables

All

16. Find the sample variance, standard deviation and range of the following data: 572, 572, 573, 568, 569, 575, 565, 570

Variance standard deviation 3.162, range 11

Variance standard deviation 4.162, range 10

Variance standard deviation 3.162, range 09

Variance standard deviation 3.162, range 10

17. A president and a treasurer are to be chosen from a student club consisting of 50 people. How many different choices of officers are possible if there are no restrictions?

2450

2500

1225

1250

18. In a college football training session, the defensive coordinator needs to have 10 players standing in a row. Among these 10 players, there are 1 freshman, 2 sophmore, 4 juniors and 3 seniors. How many different ways can they be arranged in a row if only their class level will be distinguished?

14600

12600

12800

None of the above

19. In how many ways can 5 different trees be planted in a circle?

24

12

6

120

20. If at least 85% students in a class are good in Physics, at least 80% are good in Computer Science and at least 75% are good in Mathematics, then the percentage of students who are good in all the three subjects is at least

25

40

20

60

21. A family has two children. What is the probability that both the children are girls given that at least one of them is a girl?

1/4

1/2

3/4

1/3

22. A person has 2 bank cards, each with a digit number. The 1st number is 4 times the 2nd. The 1st number is the reverse of the 2nd. Which of these is the first number?

8421

2178

8712

None of the above

23. A man passed 1/6th of his life in childhood, 1/12th as youth and 1/7th more as a bachelor. Five years after his marriage, a son was born who died 4 years before his father at half his father's final age. What was the final age of the man?

48

84

96

64

24. Ram said, "When I am as old as my father is now, I shall be five times as old as my son is now. By then, my son will be eight years older than I am now. The combined ages of my father and myself are 100 years.". How old is Ram's son?

13

15

17

None of the above

25. If a flag has three horizontal stripes which can be colored out of five different colors, how many flags can be constructed such that they are not identical and the adjacent stripes are not of the same color?

15

30

45

50

26. A bag contains 6 white balls, 6 black balls and 8 green balls. What is the probability of 3 balls which were drawn randomly of same colour?

3/1140

20/1140

56/1140

96/1140

27. A person walks 8 KM towards east. He took left turn and walks for 1 KM towards north. He took right turn and walks towards east for 7 KM. Now, he turns to right and walks towards south. Now, how much of distance; this person is away from the starting point?

25KM

23KM

19KM

17KM

28. Suppose today is Saturday, after 72 days what will be the day?

Saturday

Sunday

Monday

TUesday

29. A shopkeeper sold two toys at Rs. 120 each. While he made a profit of 20% on one, he incurred a loss of 20% on other. Then, overall, he

made a profit of Rs. 10

incurred a loss of Rs. 10

incurred a loss of Rs. 12

neither made profit nor incurred loss

Read the following text carefully, so as to answer the questions 30-33

Five Companies D and E saw growth rates ranging from 10% to 50% in the year 2015. The company A with the least revenues of Rs. 600 crores in 2015 saw the maximum growth rate of 50% and the Company 0 with the highest revenue saw the least growth rate of 10%. Company revenues in 2016 was equal to that of Company 0 in 2015, while Company 2016 revenue was equal to that of Company in 2015, Company 2016 revenue was equal to that of Company E in 2015. John, an accountant observes that one of the companies has twice the growth rate of another. Mathew, his colleague corrects him and says that this is the case in two different instances. Company E has a revenue equal to the average seen in Company A and and growth rate equal to the average growth rate of A and O. Ram, known for his cryptic-speak mentioned that if company C had grown at the rate seen by company A in 2015 would have reached the revenues seen by Company 8 in 2016.

30. What is the overall average growth rate seen by all 5 companies put together?

23.5%

27%

24.2%

28.5%

31. Which company had the third highest growth rate7

B

C

D

E

32. Which company had the median revenue in 20167

A

B

C

E

33. In absolute terms, which company added the maximum revenue in 20167

A

B

C

E

The following chart represents number of students of AMS careers at its Hyderabad centre who passed the CAT, XAT, CET or none of these ex­ams. (Assume that there are no students who passed more than one exam). Answer questions 34-37 based upon the information provided in this chart.

<img src='./qimages/16014-34 to 37.jpg'>

34. What was the percentage of students who cleared CAT exam in 2000?

19.56%

12.65%

14.28%

11.76%

35. What was the percentage of students who succeeded in at least one of the three exams in 2000?

82.4%

82.8%

82.35%

83.3%

36. Which year showed the best results in CAT entrance exams for the institute (in terms of percentage of students who cleared)?

2000

2001

2002

Can't be determined

37. What is the percentage increase in number of students in year 2002 over year 2000?

30%

17.64%

117.6%

85%

Answer questions 38-40 based upon the following information.

A group of 7 people Salman, Shahrukh, Aamir, Ranbir, Imran, Shahid and Akshay are to be arranged in a row of 7 chairs (not necessarily in the same order), such that 2 adjacent chairs are facing opposite directions but not facing each other. Given below are some of the conditions to be followed for the seating arrangement:

Akshay sits in a chair whose direction is opposite to that of Imran

None of Salman, Shahrukh or Aamir can sit adjacent to each other

Ranbir and Shahid are best friends, so they always sit together

Imran has 4 people sitting to his right

Aamir is sitting 2 positions to the right of Ranbir 9

38. Which of the following can never occupy adjacent chairs?

Sharukh Shahid

Akshay Imran

Aamir Imran

Ranbir Salman

39. If Ranbir is 3 places to the right of Imran, then who is 2 places to the left of Akshay?

Either Shahrukh or Salman

Aamir

Either Aamir or Shahrukh

None of the above

40. If Akshay is 3 places to the left of Shahid, then who can occupy the corner positions (in any order)?

Salman and Aamir

Shahrukh and Salman

Shahrukh and Aamir

None of the above

41. When an IP datagram is received by a system, the following happens to the currently running process:

Its state is changed to BLOCKED

Its state is changed to READY

Process is killed

Process is suspended

42. In a uniprocessor system that is running a non-preemptive kernel, which of the following statements is TRUE:

I. Deadlock never happens

II. Multi-threading cannot be implemented on this system

III. Atomic instructions prevent mutual exclusion problems

I and III

II and III

III only

II and III

43. Which of the following statements is NOT TRUE for run-time binding?

Process cannot be relocated

Process cannot be swapped out and into a different memory location

Process execution is highly efficient

Two process address spaces may have a conflict

44. Which of the following statements is TRUE of Zombie processes?

I. Zombies are an issue primarily in server systems and not in clients

II. Zombies make the system run slower

III. Zombies are eliminated by inheritance by the init process

II and III

II only

IandIII

II and III

45. Which of the following is NOT possible?

TLB miss with no page fault

TLB hit with no page fault

TLB miss with page fault

TLB hit with page fault

46. Which of the following -client or server or both -does an active Or passive open of sockets?

Both can do passive open

Both can do active open

Clients can do only passive open

Servers can do only passive open

47. Given the IP address 202.41.85.117/22, how many hosts can this network support?

1022

1024

512

254

48. A router R1 receives the following advertisements from its neighbors when using RIPvl that uses the distance vector algorithm as the routing protocol:

R2

R3

Which of the following can we infer from these advertisements?

I. R2 and R3 are neighbors of each other

II. Count-to-infinity problem cannot occur in this network

III. Split horizon is enabled in RIPv1 implementation being used by R2 and R3

II and III are all TRUE

I and II are TRUE

II and III are TRUE

Only I is TRUE

49. A disk is highly error-prone especially in sectors which are heavily used. In such a disk which of the following mechanisms for maintaining metadata of the files is WORSE?

Regular Linked Allocation Scheme

Regular Indexed Allocation

inode form of indexed allocation

FAT form of linked allocation

50. A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit. The number of bits in the tag field of an address is

11

14

16

27

51. A processor that has carry, overflow and sign flag bits as part of its program status word performs addition of the following two complement numbers: 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be:









52. A RAM chip has a capacity of 1024 words of 8 bits each (1K x 8). The number of 2 x 4 decoders with enable line needed to construct a 16K x 16 RAM from 1K x 8 RAM is

4

5

6

7

53. Consider the following sequence of micro-operations.

MBR
MAR
PC
Memory MBR

Which one of the following is a possible operation performed by this sequence?

Instruction fetch

Operand fetch

Conditional branch

Initiation of interrupt service

54. Let R be a relation schema with C E EC D and A B. Which of the following is a key for

CD

EC

AE

AC

55. Which of the following statements is false?

Any relation with two attributes is in BCNF

A relation in which every key has one attribute is in 2NF

A prime attribute can be transitively dependent on a key in 3NF relation

A prime attribute can be transitively dependent on a key in BCNF relation

56. Relations produced from E-R model will always be in

3NF

BCNF

4NF

2NF

57. Consider a schema R and functional dependencies A B and Then the decomposition R1 and R2 is

Dependency preserving but not lossless join

Dependency preserving and lossless join

Lossless join but not dependency preserving

Neither lossless join nor dependency preserving

58. How many sub-graphs with at least one vertex does a labeled complete graph with 3 vertices have?

7

10

12

17

59. The number of paths of length 3 between a single pair of two distinct vertices in a complete graph with 4 vertices is

5

6

7

8

60. For a set S1 let denote power set of i.e., the set of all subsets of 8. Suppose S1 and S2 are any two sets. Consider the following statements regarding S1 and S2

I. U P(S1 U S2)

II. n P(S1 n S2)

III. S1 S2)

IV.

Then

Only I and IV are true

Only II and III are true

Only II and III are true

Only III and IV are true

61. Consider that 135 cities in India are to be connected by high-speed fibre optic links. Each link will· connect a pair of cities so that the entire. network of 135 cities is connected. The additional requirement is that the network will remain connected if any single link fails. What is the minimum number of links needed to set up the network?

268

9045

270

135

62. Consider an unordered doubly linked list with n elements. Given a key, all the elements less than the key are moved to the left of the key, and all the elements greater. than the key are moved to the right of the key preserving the same order as in the original list. What is the time complexity for doing this?





O(n log

None of the above

63. Consider a weighted undirected graph G with positive edge weights. Let be an edge in the graph. It is known that the shortest path from a vertex s to u has weight 35 and the shortest path from s to v has weight 56. Which of the following is always true?

Weight of 21

Weight of 21

Weight of 21

Nothing can be said about the weight of

64. Consider a graph G with six vertices. Which of the following sequences can not represent the degree of its vertices

1

2

2

1

65. Suppose there is a polynomial time reduction from problem A to problem B. Which of the following can be inferred from this fact?

If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A.

If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.

If we have a polynomial time algorithm for we must also have a polynomial time algorithm for B.

If we don't know whether there is a polynomial time algorithm for there cannot be a polynomial time algorithm for A.

66. Time complexity of 0/1 Knapsack Problem when there are n items and total weight that can be carried in the knapsack is no more than some fixed number M is

O(M x





O(M

67. The source symbols are listed in order of decreasing probability, p .4, q .2, r .2, s .1, t .1. If a binary tree is generated using Huffman code greedy algorithm, with· assigning 0 to every left edge and 1 to every right edge, then the average code length is

3.0

2.4

2.2

2.8

68. Let A be n x n real matrix and A3 then A^36 2A is

I

A(A

2I

I

69. Which algorithm for string matching pre-processes the pattern to find matches of prefixes of the pattern with the pattern itself

Knuth-Morris-Pratt's algorithm

Boyer Moore's algorithm

Robin Karp's algorithm

None of these

70. The best case performance of heap sort for sorting a given list of numbers into descending order occurs if the given list is in

ascending order

descending order

random order

all of the above

71. Consider a node X in a binary tree. Given that X has two children, let Y be in-order successor of X. Which of the following is true about

Y has no right child

Y has no left child

Y has both children

None of the above

72. If a sorted list is provided, which is the best strategy to search for an element in the list?

linear search

binary search

ternary search

none of the above

73. You are given pointers to the first and the last nodes of a singly linked list, which of the following operation is dependent on the length of the linked list?

Delete the first element.

Insert a new element as the first element.

Delete the last element of the list. r

Add a new element at the end of the list.

74. Let G be a Context Free Grammar in Chomsky Normal Form. To derive a string of terminals of length £ using the number of productions to be used is

2l-1

2^l

2l+1

not fixed and depends on actual productions

75. L1, L2 and L3 are three languages. If L1 and L2 are regular and if L1 L2L3, then

L3 has to be regular

L3 can never be regular

L3 need not be regular

L3 can never be a context free

76. Let L be a regular language. The language LR such that w is the reverse of v where vEL} is

regular

context free, but not regular

context sensitive, but not context free

recursively enumerable, but not context sensitive

77. Let L be a regular language. The language LF such that w is a prefix of v where VEL} is

regular

context free, but not regular

context sensitive, but not context free

recursively enumerable, but not context sensitive

78. Consider the function f defined below:

struct item

int data;
struct item next;

int f(struct item

return NULL) NULL) p data



For a given linked list the function f returns 1 if and only if

The elements in the list are sorted in non-decreasing order of data value.

The elements in the list are sorted in non-increasing order of data value.

Not all elements in the list have the same value.

None of the above.

79. What is the output of following function when called with start pointing to the first node of the following singly linked list?



void fun(struct node* start){
if(start NULL)
return;
printf start->data);
if(start->next NULL)
fun(start->next->next);
printf("%d start->data);


1 3 5 5 3 1

1 3 5

1 2 3 4 5 6

1 3 5 3 1

80. Following is pseudo code of a function that takes a queue Qas an argument, and uses a stack S to do processing.

void fun (Queue
Stack creates an empty stack S
Run while Q is not empty
while
//Dequeue an item from Q and push the dequeued item to S push(&S, deQueue(Q));

while Stack S is not empty while
an item from S and enqueue the popped item to Q enQueue(Q,



What does the above function do in general?

Removes the last item from Q.

Keeps the Q same as it was before the call.

Makes Q empty.

Reverses the Q.