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 introductory-level 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 firstname.lastname@example.org
I still check this email address regularly (as of late-2012), 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 right-hand 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 right-hand 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 well-written question, I have decided. The important thing that you should learn for the exam is the distinction between sequential and non-sequential 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 two-level 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 on-die L1+L2, and even the gigantic 8MB L3 cache sits on-die. 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 Intel-64
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).
'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 no-no.
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.
Materials to help you efficiently practice for the Computer Science GRE, and for other introductory exams...
As of Nov 21, 2012, paying $10 is optional. The reason is that yesterday, my university had an online training seminar about "Conflict of Interest". Basically, they're worried that if I make significant money outside the university, then I might be tempted to do bad things to the university. (Yes, seriously.)
There was one sentence in the training materials that a "significant financial interest" would include "Intellectual property rights and interests upon receipt of income related to such rights or interests." I don't know whether this booklet counts, but it seems close enough to intellectual property "rights" and "income" that I'm not sure.
Unfortunately, getting a straight answer out of university bureaucracy is usually slow and painful. Plus, once a "Conflict of Interest" is disclosed, then the conflict needs to be "managed" by a committee or university representative forever. Aargh.
Bottom line: If you want to give me $10, consider it a GIFT because you're a nice person, not a payment, because sending money is not required.
As always, I wish you the best of luck in your studies.
or by sending $10 via Paypal: