GRE CS Subject Test Contents by Links

1. Software System and Methodology - 35%
   1. Data organization
      1. Data types
      2. Data structures and implementation techniques
         • Dictionary of Algorithms and Data Structures (excellent official algorithm site)
           • Excellent Java sorting applets (burried deep inside the above one)
         • loop invariant: true at the beginning of each execution of the loop and at the completion of the loop.
         • Huffman Code (information theory)
         • stack: LIFO, queue: FIFO
      3. File organization (e.g. sequential, indexed, multilevel)
   2. Program control
      1. Iteration and recursion
      2. Functions, procedures, and exception handlers
      3. Communication and synchronization
   3. Programming languages and notation
      1. Constructs for data organization and program control
      2. Scope, binding, and parameter passing
         • Dynamic Type Checking vs. Static Type Checking:
           • Dynamic scoping elminates the possibility of static type checking
           • Error checking can be done at two different times:
             Dynamic checking requires the program to be executed.
             Static checking happens before runtime.
           • Evaluation: Static checking is preferable for two reasons
             runtime efficiency
             completeness (static checking does not exclude run-time errors! but it excludes run-time errors due to type misuse.)
         • Subprograms, argument passing (general) (.html)
         • Parameter Passing (general) (.html)
         • Pass-by-Name (clearly explained) (.html)
         • Scoping: Static vs. Dynamic (.html)
           • static scoping: A subprogram is called in the environment of its definition.
           • dynamic scoping: A subprogram is called in the environment of its caller
         • No extra space swap
           • i = i - j; j = i + j; i = j - i;
      3. Expression evaluation
   4. Systems
      1. Compilers and interpreters
         • Shift Reduce Parsing
         • Bottom-up Parsing (.html) (Best explained)
         • LR Parser (.html)  wikipedia
         • LR Parser (.pdf)
         • Compiler Design Notes (.pdf)
         • Compiler optimization
           •  NULLSTONE compiler optimization category (.html) over 40 techniques
           •  wikipedia compiler optimization page (.html)
         • Code generation, Caller-save vs. Callee-save (.pdf)
         • Caller-save vs. Callee-save
           • Caller and callee do not know anything about each other
           • Caller-save (before the call)
             + Caller knows which registers it needs and must preserve
             - But caller does not know which registers used by callee, may save more register than necessary
           • Callee-save (before executing the procedure)
             + Callee knows which registers it will use and must preserve
             - But may preserve registers that caller doesn't care about
      2. Operating Systems, including resource management and protection/security
         1. Job Scheduling
         2. Mutual Exclusion
         3. Semaphore and P V operations
         4. Other topics about OS
            • Operating system = resource manager (most important function)
            • reentrant: A reentrant program is one which does not alter in the course of execution; in other words, it consists entirely of pure (read-only) code. Reentrancy is important whenever asynchronous execution is possible; for example, a non-reentrant program may not be safe to call from a signal handler. In systems with multiple threads of control, a non-reentrant program must be called only within interlocks. (Macro is reentrant)
         5. Multi-threading: has own stack and context (control of flow), but shares other resources such as same memory space, data, and files (loaded into memory).
            • Multithreading for Rookies (.html) Microsoft Tech.net
            • Multithreading (.html)
         6. interrupt: IO, page fault, task switching (?), definitely no cache missing.
      3. Networking and distributed systems
      4. System development tools
      5. System performance

2. Computer Organization and Architecture, Operating System - 20%
   1. A. Logic Design
      1. Implementation of combinational and sequential circuits
         • combinational circuits: no flip-flop, memoryless
         • sequential circuits: has flip-flop, has memory, must be controlled by an external clock(?), may have feed back.
      2. Functional properties of digital integrated circuits
         • Boolean Logic and Gates (.html)
         • DeMorgan's Law (html)
         • identities (html)
         • identities (html)
   2. Processors and control units
      1. Instruction sets
         • illustrated RISC (.html) stanford
         • CISC vs. RISC (.pdf) list of comparisons
         • CISC vs. RISC (.html)
         • CISC vs. RISC (comparisons and examples) (.html slides)
         • Instruction set: horizontal vs. vertical microarchitecture (.html) Horizontal mode is useful for fetching a sequence of bytes, while vertical mode is useful for fetching corresponding nibbles from two floating point numbers that are 8 bytes apart in memory. (horizontal: unencoded) (vertical: have a single opcode and multiple operand specifiers, encoded, require more time steps)
      2. Register and ALU organization
      3. Number representation
      4. Control sequencing
         • Microinstruction: An instruction that controls data flow and instruction-execution sequencing in a processor at a more fundamental level than machine instructions. Note: A series of microinstructions is necessary to perform an individual machine instruction. (CPU internal logic, different from CPU instruction, related to how CPU instruction opcode, but not related to CPU instruction address.)
         • instruction interpretation:
           • fetch
           • defer (for indirect addressing)
           • execute
      5. Data paths
   3. Memories and their hierarchies
      1. Speed, capacity, cost, allocation
         • Garbage collection:
           • not suited for reclaiming cyclic structures
           • incurs additional space overhead for each memory cell
           • an alternative to mark-and-sweep garbage collection
           • time to reclaim could be linear in the number of cells to be reclaimed.
      2. Cache, main, secondary storage
         • Cache Mapping
         • Excellent Tutorial (with cool demos) on Caching and Pipelining (.html)
      3. Virtual memory, paging, segmentation
         • Farthest in the future: Optimal but unpractical, all practical paging algorithm gather info from the history.
         • FIFO: First In Last Out
         • LIFO: Last In First Out
         • LRU: Least Recently Used
         • LFU: Least Frequently Used
   4. Communication
      1. Bus, switch, and network structures and protocols
         • Hamming distance: It can be shown that to detect n bit errors, a coding scheme requires the use of codewords with a Hamming distance of at least n + 1. It can also be shown that to correct n bit errors requires a coding scheme with at least a Hamming distnace of 2n + 1 between the codewords
         • Packet switch network: eg. TCP/IP: the packets of the same message may arrive out of order.
         • complete interconnected network: n(n-1)/2 links
         • ring network: n links, provide 2 distinct paths between any two processors.
      2. I/O
         • memory-mapped I/O
         • DMA (Direct Memory Access) (.html) necessary condition: no other I/O is processing at the same time.
      3. Synchronization
         • Serializability (.pdf) page 7, a good one
         • Serializability (.html)
         • Serializability (.html)
         • Serializability (.pdf)
   5. High-performance architectures
      1. Pipelining
         • Excellent Tutorial (with cool demos) on Caching and Pipelining (.html)
      2. Multiprocessors
      3. Vector processors

3. Theory - 20%
   1. Automata and language theory
      1. Models of computation (finite automata, pushdown automata, Turing machines)
      2. Formal languages (regular languages, context free language)
         • Chomsky hierarchy, Type (0), ... grammar (.html) wikipedia.org
         • Ambiguous Context-Free Grammar (.pdf)
      3. Decidability
   2. Design and analysis of Algorithms and computational complexity
      1. Exact or asymptotic analysis of the best, worst, or average case for the time and space complexity of specific algorithms
         • Algorithms and Complexities (collection) (.html)
      2. Upper and lower bounds on the complexity of specific problems
      3. NP-completeness
         • A compendium of NP optimization problems
         • An Annotated List of Selected NP-complete Problems
         • P, NP, CO-NP, NP-complete, NP-hard
   3. Correctness of programs
      1. Formal specifications and assertions (Hoare's triple, loop invariant)
      2. Verification techniques

4. Methematical Background - 20%
   1. Discrete structures
      1. Mathematical logic
         • karnaugh map (.html)
      2. Elementary combinatorics, including graph theory and counting arguments
         • Binomial coefficients (.html) MathWorld
      3. Elementary discrete mathematics, including number theory, discrete probability, recurrence relations
   2. Numerical mathematics, Numerical analysis
      1. Computer arithmetic, including number representations, roundoff, overflow and underflow
         • Floating point: representation, roundoff (detailed tutorial) (.html)
         • Data Representation (local .pdf)
         • Data Representation, logic (local .doc)
         • BCD (Binary Coded Decimal) (local .pdf)
      2. Classical numerical algorithms
         • Numerical Analysis (.html)
         • Newton's Method
         • Bisection Method
      3. Linear algebra
         • Matrix Factorizatioin (.ppt)
         • Permutation Matrix (.html) MathWorld

5. Advanced Topics - 5%
   • Topics including modeling and simulation, information retrieval artificial intelligence, computer graphics, data communicatioins, databases, VLSI.

• Glossary
  • SPOOLing (Simultaneous Peripheral Operations On-LINe) (.html)
  • daemon
• Links
  • wikipedia Very useful science encyclopedia
  • CS GRE booklet written by Christopher Scaffidi
  • P, NP, CO-NP (.html)
  • Operating System (.html site)  Comprehensive OS lecture
  • David Yu Chen's GRE Link Some review, but not complete
  • my notes (.html)