Preparing for Graduate School Examinations in Computer Science
"Stay away from study guides for the GRE CS sold at Amazon.com by REA and other publishers since they didn't help me and are worthless compared to the Titanium Bits study guide."  user on Urch.com forum
The purpose of this booklet is to help you prepare for the GRE subject test and other general introductorylevel tests related to graduate school in computer science (CS). Download now
This booklet contains several sections. It begins with approximately 100 practice questions on computer science, followed by an answer key and a commentary on each problem. The questions cover hardware systems, software systems, algorithms & data structures, and the mathematics & theory of CS. The booklet closes with a list of supplementary resources that you should definitely check out.
Please note that these questions are not taken from any GRE subject test or other particular real computer science test, nor are they intended to "give away" what will be on the actual exam. Who can predict the exact questions that will appear on your test? My hope is that this booklet will help you assess yourself in order to decide where to invest your time.
If you have any questions, please email me at titanium.bits@gmail.com I still check this email address regularly (as of late2012), but not every day.
Errata and comments
Regarding question 97:
Oops. There are two correct answers:
B. Grammar G2 is ambiguous (it's not ambiguous, for the reasons given in the commentary)
E. Grammar G2 is in Chomsky Normal Form (it's not, as the start symbol, S, appears on the righthand side of a rule)
Grammar G2 almost perfectly fits the definition for Chomsky Normal Form given by Sipser and listed on Wikipedia (http://en.wikipedia.org/wiki/Chomsky_normal_form), except that the start symbol may not appear on the righthand side of a rule, as it does in the first rule listed in the grammar.
Thanks to Josh for the comments above. Regarding question 3:
Three people have written to me saying that a barrel shifter isn't sequential and that it is combinational. This isn't a very wellwritten question, I have decided. The important thing that you should learn for the exam is the distinction between sequential and nonsequential circuits. If you have that down, then you should do just fine. Thanks to Leonid, Sky, and Andrew for your feedback!
Question 52 should read:
The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r 2 [2,N), bits[r] is supposed to equal 1 if and only if r is composite. Assume that the bits array is initialized to all zeroes.
Thanks to Yuri Niyazov for pointing this out.
Regarding question 10, choice B:
B. In twolevel caches, the L2 cache is generally physically located on the same chip as the CPU. A reader writes, "While this was indeed untrue up to even a few years ago, it's no longer the case, especially in the multicore era. Take a look at the Nehalem floorplan; each core enjoys an ondie L1+L2, and even the gigantic 8MB L3 cache sits ondie. This is reflected in the minimum latencies for a cache hit at each level (5, 10, and 35 cycles  see the Intel Optimization Guide for Intel64 and IA32 Architectures, Nehalem section); these grow roughly with the size of the caches. You might want to update this question (it was still obvious that the answer desired was E, since B only changed fairly recently for COTS hardware). "rigorously, nick" Thanks, Nick!
Jie says: 'Your booklet is great! But, I think in your GRE CS practice booklet, question 54, the code is used to multiply B and A and store the result in the matrix C, not “multiply A and B”, since the commutative law doesn’t exist in matrix world.'
Yeah, I should have written "multiply B and A" rather than "multiply A and B".
By the way, folks, I am told that linear algebra is no longer on the GRE (though I haven't taken the exam lately and so can't verify that they really and truly did remove all traces of linear algebra from the exam). But if you're using this booklet to prepare for the CS GRE, you might not need to worry so much about matrix stuff. Personally, though, I think every CS grad student ought to know a little bit about the material covered by this question, since it's really about algorithms and complexity rather than linear algebra.
Regarding question 4: It's odd, a lot of people write to me about that question. There is no erratum.
The reason why E is wrong is because a valid Gray code also has to "wrap around". If you choose E, then successive incrementation results in this sequence:
000,100,101,001,011,010,110,111, 000,100,101,001,011,010,110,111, 000,100,101,001,011,010,110,111, ...
If you look closely, you'll see that when you go from 111 to 000, three bits flip. That's a nono.
In contrast, C is correct because it gives you the following sequence:
000,100,101,001,011,111,110,010, 000,100,101,001,011,111,110,010, 000,100,101,001,011,111,110,010, ...
Now, each increment (including the "wrap around") only flips one bit.
I hope that helps.

