neikel

There are two circuits C and D, consisting of only AND, OR, and NOT. Each circuit has n inputs, and a single output. Suppose that P=NP, which of the following can be computed in polynomial time: I. The equivalence of C and D. II. Whether there exist a smaller circuit than C that is equivalent to C. III. Whether there exist an input to C which returns 1. (A) I (B) II © II and III (D) I, II, and III (E) None of the above Which is your choice ?

Of the following statements about separate compilation, which is LEAST accurate? (A) It decrease the expected length of the edit-compile-run cycle by reducing the fraction of the program that must be recompile after a given change. (B) It facilitates code reuse by allowing functions to be incorporated in more than one program without source-level modifications. © Its benefits are reduced when external procedures are made into inline procedures. (D) It provides an encapsulation mechanism for languages such as C that lack o built-in module facility (E) It makes it easier for a compiler to perform global optimizations Please give your answer :)

Just one of practice questions for GRE Subject test I have collected from Google.

Yes, I also have the same answer. But there is no official answer for this. I want to check for sure if I have the right choice, thanks.

If a recursive, depth-first search is used on a completed undirected graph with n vertexes, the maximum depth of the recursion is (A) Θ(1) (B)Θ(log(n)) ©Θ(rootsquareof (n) ) (D)Θ(n) (E) Θ(n^2) Let's give your answers mates ;)

I don't know how much is your ability however it would take you a bit more time than few months :) if you never taken any CS courses before. Maybe CalmLogic could tell you more exactly about the time he took before the test because he also was not a CS student. http://www.www.urch.com/forums/gre-computer-science/62746-advice-needed-gre-cs-prep-test-april-14-2007-a.html#post411230 Please check some suggested materials in this forum and you could have your best answer yourself. Good lucks.

Filling the answers quick and not careful and those missing answers weren't counted ?

Hi, there ! I think that A is the right answer because x = x*x is equal to the growing x^(2^k) for example: first round k = 1 we have x^(2^1) = x^2 k = 2 we have x = x*x= (x^2)*(x^2) = x^4 = x^(2^k) [k=2] k = 3 we have x = x*x= (x^4)*(x^4) = x^8 = x^(2^k) [k=3] and so on then for f(k) > n (x = 2 > 1) it means that x^(2^k) > n => 2^k > log2(n) => k > log2(log2(n)) So I think A is the right answer.

Thank you, Ali This article boost me so much.