Problem-Solving

Question 1

Suppose we have a function HALTS which when applied to any arbitrary function f and its arguments will say TRUE if function f terminates for those arguments and FALSE otherwise. Example, Given the following function definition.
FACTORIAL (N) = IF(N=0) THEN 1 ELSE N*FACTORIAL (N-1)
Then HALTS(FACTORIAL 4) = TRUE and HATS(FACTORIAL - 5) = FALSE

Let us define the function FUNNY(f) = IF HALTS(ff) THEN not(ff) ELSE TRUE
(a) Show that FUNNY terminates for all functions f.
(b) Use (a) to prove (by contradiction) that it is not possible to have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.

A
Theory Explanation.
Question 2
In the land of Twitter, there are two kinds of people: knights (also called outragers), who always tell the truth, and knaves (also called trolls), who always lie. It so happened that a person with handle @anand tweeted something offensive. It was not known whether @anand was a knight or a knave. A crack team, headed by Inspector Chitra, rounded up three suspects and interrogated them.
The first interrogation went as follows.
Chitra : What do you know about @anand?
Suspect 1 : @anand once claimed that I was a knave.
Chitra : Are you by any chance @anand?
Suspect 1 : Yes.
The second interrogation:
Chitra : Have you ever claimed you were @anand?
Suspect 2 : No.
Chitra : Did you ever claim you are not @anand?
Suspect 2 : Yes.
The third suspect arrived with a defense lawyer (also on Twitter):
Lawyer : My client is indeed a knave, but he is not @anand.
Suspect 3 : My lawyer always tells the truth.
Which of the above suspects are innocent, and which are guilty?
Explain your reasoning.
A
Description Explanation
Question 2 Explanation: 
If Suspect 1 were Anand, then since he answers truthfully to the second question, he is a knight, but then his first reply means that he once claimed he was a knave, which knights will not do. Hence Suspect 1 is not Anand.
If Suspect 2 were Anand, then he is either a knight or a knave. If he were a knight, then the answer to question 2 means he claimed he was not Anand, which is a lie. Hence he is a knave. But then the answer to question 1 is a lie, which means he has once claimed he is Anand, which a liar will not do. This contradiction means that he is not Anand.
Now Suspect 3 cannot be a knight, since he says his lawyer is truthful, and the lawyer says that he is a knave. So Suspect 3 is a knave. And so what he said is false, and his lawyer is a knave. But then the lawyer has uttered a falsehood. Of the conjuction he uttered, at least one conjunct is false. But the first conjunct is true, so the second is false. And Suspect 3 is indeed Anand!
Question 3
Consider the following algorithm for computing the factorial of a positive integer n, specified in binary: ,br> prod ← 1 ,
for i from 1 to n
prod ← prod × i
output prod
Assume that the number of bit operations required to multiply a k-bit positive integer with an ℓ-bit positive integer is at least Ω(k+l) and at most O(kl). Then, the number of bit operations required by this algorithm is
A
O(n)
B
O(n log n) but ω(n)
C
O(n2) but ω(n log n)
D
O(n3) but ω(n 2
E
None of the above
There are 3 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access