Explore topic-wise InterviewSolutions in .

Right choice is (d) O(sum*n)

To explain: Set partition problem has both recursive as WELL as dynamic PROGRAMMING SOLUTION. The dynamic programming solution has a time complexity of O(n*sum) as it as a NESTED loop with limits from 1 to n and 1 to sum RESPECTIVELY.

The CORRECT choice is (a) It has an EXPONENTIAL time complexity

The explanation is: Set partition PROBLEM has both recursive as WELL as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in the WORST case.

The correct option is (c) checking whether the set can be DIVIDED into two SUBSETS of with equal sum of elements and printing true or false based on the result

Explanation: In set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each SUBSET is equal. If such subsets are present then we print true OTHERWISE false.

The correct ANSWER is (B) set of all subsets

Easiest explanation - Power set of a set is defined as the set of all subsets. Ex- if there is a set S={1,3} then power set of set S will be P={{},{1},{3}{1,3}}.

The correct option is (b) checking for the presence of a subset that has sum of elements equal to a given number and printing TRUE or false based on the result

Best EXPLANATION: In subset sum problem CHECK for the presence of a subset that has sum of elements equal to a given number. If such a subset is PRESENT then we print true otherwise false.

Right OPTION is (b) if all elements of SET A are also present in set B

Easy EXPLANATION - Any set A will be called a subset of set B if all elements of set A are also present in set B. So in such a case set A will be a PART of set B.

The correct OPTION is (c) 0

The BEST I can explain: The above graph has no Hamiltonian PATHS. That is, we cannot traverse the graph with meeting VERTICES EXACTLY once.

The correct CHOICE is (a) 1

Explanation: The above GRAPH has only ONE Hamiltonian PATH that is from a-b-c-d-e.

The correct answer is (a) O(0.251^n)

Easy explanation - For a GRAPH of maximum degree THREE, a HAMILTONIAN path can be FOUND in TIME O(0.251^n).

Correct option is (c) Andreas Bjorklund

The BEST I can explain: Andreas Bjorklund CAME up with the inclusion-exclusion PRINCIPLE to reduce the counting of number of HAMILTONIAN CYCLES.

Right option is (a) true

Explanation: According to a handshaking lemma, in graphs, in which all VERTICES have an ODD DEGREE, the number of Hamiltonian CYCLES through any fixed edge is ALWAYS even.

Correct option is (d) O(N^2 2^N)

The best explanation: USING DYNAMIC programming, the TIME taken to solve the Hamiltonian path PROBLEM is mathematically FOUND to be O(N^2 2^N).

The correct choice is (a) Martello

For EXPLANATION: The FIRST EVER problem to solve the HAMILTONIAN path was the enumerative algorithm formulated by Martello.

Right CHOICE is (b) false

Easy explanation - There is a relationship between HAMILTONIAN PATH PROBLEM and Hamiltonian circuit problem. The Hamiltonian path in graph G is EQUAL to Hamiltonian cycle in graph H under certain conditions.

Correct answer is (a) branch and BOUND

For EXPLANATION: The Hamiltonian path problem can be SOLVED EFFICIENTLY USING branch and bound approach. It can also be solved using a backtracking approach.

Right CHOICE is (a) computational complexity

Easiest explanation - An extensive theory called computational complexity seeks to CLASSIFY problems according to their INHERENT difficulty.

The correct CHOICE is (d) HALTING problem

Easy EXPLANATION - HAMILTONIAN CIRCUIT, bin packing, partition problems are NP complete problems. Halting problem is an undecidable problem.

Right OPTION is (b) 2

Easiest EXPLANATION - FIRST, the problem should be NP. Next, it should be PROVED that every problem in NP is reducible to the problem in question in polynomial time.

Correct choice is (c) NP complete

The best EXPLANATION: The CNF SATISFIABILITY PROBLEM belongs to NP complete class. It deals with BOOLEAN expressions.

The correct choice is (b) 2

To explain: A function t that maps all yes INSTANCES of decision problems D1 and D2 and t should be COMPUTED in polynomial time are the TWO conditions.

The correct choice is (a) true

Easy explanation - One of the PROPERTIES of NP class problems STATES that A non-deterministic algorithm is said to be non-deterministic POLYNOMIAL if the time-efficiency of its verification STAGE is polynomial.

Correct option is (B) 2

The best I can explain: A non-deterministic ALGORITHM is a two-STAGE procedure- guessing stage and VERIFICATION stage.

Correct OPTION is (b) UNDECIDABLE problem

Easiest explanation - HALTING problem by Alan Turing cannot be solved by any ALGORITHM. HENCE, it is undecidable.

The correct CHOICE is (d) O(N^2)

Easiest explanation - Mathematically, the run time of EULER’s circuit PROBLEM is DETERMINED to be O(N^2).

Right ANSWER is (C) UNDECIDABLE problems

The explanation is: Problems cannot be solved by any ALGORITHM are called undecidable problems. Problems that can be solved in polynomial TIME are called Tractable problems.

Right answer is (a) NP

The BEST I can explain: NPproblems are CALLED as non-deterministic polynomial problems. They are a class of DECISION problems that can be SOLVED using NP ALGORITHMS.

Correct option is (a) true

The best EXPLANATION: ONE of the properties of POLYNOMIAL FUNCTIONS states that the sum and composition of two polynomials are always polynomials.

The correct answer is (b) tractable

The best I can explain: Problems that can be SOLVED in POLYNOMIAL TIME are known as tractable. Problems that cannot be solved in polynomial time are INTRACTABLE.

The CORRECT choice is (d) 0.97

Explanation: For a hamming code of PARITY BIT 8, total BITS = 255 and data bits = 247. Rate= data bits/ total bits

= 247/255 = 0.969 = 0.97.

The correct OPTION is (a) (255, 247)

EXPLANATION: Total BITS are COMPUTED as, 2^m-1 = 2^8-1 =255.

Data bits are computed as 2^m-m-1= 2^8-8-1= 247.

Right choice is (C) 1/3

Easy explanation - The CODE rate of a REPETITION hamming code is the second number divided by the first number. Here, it is 1/3.

Correct option is (a) REPETITION

The best I can EXPLAIN: Repeating data BITS multiple times is done to ensure consistency. If the data bit to be sent is a 1, a n=3 repetition code will send 111. If the bits are not the same, an ERROR has occurred.

Correct ANSWER is (B) false

The explanation is: If error has occurred in a DATA string, PARITY will change inorder to indicate errors. However, if the error occurs in parity bit, the error goes undetected.

The correct option is (B) Three 0S and two 1s

Best explanation: A two-out-of-five code consists of three 0s and two 1s. Hence, it contains TEN POSSIBLE combinations to represent DIGITS from 0-9.

Correct option is (a) 1-[r/(2^r-1)]

The best explanation: Rate of a hamming code is message length divided by BLOCK length (i.e.) 2^r-r-1/2^r-1 = 1-[r/(2^r-1)]. It is the HIGHEST rate for a minimum distance of THREE.

Correct option is (B) 2^R-1

The best I can explain: Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7, 4) CODE, the BLOCK length ‘n’ is 2^r-1 where r is the parity bit. Here, r=3.

Right choice is (a) RICHARD Hamming

The best explanation: Richard W. Hamming invented hamming CODES in BELL TELEPHONE Laboratory to minimize the errors in punched CARD readers. Huffman invented huffman codes. Shannon invented Shannon-Fanno codes.

Right answer is (b) False

For EXPLANATION: Hamming BITS are suitable only for single-bit error DETECTION and correction and two bit error detection. It is very unlikely to detect BURST ERRORS.

The correct option is (a) ERROR correction

The EXPLANATION is: HAMMING codes are used for the purpose of error detection and correction. It is also used for channel ENCODING and decoding. They are linear-error correcting codes.

The CORRECT option is (C) 3

To explain: Since we use a generalized version of HAMMING(7, 4) code, the minimal hamming distance is 3. It cannot correct BURST errors.

The CORRECT choice is (a) HAMMING(7, 4) code

To explain: The most COMMON hamming codes generalize to form hamming(7, 4) code. It ENCODES four bits of data into seven bits by adding three parity bits.