HPSC Data Security 2023 Paper – Assistant Scientist

Q0.

(a) Show that any finite integral domain is a field.

(b) A biased coin with probability of obtaining head equal to p > 0, is tossed repeatedly and independently until the first head is observed. Calculate the probability that the first head appears at an even-numbered toss.

Q0. Show that a connected graph is bipartite if and only if all the cycles are of even length.

Q0.

(a) Design a minimum state DFA for the language L = { w ∈ {0,1}* | w has both an even number of 0's and an even number of 1's }.

(b) State whether the following statements are true or false. Give justifications:
(i) { aⁱ b^j c^k | i < j } ∪ { aⁱ b^j c^k | i < k } is a DCFL (Deterministic Context-Free Language).
(ii) {aⁱ b^j c^k | i < j} ∪ {aⁱ b^j c^k | i < k} is a DCFL (Deterministic Context-Free Language).

Q0. Consider the following NFA. Draw the corresponding transition table for the NFA and then apply subset construction on the same.

Q0. Suppose you are given an array A[1..n] with n entries, with each entry A[i] holding a distinct number. You are told that there is some index p between 1 and n, such that the values in the array entries decrease up to position p in A and then increase the remainder of the way until position n. Show how to find the index p by reading at most O(log n) entries of A.

Q1.

(a) Finance State Dunmai 5 1. Show that any finite integral domain is a field.

(b) A biased coin with probability of obtaining head equal to p > 0, is tossed repeatedly and independently until the first head is observed. Calculate the probability that the first head appears at an even numbered toss.

Q2. (a) Show that a connected graph is bipartite if and only if all the cycles are of even length. 3. Design a minimum state Definite Finite Automata (DFA) for the following language: L = \{ w ∈ \0, \ \mid w \text has both an even number of 0's and an even \} number of 1's

(a) Show that a connected graph is bipartite if and only if all the cycles are of even length. 3. Design a minimum state Definite Finite Automata (DFA) for the following language: L = \{ w ∈ \0, \ \mid w \text has both an even number of 0's and an even \} number of 1's

(b) State whether the following statements are true or false. Give justifications :
(i) \ \ 0. \ aⁱ b^j c^k \mid i < j \ ∪ 1. \ aⁱ b^j c^k \mid i < k \ \text is a DCFL (Deterministic Context- Free Language).
(ii) \a^ib^jc^k\mid i < j\ ∪ \a^ib^jc^k\mid i < k\ is a DCFL (Deterministic Context-Free Language).
4. Consider the following NFA. Draw the corresponding transition table for the NFA and then apply subset construction on the same. 10 0, 1 Figure
1. NFA for the above problem.
5. Suppose you are given an array A[1..n] with n entries, with each entry A[i] holding a distinct number. You are told that there is some index p between 1 and n, such that the values in the array entries decrease up to position p in A and then increase the remainder of the way until position n. Show how to find the index p by reading at most O(log n) entries of A. 10 \boldsymbol2 HPSC/65B

• (a) Show that a connected graph is bipartite if and only if all the cycles are of even length. 3. Design a minimum state Definite Finite Automata (DFA) for the following language: L = \{ w ∈ \0, \ \mid w \text has both an even number of 0's and an even \} number of 1's
• (b) State whether the following statements are true or false. Give justifications :