In a village, people build houses in the same side of the road. A thief plans to loot the village. He wants maximum amount of money without having any risk of getting caught. By some means, the villagers know that their adjacent house is being looted or not and thus they become alert. So the thief cannot loot contiguous two houses. Given that the thief knows the amount of money stored in each house and the road is straight and there is no turning, which is the most efficient algorithmic strategy to solve this problem?
(A) Brute-force
(B) Dynamic Programming
(C) Backtracking
(D) Divide and Conquer

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: (GATE CS 2005)
(A) nk
(B) (n – 1) k+ 1
(C) n( k – 1) + 1
(D) n( k – 1)

Which of the following is not an in-place algorithm?
(A) Insertion sort
(B) Selection sort
(C) Merge sort
(D) Heap sort

Which is the correct order of the following algorithms with respect to their time Complexity in the best case ?
(A) Merge sort > Quick sort >Insertion sort > selection sort
(B) insertion sort < Quick sort < Merge sort < selection sort
(C) Merge sort > selection sort > quick sort > insertion sort
(D) Merge sort > Quick sort > selection sort > insertion sort

Consider an array of elements arr[5]= {5,4,3,2,1} , what are the steps of insertions done while doing insertion sort in the array.

(A) 4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5

(B) 5 4 3 1 2
5 4 1 2 3
5 1 2 3 4
1 2 3 4 5

(C) 4 3 2 1 5
3 2 1 5 4
2 1 5 4 3
1 5 4 3 2

(D) 4 5 3 2 1
2 3 4 5 1
3 4 5 2 1
1 2 3 4 5

Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array ?
(A) 50
(B) 25
(C) 75
(D) 100

Which of the following standard algorithms is not a Greedy algorithm?
(A) Dijkstra’s shortest path algorithm
(B) Prim’s algorithm
(C) Kruskal algorithm
(D) Huffman Coding
(E) Bellmen Ford Shortest path algorithm

A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:

Note : Each character in input message takes 1 byte.

If the compression technique used is Huffman Coding, how many bits will be saved in the message?
(A) 224
(B) 800
(C) 576
(D) 324

In question #2, which of the following represents the word “dead”?
(A) 1011111100101
(B) 0100000011010
(C) Both A and B
(D) None of these