# Checksum Complexity Classes And NP Complete Problems MCQ

1. The most common hamming codes are a generalized version of?

a) Hamming(7, 4) code

b) Hamming(8, 4) code

c) Hamming(6, 3) code

d) Hamming(5, 7) code

Answer: a

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.

2. What is the minimal Hamming distance between any two correct codewords?

a) 1

b) 2

c) 3

d) 4

Answer: c

The minimal Hamming distance between any two correct codewords is 3.

Since we use a generalized version of Hamming(7, 4) code, the minimal hamming distance is 3. It cannot correct burst errors.

3. Why do we require hamming codes?

a) Error correction

b) Encryption only

c) Decryption

d) Bit stuffing

Answer: a

Hamming codes are used for error detection and correction. It is also used for channel encoding and decoding. They are linear-error correcting codes.

4. Hamming bits are suitable only for single-bit error detection and correction and two-bit error detection.

a) True

b) False

Answer: a

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.

5. Who invented Hamming codes?

a) Richard Hamming

b) Ross Hamming

c) Shannon

d) Huffman

Answer: a

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.

6. What is the total block length ‘n’ of a Hamming code?

a) 2^{r}

b) 2^{r}-1

c) 2^{r-1}-1

d) 2^{r}+1

Answer: b

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.

7. What is the message length ‘k’ of a Hamming(7,4) code?

a) 2^{r}-1

b) 2^{r}-r+1

c) 2^{r}-r-1

d) 2^{r+1}-r

Answer.c

Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7,4) code, the message length ‘k’ is 2^{r}-r-1

where r is the parity bit. Here, r=3.

8. What is the rate of hamming codes?

a) 1-[r/(2^{r}-1)]

b) 1-(r/2^{r})

c) 1+(r/2^{r})

d) r/2^{r}+1

Answer: a

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.

9. A two-out-of-five code consists of _________

a) Two 0s and three 1s

b) Three 0s and two 1s

c) Four 0s and one 1s

d) One 0s and four 1s

Answer: b

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.

10. Including a parity bit along with the data surely detects the errors.

a) true

b) false

Answer: b

If an error has occurred in a data string, parity will change in order to indicate errors. However, if the error occurs in the parity bit, the error goes undetected.

11. ________ is the mechanism of sending data bits multiple times to ensure consistency.

a) Repetition

b) Duplication

c) Mirroring

d) Redundancy

Answer: a

Repeating data bits multiple times is done to ensure consistency. If the data bit to be sent is a 1, an n=3 repetition code will send 111. If the bits are not the same, an error has occurred.

12. An Extended hamming code is also called as __________

a) SEDDEC

b) SEDDED

c) SECDED

d) SECDEC

Answer: c

An Extended Hamming code is also called as SECDED (Single Error Correction Double Error Detection). The most popular codes are (72, 64) code and (127,120) code.

13. What is the code rate of a repetition of Hamming code (3, 1)?

a) 1

b) 3

c) 1/3

d) 1.3

Answer: c

The code rate of a repetition hamming code is the second number divided by the first number. Here, it is 1/3.

14. For a hamming code of parity bit m=8, what are the total bits and data bits?

a) (255, 247)

b) (127, 119)

c) (31, 26)

d) (0, 8)

Answer: a

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.

15. What is the rate of the hamming code of parity bit m=8?

a) 0.94

b) 0.92

c) 0.90

d) 0.97

Answer. d

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.

1. The worst-case efficiency of solving a problem in polynomial time is?

a) O(p(n))

b) O(p( n log n))

c) O(p(n2))

d) O(p(m log n))

Answer: a

The worst-case efficiency of solving a problem in polynomial time is O(p(n)) where p(n) is the polynomial time of input size.

2. Problems that can be solved in polynomial time are known as?

a) intractable

b) tractable

c) decision

d) complete

Answer: b

Problems that can be solved in polynomial time are known as tractable. Problems that cannot be solved in polynomial time are intractable.

3. The sum and composition of two polynomials are always polynomials.

a) true

b) false

Answer: a

One of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials.

4. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.

a) NP

b) P

c) Hard

d) Complete

Answer: a

NP problems are called non-deterministic polynomial problems. They are a class of decision problems that can be solved using NP algorithms.

5. Problems that cannot be solved by any algorithm are called?

a) tractable problems

b) intractable problems

c) undecidable problems

d) decidable problems

Answer: c

Problems that cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.

6. The Euler’s circuit problem can be solved in?

a) O(N)

b) O( N log N)

c) O(log N)

d) O(N^{2})

Answer: d

Mathematically, the run time of Euler’s circuit problem is determined to be O(N^{2}).

7. To which class does the Euler’s circuit problem belong?

a) P class

b) NP class

c) Partition class

d) Complete class

Answer: a

Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex.

The Euler’s circuit problem belongs to the P class. Euler’s circuit problem can be solved in polynomial time. It can be solved in O(N^{2}).

8. Halting problem is an example for?

a) decidable problem

b) undecidable problem

c) complete problem

d) trackable problem

Answer: b

The halting problem, commonly applied to Turing-complete programs and models, is the problem of finding out whether, with the given input, a program will halt at some time or continue to run indefinitely.

The halting problem by Alan Turing cannot be solved by any algorithm. Hence, it is undecidable.

9. How many stages of procedure does a non-deterministic algorithm consist of?

a) 1

b) 2

c) 3

d) 4

Answer: b

A non-deterministic algorithm is a two-stage procedure- the guessing stage and the verification stage.

10. A non-deterministic algorithm is said to be a non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.

a) true

b) false

Answer: a

One of the properties of NP class problems states that A non-deterministic algorithm is said to be a non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.

11. How many conditions have to be met if an NP-complete problem is polynomially reducible?

a) 1

b) 2

c) 3

d) 4

Answer: b

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.

12. To which of the following class does a CNF-satisfiability problem belong?

a) NP class

b) P class

c) NP-complete

d) NP-hard

Answer: c

The CNF satisfiability problem belongs to the NP-complete class. It deals with Boolean expressions.

The CNF-satisfiability problem is a version of the Boolean satisfiability problem, where the Boolean formula is specified in the conjunctive normal form (CNF), i.e., a conjunction of clauses, where each clause is a disjunction of literals, and a literal is a variable or its negation.

13. How many steps are required to prove that a decision problem is NP-complete?

a) 1

b) 2

c) 3

d) 4

Answer: b

2 steps are required to prove that a decision problem is NP-complete.

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.

14. Which of the following problems is not NP-complete?

a) Hamiltonian circuit

b) Bin packing

c) Partition problem

d) Halting problem

Answer: d

Hamiltonian circuit, bin packing, and partition problems are NP-complete problems. The halting problem is an undecidable problem.

15. The choice of the polynomial class has led to the development of an extensive theory called ________

a) computational complexity

b) time complexity

c) problem complexity

d) decision complexity

Answer: a

The choice of the polynomial class has led to the development of an extensive theory called computational complexity.

An extensive theory called computational complexity seeks to classify problems according to their inherent difficulty.

1. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?

a) branch and bound

b) iterative improvement

c) divide and conquer

d) greedy algorithm

Answer: a

The Hamiltonian path problem can be solved efficiently using the branch and bound approach. It can also be solved using a backtracking approach.

2. The problem of finding a path in a graph that visits every vertex exactly once is called?

a) Hamiltonian path problem

b) Hamiltonian cycle problem

c) Subset sum problem

d) Turnpike reconstruction problem

Answer: a

The Hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas the Hamiltonian cycle problem is finding a cycle in a graph.

3. Hamiltonian path problem is _________

a) NP problem

b) N class problem

c) P class problem

d) NP-complete problem

Answer: d

- Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once.
- Hamiltonian path problem is found to be NP-complete. Hamiltonian cycle problem is also an NP-complete problem.

4. There is an existing relationship between a Hamiltonian path problem and a Hamiltonian circuit problem.

a) true

b) false

Answer: a

There is a relationship between the Hamiltonian path problem and the Hamiltonian circuit problem. The Hamiltonian path in graph G is equal to the Hamiltonian cycle in graph H under certain conditions.

5. Which of the following problems is similar to that of a Hamiltonian path problem?

a) knapsack problem

b) closest pair problem

c) traveling salesman problem

d) assignment problem

Answer: c

Hamiltonian path problem is similar to that of a traveling salesman problem since both the problem traverses all the nodes in a graph exactly once.

6. Who formulated the first-ever algorithm for solving the Hamiltonian path problem?

a) Martello

b) Monte Carlo

c) Leonard

d) Bellman

Answer: a

The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.

7. At what time can the Hamiltonian path problem can be solved using dynamic programming?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(N^{2} 2N)

Answer: d

Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N^{2} 2N).

8. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.

a) true

b) false

Answer: a

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.

9. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?

a) Karp

b) Leonard Adleman

c) Andreas Bjorklund

d) Martello

Answer: c

Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of the number of Hamiltonian cycles.

10. For a graph of degree three, at what time can a Hamiltonian path be found?

a) O(0.251n)

b) O(0.401n)

c) O(0.167n)

d) O(0.151n)

Answer: a

For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251n).

11. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?

a) O(N!)

b) O(N! * N)

c) O(log N)

d) O(N)

Answer: b

For a graph having N vertices traverse the permutations in N! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).

12. How many Hamiltonian paths does the following graph have?

a) 1

b) 2

c) 3

d) 4

Answer: a

The above graph has only one Hamiltonian path that is from a-b-c-d-e.

13. How many Hamiltonian paths does the following graph have?

a) 1

b) 2

c) 0

d) 3

Answer: c

The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.

1. Under what condition any set A will be a subset of B?

a) if all elements of set B are also present in set A

b) if all elements of set A are also present in set B

c) if A contains more elements than B

d) if B contains more elements than A

Answer: b

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.

2. What is a subset sum problem?

a) finding a subset of a set that has sum of elements equal to a given number

b) checking for the presence of a subset that has a sum of elements equal to a given number and printing true or false based on the result

c) finding the sum of elements present in a set

d) finding the sum of all the subsets of a set

Answer: b

In the subset sum problem check for the presence of a subset that has a sum of elements equal to a given number. If such a subset is present then we print true otherwise false.

3. Which of the following is true about the time complexity of the recursive solution of the subset sum problem?

a) It has an exponential time complexity

b) It has a linear time complexity

c) It has a logarithmic time complexity

d) it has a time complexity of O(n^{2})

Answer: a

The subset sum problem has both recursive as well as dynamic programming solutions. The recursive solution has an exponential time complexity as it will require checking for all subsets in the worst case.

4. What is the worst-case time complexity of the dynamic programming solution of the subset sum problem(sum=given subset-sum)?

a) O(n)

b) O(sum)

c) O(n2)

d) O(sum*n)

Answer: d

The subset sum problem has both recursive as well as dynamic programming solutions.

The dynamic programming solution has a time complexity of O(n*sum) as it is a nested loop with limits from 1 to n and 1 to sum respectively.

5. Subset sum problem is an example of an NP-complete problem.

a) true

b) false

Answer: a

The subset sum problem takes exponential time when we implement a recursive solution. Subset sum problem is known to be a part of NP-complete problems.

6. Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.

a) true

b) false

Answer: b

The recursive solution to the subset sum problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. So dynamic programming solution is faster in terms of time complexity.

7. Which of the following is not true about the subset sum problem?

a) the recursive solution has a time complexity of O(2n)

b) there is no known solution that takes polynomial time

c) the recursive solution is slower than the dynamic programming solution

d) the dynamic programming solution has a time complexity of O(n log n)

Answer: d

The recursive solution of the subset sum problem is slower than the dynamic problem solution in terms of time complexity. A dynamic programming solution has a time complexity of O(n*sum).

1. What is meant by the power set of a set?

a) subset of all sets

b) set of all subsets

c) set of particular subsets

d) an empty set

Answer: b

The 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}}.

2. What is the set partition problem?

a) finding a subset of a set that has sum of elements equal to a given number

b) checking for the presence of a subset that has a sum of elements equal to a given number

c) checking whether the set can be divided into two subsets with an equal sum of elements and printing true or false based on the result

d) finding subsets with an equal sum of elements

Answer: c

In the 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.

3. Which of the following is true about the time complexity of the recursive solution of the set partition problem?

a) It has an exponential time complexity

b) It has a linear time complexity

c) It has a logarithmic time complexity

d) it has a time complexity of O(n2)

Answer: a

Set partition problem has both recursive as well as dynamic programming solutions. The recursive solution has an exponential time complexity as it will require checking for all subsets in the worst case.

4. What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

a) O(n)

b) O(sum)

c) O(n2)

d) O(sum*n)

Answer: d

Set partition problem has both recursive as well as dynamic programming solutions. The dynamic programming solution has a time complexity of O(n*sum) as it is a nested loop with limits from 1 to n and 1 to sum respectively.

5. Set partition problem is an example of an NP-complete problem.

a) true

b) false

Answer: a

Set partition problem takes exponential time when we implement a recursive solution. The set partition problem is known to be a part of NP-complete problems.

6. Recursive solution of the Set partition problem is faster than the dynamic problem solution in terms of time complexity.

a) true

b) false

Answer: b

The recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. So dynamic programming solution is faster in terms of time complexity.

7. Which of the following is not true about the set partition problem?

a) the recursive solution has a time complexity of O(2n)

b) there is no known solution that takes polynomial time

c) the recursive solution is slower than the dynamic programming solution

d) the dynamic programming solution has a time complexity of O(n log n)

Answer: d

The recursive solution of the set partition problem is slower than the dynamic problem solution in terms of time complexity. A dynamic programming solution has a time complexity of O(n*sum).

11. What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

a) O(n log n)

b) O(n^{2})

c) O(2n)

d) O(sum*n)

Answer: d

The auxiliary space complexity of the set partition problem is required in order to store the partition table. It takes up a space of n*sum, so its auxiliary space requirement becomes O(n*sum).