m0pilot

Hi everyone, I'm taking the Subject Test in April and I was wondering if I could ask those of you who recently took it a few quick questions? I am somewhat concerned about the test contents as I'm not a CS undergrad major and I'm finding it difficult to prepare for the test above a certain level. Now there is obviously a certain pool of "standard" topics that seem to be asked frequently and are covered extensively on this forum, the Titanium Bits guide and other places online. Things like caches & memory, algorithmic complexity, RISC pipeline etc. I'm not particularly worried about these as they are well-documented and with a bit of reading (Cormen et al for algorithms, Pattterson & Hennesy for hardware, Tanenbaum for OS) it's fairly straightforward to get a grasp on these topics even without a CS background, and it seems fairly obvious what the "important" points are. However, there is also a lot of stuff in the syllabus that is less clearly defined, and I have little to no idea where to start for these things. Case in point: Everything under "Software Engineering" in the ETS booklet - I have no idea where to even start there, beyond reading the handful of obvious Wikipedia pages on the subject. Similarly, a few people have said that the exam covered some algorithms they did not expect to encounter there - Beyond the handful of algorithms covered in Cormen et al (i.e. the most important sorting and graph algorithms), I have no clue as to what to even look at for the exam. "Other topics" is, of course, similarly difficult to judge for me. Other than a question on RSA in the ETS booklet, I have no idea what that might cover. Besides, the ETS booklet seems to be a bit dated by now too, and I have no idea how current the selection of topics is. So I was wondering if those of you who have recently taken would care to share their experience? I know that specific questions are off-limits, but even some vague pointers in the right directions would be very much appreciated. I have been studying for the test for a while now, and I am finding it increasingly frustrating as at this point, I have little trouble understanding any of the material I've looked at, but rather, I have no idea what else to look at. In any case good luck for all of you currently waiting for your scores, as well as with your applications of course! Many thanks in advance for any advice you can give me, m0

Hi bags, for the Farthest Neighbors, simply go through the array in order and keep track of the largest and smallest values so far encountered (this can be done using operation 1 and takes linear time in each step). Once you're done you have the largest and smallest number in the array, which are by definition the farthest away from one another. Clearly this can be done in O(n) time. For the nearest neighbor, the solution is similar, except you have to sort the array first - this can be done on O(n log n) time with the operations provided using e.g. heapsort. Then like before you go through the array in order, and keep track of the shortest distance between any two adjacent nodes. Again this will take O(n) time. So in total you need O((n log n) + n) = O(n log n) time. You could now check that indeed no algorithm could do better than that - but these are already the smallest value given, so you can skip that step - assuming that the answers given include the correct one, it has to be (A). (And indeed, Farthest Neighbor cannot conceivably be solved in less than O(n) time as you have to look at each element at least once. Nearest neighbor is less straightforward, but I guess an argument similar to the proof that any comparison sort needs at least O(n log n) time might work.) So, are you doing the test next week as well? Good luck, Matt

How much is it? Can I have access,,,