An aggregation of information for the GRE CS examination


Resources


Forums

  • Urch Forums: The Urch forums contain a wealth of information on not just subject matter, but also other paraphranelia concerning administrative stuff about the test.
  • Yahoo! GRECS group Check the "files" section for previous year tests and other material

Tips

  • Revisit the practice tests from the last 3 years at least. They are very helpful. They will give you a feel for not only the type of questions but also the distribution by topic.
  • Use Titanium Bits to your advantage.
  • Use cs_gre_notes (from Stanford) to get a rough idea of the syllabus and the main topics. Also the material contained here will give you a good idea of what to study.
  • Use wikipedia effectively.
  • If you've studied decently, you shouldn't find more than 6-7 questions in this paper hard
  • Since this is a multiple-choice answer paper, prepare accordingly. Make sure you are strong at your fundamentals. That will help you distinguish among multiple seemingly correct options.

Question Types

  • You will be given a program fragment and will be asked to calculate:
    • Its output
    • Its runtime/space complexity
    • The final state of some data structure
    • Some invariant of the code fragment (pre/post condition)
    • The output when the parameters are passed (parameter passing methods):
      • By value
      • By reference
      • By name
      • By value result
      • By object reference
  • You will be given a pre/post/infix expression and asked to:
    • Find the equivalent pre/post/infix expression
    • Calculate the value of the expression
  • You will be given a Binary Tree and asked questions that relate it to a Binary Search Tree (BST)
  • Questions on various BST traversals (in/pre/postorder)
  • Questions about Finite State Machines
  • You will be given a statement (question) and you need to answer whether it is decidable or not
  • Examples of decidable questions:
    • How many states does a TM have?
    • Will a TM halt within 'k' steps?
    • How many states does the minimized FSM for this language have?
    • Are these 2 regular language equivalent (i.e. Accept only the same set of strings)?
    • (subtle): Is this context-free language a subset of this regular language
  • Examples of undecidable questions:
    • Are these 2 CFGs the same?
    • Are these 2 TMs the same?
    • Will this TM halt after 'k' steps?
    • Will this TM finish computing before sunset if it were to start before sunrise on the same day? (correction: Assuming that you know how much time each step of the turing machine takes and if all steps take the same amount of time, then this _IS_ decidable. Thanks to Jeffrey for this!!)
    • (subtle): Is this regular language a subset of this context-free language
  • You will be given a Context Free Grammar (CFG) definition and asked:
    • If it is ambiguous
    • Which out of a set of strings it accepts
    • Which out of a set of strings it does NOT accept
    • If it generates the empty string
    • Generates a finite or infinite set
    • How many sentential forms are possible for a certain input string
  • You will be given 2 or more CFG definitions and asked:
    • If they are equivalent -- i.e. Generate the same set of strings
  • You will be given an english language description of a language(grammar) and asked if it is::
  • You will be give a list of page numbers and the number of pages that a certain fixed size cache can hold. You will have to simulate one of the page replacement algorithms such as LRU, LFU, optimal, MRU, MFU, FIFO, etc... on these pages and answer questions such as:
    • Which pages resulted in page faults
    • Which pages are in still in the cache
    • Which pages entered the cache but are not in it any more
  • If you are given the FIFO page replacement algorithm for simulation purposes, you might be asked what size of the cache results in the fewest number of page faults. In case of FIFO, a larger cache size need not necessarily result in fewer page faults. In fact, it may result in more page faults. It is called as Belady's anomaly.
  • You will be asked to match machines to the corresponding highest language that they recognize. For example:
    • DFA/NFA -- Regular Grammar
    • PDA -- Context-Free Grammar
    • LBA -- Context-Sensitive Grammar
    • TM -- Recursive Language (a TM can decide a recursive language but recognize a recursively enumerable one)
  • You will be asked to compute the number of tag bits given the main memory size, the cache size and type of cache (direct, associative, set-associative).
  • Various other questions on caches. You should study these in great detail.
  • You will be given a program fragment and asked what certain variables should be initialized to for a particular desired final outcome.
  • You will be given a program fragment and asked what certain semaphore variables should be initialized to for the correct functioning of the program according to a set of specified requirements.
  • You will be asked certain questions on probability and counting. I personally am bad at probability, so I found these to be slightly hard and left them untouched. Counting too can be a bit dicy at times.
  • You will be asked to classify the best (or a certain) solution to a problem as lying in P or NP or NP-Complete, etc... Basically, the most tight classification that you can give. Some problems may also expect a lose classification, and would be worded differently. i.e. As True/False questions.
  • Questions involving virtual memory, segmentation, their advantages, disadvantages, use-cases and the like.
  • You will be given a boolean formula or a circuit and would be asked:
    • To calculate the minimized SOP or POS form
    • Which out of the given boolean formulae it is equivalent to.
  • You will be given a recurrence equation for the runtime of a program and you will be asked to compute the program's runtime in big-Oh notation. For example, suppose T(n) = T(n-1) + n then the program's runtime is: O(n^2)