## Computer Science GRE Study Guide, Digital logic design

Table of Contents II.    Computer Organization and Architecture – 15% A.    Digital logic design 1.      Implementation of combination and sequential circuits a.       Definition: Sequential circuits have memory, and the output depends on the input and the memory. Combinational circuits do not have memory and the output is based only on the input. b.      A flip-flop

## Computer Science GRE Study Guide, Memories and their hierarchies

Table of Contents II.    Computer Organization and Architecture – 15% C.     Memories and their hierarchies 1.      Performance, implementation, and management a.       Definition: Because fast memory is significantly more expensive that slow memory, you cannot load up your system with fast memory. So, you must have different speeds of memory. Managing that memory is a sophisticated

## Computer Science GRE Study Guide, Networking and communications

Table of Contents II.    Computer Organization and Architecture – 15% D.    Networking and communications 1.      Interconnect structures (e.g. buses, switches, routers) a.       Caveat: I do not have time to put any information in this section. According to people that took the test in November 2003, there are networking questions on the test. 2.      I/O systems

## Computer Science GRE Study Guide, Exact and asymptotic analysis of specific algorithms

Table of Contents III. Theory and Mathematical Background – 40% A.    Algorithms and complexity 1.      Exact and asymptotic analysis of specific algorithms a.       Definition: When looking at an algorithm and evaluating it, we might want to precisely define how long it will take the program to run (exact analysis), but we usually just approximate the

## Computer Science GRE Study Guide, Algorithmic design techniques

Table of Contents III. Theory and Mathematical Background – 40% A.    Algorithms and complexity 2.      Algorithmic design techniques (e.g. greedy, dynamic programming, divide and conquer) a.       Definition: Since we really do not know how to make algorithms, we have created artistic guidelines. b.      Divide-and-conquer is an effective algorithmic technique that requires recursion. First recursively divide

## Computer Science GRE Study Guide, Computational complexity, including NP-completeness

Table of Contents III. Theory and Mathematical Background – 40% A.    Algorithms and complexity 4.      Computational complexity, including NP-completeness a.       Definition: Computability refers to whether or not a certain type of machine can solve a certain problem. b.      Definition: NP-complete problems are special problems in modern computing. The name comes from the fact that you

## Computer Science GRE Study Guide, Models of computation

Table of Contents III. Theory and Mathematical Background – 40% B.     Automata and language theory 1.      Models of computation (finite automata, Turing machines) a.       Definition: Before we made computers from sand, people designed models on paper that could calculate. These hypothetical machines are the basis for all modern computers. b.      A deterministic finite automaton (DFA)

## Computer Science GRE Study Guide, Formal languages and grammars

Table of Contents III. Theory and Mathematical Background – 40% B.     Automata and language theory 2.      Formal languages and grammars (regular and context free) a.       Definition: The users manual for the computational machines (see III.B.1.a) consist of the things you are allowed to do to them. To say it another way, all of the inputs

## Computer Science GRE Study Guide, Decidability

Table of Contents III. Theory and Mathematical Background – 40% B.     Automata and language theory 3.      Decidability a.       Definition: A machine cannot solve some problems. If the machine can solve it, then we say it is decidable on that machine. b.      Some problems cannot be solved by an algorithm. For example, it is impossible to

## Computer Science GRE Study Guide, Boolean logic

Table of Contents III. Theory and Mathematical Background – 40% C.     Discrete structures 1.      Mathematical logic a.       Definition: Mathematical logic is based on formulas that are always true or false. b.      Three Americans (a scientist, a mathematician, and a logician) are traveling on a train in China. The scientist sees a green cow in the