ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
Which of the following problems is not NP-complete?
Hamiltonian circuit
Bin packing
Partition problem
Halting problem
Hamiltonian circuit, bin packing, and partition problems are NP-complete. The Halting problem is undecidable — it cannot be solved by any algorithm at all.
How many steps are required to prove that a decision problem is NP-complete?
1
2
3
4
Two steps: first, show the problem is in NP; second, prove that every NP problem is polynomially reducible to it.
To which of the following class does a CNF-satisfiability problem belong?
NP class
P class
NP complete
NP hard
The CNF satisfiability problem belongs to the NP-complete class. It deals with Boolean expressions in conjunctive normal form.
How many conditions have to be met if an NP-complete problem is polynomially reducible?
1
2
3
4
Two conditions must be met: a function t that maps all yes-instances of decision problems D1 to D2, and t must be computable in polynomial time.
A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.
True
False
A non-deterministic algorithm is classified as NP if its verification stage runs in polynomial time.
How many stages of procedure does a non-deterministic algorithm consist of?
1
2
3
4
A non-deterministic algorithm is a two-stage procedure: a guessing stage and a verification stage.
Halting problem is an example for?
Decidable problem
Undecidable problem
Complete problem
Tractable problem
The Halting problem, proved by Alan Turing, cannot be solved by any algorithm and is therefore undecidable.
To which class does the Euler's circuit problem belong?
P class
NP class
Partition class
Complete class
Euler's circuit problem can be solved in polynomial time O(N^2), so it belongs to the P class.
The Euler's circuit problem can be solved in?
O(N)
O(N log N)
O(log N)
O(N^2)
The Euler's circuit problem has a running time of O(N^2).
Problems that cannot be solved by any algorithm are called?
Tractable problems
Intractable problems
Undecidable problems
Decidable problems
Problems that cannot be solved by any algorithm are called undecidable problems. Problems solvable in polynomial time are called tractable.
________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.
NP
P
Hard
Complete
NP (Non-deterministic Polynomial) is the class of decision problems solvable by non-deterministic polynomial algorithms.
The sum and composition of two polynomials are always polynomials.
True
False
One of the fundamental properties of polynomial functions states that both the sum and composition of two polynomials always result in a polynomial.
Problems that can be solved in polynomial time are known as?
Intractable
Tractable
Decision
Complete
Problems solvable in polynomial time are called tractable. Problems that cannot be solved in polynomial time are called intractable.
The worst-case efficiency of solving a problem in polynomial time is?
O(p(n))
O(p(n log n))
O(p(n^2))
O(p(m log n))
The worst-case efficiency of solving a problem in polynomial time is O(p(n)), where p(n) is a polynomial function of the input size n.
What is the rate of the hamming code of parity bit m=8?
0.94
0.92
0.90
0.97
For m=8: total bits = 255, data bits = 247. Rate = 247/255 = 0.969 ≈ 0.97.
For a hamming code of parity bit m=8, what is the total bits and data bits?
(255, 247)
(127, 119)
(31, 26)
(0, 8)
Total bits = 2^m - 1 = 2^8 - 1 = 255. Data bits = 2^m - m - 1 = 256 - 8 - 1 = 247. So the answer is (255, 247).
What is the code rate of a repetition Hamming code (3, 1)?
1
3
1/3
1.3
The code rate is the second number divided by the first number. For (3, 1), the rate = 1/3.
An Extended Hamming code is also called as:
SEDDEC
SEDDED
SECDED
SECDEC
An Extended Hamming code is called SECDED (Single Error Correction Double Error Detection). The most popular codes are (72, 64) and (127, 120).
________ is the mechanism of sending data bits multiple times to ensure consistency.
Repetition
Duplication
Mirroring
Redundancy
Repetition involves sending the same data bits multiple times. For example, with n=3 repetition, a bit '1' is sent as '111'. If the received bits differ, an error has occurred.
Including a parity bit along with the data surely detects all errors.
True
False
If an error occurs in the data string, parity changes to indicate it. However, if the error occurs in the parity bit itself, the error goes undetected.
