Question
What is an optimal Huffman code for alphabet b of the following set of frequencies
 a: 45, b:13, c:12, d:16, e:9, f:5
Select one:
a. 111
b. 101
c. 100
d. 001

The correct answer is:101
Question
In flow networks Residual capacity Cf (u,v)=
Select one:
a. c(u,v) – f(u,v)
b. t(u,v) – s(u,v)
c. f(u, v) – c(u,v)
d. s(u,v) – t(u, v)

The correct answer is:c(u,v) – f(u,v)

Question
In Ford-Fulkerson algorithm, flow of the augmenting path is selected based on
Select one:
a. cf(p) =min{ cf (u,v):(u,v)is in f-P }
b. cf(p) =min{ cf (u,v):(u,v)is in p }
c. cf(p) =max{ cf (u,v):(u,v)is in f-P }
d. cf(p) =max{ cf (u,v):(u,v)is in p }

The correct answer is: cf(p) =min{ cf (u,v):(u,v)is in p }

Question
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Select one:
a. Queue
b. Heap
c. Stack
d. B-Tree

The correct answer is:Queue

Question
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
Select one:
a. Warshall’s algorithm
b. Performing a DFS starting from S.
c. Dijkstra’s algorithm starting from S.
d. Performing a BFS starting from S

The correct answer is:Performing a BFS starting from S

Question
Consider the decision problem 2CNFSAT defined as follows:

Select one:
a. NP-hard, but not NP-complete.
b. solvable in constant time since any input instance is satisfiable.
c. NP-Complete.
d. solvable in polynomial time by reduction to directed graph reachability

The correct answer is:solvable in polynomial time by reduction to directed graph reachability

Question
Find the Running Time of the fastest algorithm to calculate the shortest path between any two vertices of a graph where all edges have equal weights.
Select one:
a. 0(V  log2V+E )
b. 0 (E+V)
c. 0(V log V2+E)
d. 0 (V+E) log2V

The correct answer is:0 (E+V)

Question
Match the following
            Group A                                                                      Group B
a) Dijkstra's single shortest path                                     p) Dynamic Programming
b) Bellmen Ford's single shortest path algorithm           q) Backtracking
c) Floyd Warshell's all pair shortest path algorithm        r) Greedy Algorithm
Select one:
a. a-p,  b-r, c-q
b. a-p,  b-p, c-p
c. a-r,  b-p, c-p
d. a-r,  b-q, c-p

The correct answer is: a-r,  b-p, c-p

Question
Match the following:

              List – I                           List – II

         1 Quick Sort              a Divide and Conquer

         2 Graph colouring     b Greedy

         3 String editing          c Dynamic Programming
                                     
         4 Prim’s Algorithm   d Back tracking
Select one:
a. 1-a, 2-c, 3-b, 4-d
b. None of these
c. 1-a, 2-d, 3-c, 4-b
d. 1-b, 2-a, 3-d, 4-c

The correct answer is: 1-a, 2-d, 3-c, 4-b

Question
Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable
   from the source.
Select one:
a. P Only
b. Neither P nor Q
c. Both P and Q
d. Q Only

The correct answer is: Q Only

Question
The time required to find shortest path in a graph with n vertices and e edges is
Select one:
a. O (e)
b.  O (e²)         
c.  O (n)   
d.  O (n²) 

The correct answer is: O (n²)

Question
There are 5 items as follows

Select one:
a. 260 $
b. 270 $
c. 290$
d. 250$

The correct answer is:260$

Question
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
Select one:
a. 44000
b. 19000
c. 25000
d. 248000

The correct answer is:19000

Question
A simple Graph G = L U R, set of 2 non-empty vertices and each vertex from L  has an edge to atleast one vertex of R, is called as
Select one:
a.  Bifocal graph
b. Bipartite Graph
c. Complete graph
d. Flow-network graph

The correct answer is: Bipartite Graph

Question
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
Select one:
a. Π is NP-complete
b. Π is neither NP-hard, nor in NP
c. Π is NP-hard but not NP-complete
d. Π is in NP, but is not NP-complete

The correct answer is:Π is NP-complete

Question
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
       = expr1, if i,j > 0 and X[i-1] = Y[j-1]
       = expr2, if i,j > 0 and X[i-1] != Y[j-1]
Select one:
a. expr2 ≡ max(l(i-1,j-1),l(i,j))
b. expr2 ≡ max(l(i-1, j), l(i, j-1))
c. expr1 ≡ l(i-1, j) + 1
d. expr1 ≡ l(i, j-1)

The correct answer is: expr2 ≡ max(l(i-1, j), l(i, j-1))

Question
If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
Select one:
a. O(log n)
b. O(n³)    
c. O(n log n)   
d. O(n²)

The correct answer is: O(n³)

Question
Kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
Select one:
a. edges,edges
b. vertex,vertex
c. edges,vertex
d. vertex,edges

The correct answer is: edges,vertex

Question
For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
Select one:
a. O(NW), O(N)
b. O(NW), O(N+W)
c. O(N), O(NW)
d.   O(N+W), O(NW)

The correct answer is:O(NW), O(N+W)

Question
Consider the following two problems of graph.
1) Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2) Given a graph, find if the graph has a cycle that visits every edge exactly once. Which of the following is true about above two problems
Select one:
a. Both problems belong to P set
b. Problem 1 belongs to P set and 2 belongs to NP Complete set
c. Problem 1 belongs NP Complete set and 2 belongs to P
d. Both problems belong to NP complete set

The correct answer is: Problem 1 belongs NP Complete set and 2 belongs to P

Question
This clustering approach initially assumes that each data instance represents a single cluster.

Select one:
a. expectation maximization
b. K-Means clustering
c. agglomerative clustering
d. conceptual clustering

The correct answer is:agglomerative clustering

Question
The correlation coefficient for two real-valued attributes is –0.85. What does this value tell you?

Select one:
a. The attributes are not linearly related.
b. As the value of one attribute decreases the value of the second attribute increases.
c. As the value of one attribute increases the value of the second attribute also increases.
d. The attributes show a linear relationship

The correct answer is: As the value of one attribute decreases the value of the second attribute increases.

Question
Time Complexity of k-means is given by

Select one:
a. O(mn)
b. O(tkn)
c. O(kn)
d. O(t2kn)

The correct answer is: O(tkn)

Question
Given a rule of the form IF X THEN Y, rule confidence is defined as the conditional probability that

Select one:
a. Y is false when X is known to be false.
b. Y is true when X is known to be true.
c. X is true when Y is known to be true
d. X is false when Y is known to be false.

The correct answer is: Y is true when X is known to be true.

Cloud Computing in simple terms:

Welcome to Cloud Computing, The first question in our mind is - What is Cloud computing?

I am pretty sure, you also looking for the same. So we will directly jump into the interesting scenario-based language. We have tons of information from various sources as NIST(National Institute of Standards and Technology), 451 Group, analyst firm like Gartner, Wikipedia etc.

As per our information - It is very large where several services and data you access all over the network. The software and data which you access for your work doesn't exist on your computer and set on the servers. This concept of using services stored on other system called cloud computing.
There was a time when several clients want to access information from several terminals but the mainframe technology was too costly so to save money they want something new. At that time it was just a hope but now we have a cloud today.

In a simple term - It's a term for a service made available over the network on-demand for an optimized highly scalable service provider, the name cloud computing was inspired by the cloud symbol. Exact information and origin of the cloud are still debated but attributes are agreed upon.

Accessing Cloud:
We can access Cloud using various devices shown below in the diagram:

Question:
Give an example for each of the following preprocessing activates
a. Incomplete
b. Inconsistent

Answer:
Data Processing: It is a data mining technique that involves transforming raw data into an understandable format. Our Real-world data is often incomplete, inconsistent, and/or lacking in certain behaviors or trends, and is likely to contain many errors. Hence it is needed for resolving such issues.
"Preprocessing is needed to improve data quality"

A. Incomplete: Lacking attribute values, lacking certain attributes of interest, or containing only aggregate data.
E.g. Many tuples have no recorded value for several attributes,
Occupation = “ ” (missing data)

B. Inconsistent: Containing discrepancies in codes or names.
E.g.
Age = “42”, Birthday = “03/07/2010”
Was rating “1, 2, 3”, now rating “A, B, C”
discrepancy between duplicate records

Question
One of your friends has written a program to search a string in a string and requested you to test the below function using equivalent class portioning :

function strpos_generic( $haystack, $needle, $nth,  $insensitive)
Following are terminology definitions:

• $haystack= the string in which you need to search value
• $needle= the character that needs to be searched, the $needle should be a single character
• $nth= occurrence you want to find, the value can be number between 1,2,3
• $insensitive= 1- case insensitive, 0 or any other value is case sensitive
• Passing as Null as parameter in haystack or needle is not a valid scenario and will return boolean false
• The function will return mixed integer either the position of the $nth occurrence of $needle in $haystack, or Boolean false if it can't be found.

a) Derive positive and negative domain equivalence class portioning with the value in the following format     

$haystack	$needle	$nth	$insensitive

                                                                             
b) And drive test case for weak robust variant in following format and use the variable efficiently and cover  all the paths:
 

Sl.no

$haystack

$needle

$nth

$insensitive

Expected  results

Answer:
NOTE : The above question is for your exercise,kindly try solving it using below reference questions

Question
ABC Transportation Company has implemented an online ticket booking system for their buses, and they have created a simple screen to search the bus and following are some of the business rules they have incorporated in the screen.
From and To location should be minimum 3 characters and maximum  of  25 characters
• Date of travel cannot be lesser than today’s date
• Time : Morning, Afternoon, Night
• No of Passengers can be 1 to 6
• Service class can be: Premium, Deluxe, Express
a) Identify the positive and negative domain.
b) Write test case for weak robust variant.