Data Structure And Algorithm : Practice Questions and Answers

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 has a running time of O(N^2).

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

NP (Non-deterministic Polynomial) is the class of decision problems solvable by non-deterministic polynomial algorithms.

One of the fundamental properties of polynomial functions states that both the sum and composition of two polynomials always result in a polynomial.

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)), where p(n) is a polynomial function of the input size n.

For m=8: total bits = 255, data bits = 247. Rate = 247/255 = 0.969 ≈ 0.97.

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).

The code rate is the second number divided by the first number. For (3, 1), the rate = 1/3.

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

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.

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.

A two-out-of-five code consists of three 0s and two 1s, giving ten possible combinations to represent digits 0–9.

Rate of a hamming code = message length / block length = (2^r - r - 1) / (2^r - 1) = 1 - r/(2^r - 1). It is the highest rate for a minimum distance of 3.

For a Hamming(7, 4) code, the message length k = 2^r - r - 1, where r is the number of parity bits. Here r = 3, so k = 4.

For a Hamming(7, 4) code, the block length n = 2^r - 1, where r is the number of parity bits. Here r = 3, so n = 7.

Richard W. Hamming invented hamming codes at Bell Telephone Laboratory to minimize errors in punched card readers. Huffman invented Huffman codes. Shannon invented Shannon-Fano codes.

Hamming codes are suitable only for single-bit error detection and correction, and two-bit error detection. They are very unlikely to detect burst errors.

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