In the name of ALLAH, the most beneficient, the most merciful

Theory of Computation (CS701)

Subjective, Short Questions from Past Papers

 

Subjective Questions

Question

(Mid Term, Marks = 10, Lesson No. )

CONNECTED = {| is a connected undirected graph}. Give an algorithm that decides this language and show that CONNECTED € P.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

In numbers 561, 2984. Show that these numbers relatively prime or not.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

Is the following statement TRUE or FALSE? Justify your answer. ∀x∀y∃z [ R1(x, y, z) ∨ R1(y, x, z) ∨ R2(x, y) ], where universe is the set of positive integers and R1 = MINUS, that is, MINUS (x, y, z) = TRUE whenever x – y = z, and R2(x, y) = TRUE whenever x = y.

Answer:

Question

(Final Term, Marks = 5, Lesson No. )

Prove that DOUBLE-SAT is NP-Complete by reducing from 3SAT.

Answer:

Question

(Final Term, Marks = 5, Lesson No. )

DOMINATING-SET = {}, show that it is NP-complete by giving a reduction from VERTEX-COVER.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

Show that the set of all positive real numbers has one-to-one correspondence with the set of all real numbers.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

Consider the pair of numbers 64 and 32965. Show that they are relatively prime or not.

Answer:

Question

(Mid Term, Marks = 10, Lesson No. )

In the Silly Post Correspondence Problem (SPCP), the iop string in each pairhas the same length as the bottom string. Show that SPCP is decidable.

Answer:

Question

(Mid Term, Marks = 10, Lesson No. )

Show that some true statements in TH(N, +, x) are not provable.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

Show that the set of all odd integers has one-to-one correspondence with the set of all even integers.

Answer:

Question

(Mid Term, Marks = 5, Lesson No. )

Consider the pair of numbers 234 and 399. Show that they are relatively prime or not.

Answer:

Question

(Mid Term, Marks = 10, Lesson No. )

Show that set of provable statements in TH(N, +, x) is turing recognizable.

Answer: