Skip to main content
Get your Wikispaces Classroom now:
the easiest way to manage your class.
Pages and Files
Add "All Pages"
An aggregation of information for the GRE CS examination
Official ETS paper - 2003
2001 Test with solutions
102 Questions on various topics covered on the GRE CS
Advice, including CS GRE exam prep
CS GRE Notes from Stanfo
Hunter Hogan's Study Guide
Major Field Test in CS
Videos on Theory of Computation
A pot of links by CalmLogic
Various Driller Threads
Various Threads on Recurrences
Closure and set properties of various Languages
Slightly overkill notes on Computer Architecture
Howardz notes from gatech
Notes by Ivo Jimenez
Some sample questions for practice
: The Urch forums contain a
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
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.
to your advantage.
(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
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.
You will be given a program fragment and will be asked to calculate:
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 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
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 (
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)
help on how to format text
Turn off "Getting Started"