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, Feb 2006
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).
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.
This booklet is shareware. That means you can (and should) copy it and share it with friends, family, and complete strangers. If you like it, please mail a check to me (Christopher Scaffidi) for $10 or whatever you think the booklet is worth. See instructions to the right.
If you have any questions, please email me at titanium.bits@gmail.com
Errata and comments
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). "--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 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. |
|
