Cs Gre Notes

Transcript

Eta Kappa Nu – Mu Chapter CS GRE Notes CS GRE Notes Eta Kappa Nu – Mu Chapter  Department of Electrical Engineering and Computer Sciences College of Engineering UC Berkeley Revision History Section(s) 162 61C, 150, 152, 170, 172, 174 170, 172 170, 172 150 Editor Karl Chen Email quarl@hkn Semester Fall 2004 Brandon Ooi brandono@hkn Fall 2004 Alex Fabrikant Michael Martin James Donald Steve VanDeBogart Brenda Liu alexf@hkn mcmartin@hkn Fall 2003 Fall 2002 Fall 2001 vandebo@hkn Fall 2001 61C, 152 Fall 2001 61C, 152 Comments Unified document, integrated some notes. Many new notes. Updated notes by Michael Martin TABLE OF CONTENTS I. SOFTWARE SYSTEMS AND METHODOLOGY.................. METHODOLOGY................................ ............................ ............................ ........................... ........................... .....................3 .......3 A. DATA ORGANIZATION ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ ...........................3 .............3 1. Data types ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ ........................... ...........................3 ..............3 2. Data structures and implementation implementation techniques ........................... ......................................... ............................ ............................ ............................ .........................3 ...........3 B. PROGRAM CONTROL AND STRUCTURE ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ..................3 ....3 1. Iteration and recursion ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ........................... ....................3 .......3 2. Procedures, functions, methods, and exception handlers ........................... ......................................... ............................ ............................ .........................3 ...........3 3. Concurrency, communication, and synchronization..................... synchronization................................... ............................ ............................ ............................ .........................3 ...........3 C. PROGRAMMING LANGUAGES AND NOTATION ............................ .......................................... ............................ ............................ ............................ ........................... ....................3 .......3 1. Constructs for data organization and program control ............................ .......................................... ............................ ........................... ...........................3 ..............3 2. Scope, binding, and parameter passing ............................ .......................................... ............................ ............................ ............................ ............................ .......................3 .........3 3. Expression evaluation ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ .......................3 .........3 D. SOFTWARE ENGINEERING ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ .......................3 .........3 1. Formal specifications and assertions............................ assertions.......................................... ............................ ............................ ............................ ........................... ...........................3 ..............3 2. Verification techniques...................... techniques.................................... ............................ ............................ ............................ ............................ ............................ ............................ ...........................3 .............3 3. Software development models, patterns, and tools ....................................... ..................................................... ............................ ............................ .......................3 .........3 E. SYSTEMS ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ ........................... ........................... .....................3 .......3 1. Compilers, interpreters, and run-time systems ........................... ......................................... ............................ ............................ ........................... ...........................3 ..............3 2. Operating systems, including resource management and protection/security protection/security .......................... ........................................ .......................4 .........4 3. Networking, Internet, and distributed systems ............................ .......................................... ............................ ............................ ........................... ...........................4 ..............4 4. Databases............................ Databases.......................................... ............................ ............................ ............................ ............................ ............................ ............................ ........................... ...........................4 ..............4 5. System analysis and development tools.................................. tools................................................ ............................ ............................ ............................ ............................ ..................4 ....4 Page 1 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes II. COMPUTER ORGANIZATION ORGANIZATION AND ARCHITECTURE................. ARCHITECTURE............................... ............................ ........................... ........................... .....................5 .......5 A. DIGITAL LOGIC DESIGN ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ .........................5 ...........5 1. Implementation Implementation of combinational and sequential circuits ............................ .......................................... ............................ ............................ .......................5 .........5 2. Optimization and analysis................................. analysis............................................... ............................ ............................ ............................ ............................ ............................ .......................11 .........11 B. PROCESSORS AND CONTROL UNITS ........................... ......................................... ............................ ............................ ............................ ............................ ............................ .....................16 .......16 1. Instruction sets ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ ..................17  ....17  2. Computer arithmetic and number representation ........................... ......................................... ............................ ............................ ............................ .....................17  .......17  3. Register and ALU organization.................... organization.................................. ............................ ............................ ............................ ............................ ............................ ............................20 ..............20 4. Data paths and control sequencing............................ sequencing.......................................... ............................ ............................ ............................ ............................ ............................24 ..............24 C. MEMORIES AND THEIR HIERARCHIES ........................... ......................................... ............................ ............................ ............................ ............................ ........................... ..................24 .....24 1. Performance, implementation, implementation, and management..................... management................................... ............................ ............................ ............................ ............................25 ..............25 2. Cache, main, and secondary storage ............................ .......................................... ............................ ............................ ............................ ........................... .........................25 ............25 3. Virtual memory, paging, and segmentation .................................. ................................................ ............................ ............................ ............................ .......................25 .........25 D. N D. NETWORKING AND COMMUNICATIONS ............................ .............. ............................ ............................ ............................ ............................ ............................ ............................25 ..............25 COMMUNICATIONS 1. Interconnect structures (e.g., buses, switches, routers) ............................ .......................................... ............................ ........................... .........................25 ............25 2. I/O systems and protocols ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................25 ..............25 3. Synchronization....................... Synchronization..................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .....................25 .......25 E. HIGH-PERFORMANCE ARCHITECTURES ............................ .......................................... ............................ ............................ ............................ ............................ ............................25 ..............25 1. Pipelining superscalar and out-of-order execution processors ........................... ......................................... ............................ ............................25 ..............25 2. Parallel and distributed architectures ........................................ ...................................................... ............................ ............................ ........................... .........................28 ............28 III. THEORY AND MATHEMATICAL MATHEMATICAL BACKGROUND BACKGROUND .......................... ........................................ ............................ ............................ ............................28 ..............28 A. ALGORITHMS AND COMPLEXITY ............................ .......................................... ............................ ............................ ............................ ............................ ............................ .......................29 .........29 1. Exact and asymptotic analysis of specific algorithms ............................ .......................................... ............................ ............................ ............................30 ..............30 2. Algorithmic design techniques (e.g. greedy, dynamic programming, divide and conquer) ...........................32 ...........................32 3. Upper and lower bounds on the complexity of specific problems ........................... ........................................ ........................... ..........................34 ............34 4. Computational complexity, including NP-completeness NP-completeness ........................... ......................................... ............................ ........................... .........................34 ............34 B. AUTOMATA AND LANGUAGE THEORY ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ................35 ..35 1. Models of computation (finite automata, Turing machines) ............................ .......................................... ........................... ........................... ...................35 .....35 2. Formal languages and grammars (regular and context free)..................................... free)................................................... ............................ .....................39 .......39 3. Decidability............................. Decidability........................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .....................40 .......40 C. DISCRETE STRUCTURES ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ .......................40 .........40 1. Mathematical logic ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ .........................40 ...........40 2. Elementary combinatorics and graph theory....................................... theory..................................................... ............................ ............................ ............................ ................40 ..40 3. Discrete probability, recurrence relations, and number theory ........................... ......................................... ............................ ............................40 ..............40 VI. OTHER TOPICS ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ ..................40 ....40 V. REFERENCES REFERENCES ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .......................41 .........41 Page 2 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes II. COMPUTER ORGANIZATION ORGANIZATION AND ARCHITECTURE................. ARCHITECTURE............................... ............................ ........................... ........................... .....................5 .......5 A. DIGITAL LOGIC DESIGN ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ .........................5 ...........5 1. Implementation Implementation of combinational and sequential circuits ............................ .......................................... ............................ ............................ .......................5 .........5 2. Optimization and analysis................................. analysis............................................... ............................ ............................ ............................ ............................ ............................ .......................11 .........11 B. PROCESSORS AND CONTROL UNITS ........................... ......................................... ............................ ............................ ............................ ............................ ............................ .....................16 .......16 1. Instruction sets ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ ..................17  ....17  2. Computer arithmetic and number representation ........................... ......................................... ............................ ............................ ............................ .....................17  .......17  3. Register and ALU organization.................... organization.................................. ............................ ............................ ............................ ............................ ............................ ............................20 ..............20 4. Data paths and control sequencing............................ sequencing.......................................... ............................ ............................ ............................ ............................ ............................24 ..............24 C. MEMORIES AND THEIR HIERARCHIES ........................... ......................................... ............................ ............................ ............................ ............................ ........................... ..................24 .....24 1. Performance, implementation, implementation, and management..................... management................................... ............................ ............................ ............................ ............................25 ..............25 2. Cache, main, and secondary storage ............................ .......................................... ............................ ............................ ............................ ........................... .........................25 ............25 3. Virtual memory, paging, and segmentation .................................. ................................................ ............................ ............................ ............................ .......................25 .........25 D. N D. NETWORKING AND COMMUNICATIONS ............................ .............. ............................ ............................ ............................ ............................ ............................ ............................25 ..............25 COMMUNICATIONS 1. Interconnect structures (e.g., buses, switches, routers) ............................ .......................................... ............................ ........................... .........................25 ............25 2. I/O systems and protocols ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................25 ..............25 3. Synchronization....................... Synchronization..................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .....................25 .......25 E. HIGH-PERFORMANCE ARCHITECTURES ............................ .......................................... ............................ ............................ ............................ ............................ ............................25 ..............25 1. Pipelining superscalar and out-of-order execution processors ........................... ......................................... ............................ ............................25 ..............25 2. Parallel and distributed architectures ........................................ ...................................................... ............................ ............................ ........................... .........................28 ............28 III. THEORY AND MATHEMATICAL MATHEMATICAL BACKGROUND BACKGROUND .......................... ........................................ ............................ ............................ ............................28 ..............28 A. ALGORITHMS AND COMPLEXITY ............................ .......................................... ............................ ............................ ............................ ............................ ............................ .......................29 .........29 1. Exact and asymptotic analysis of specific algorithms ............................ .......................................... ............................ ............................ ............................30 ..............30 2. Algorithmic design techniques (e.g. greedy, dynamic programming, divide and conquer) ...........................32 ...........................32 3. Upper and lower bounds on the complexity of specific problems ........................... ........................................ ........................... ..........................34 ............34 4. Computational complexity, including NP-completeness NP-completeness ........................... ......................................... ............................ ........................... .........................34 ............34 B. AUTOMATA AND LANGUAGE THEORY ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ................35 ..35 1. Models of computation (finite automata, Turing machines) ............................ .......................................... ........................... ........................... ...................35 .....35 2. Formal languages and grammars (regular and context free)..................................... free)................................................... ............................ .....................39 .......39 3. Decidability............................. Decidability........................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .....................40 .......40 C. DISCRETE STRUCTURES ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ .......................40 .........40 1. Mathematical logic ........................... ......................................... ............................ ............................ ............................ ............................ ............................ ............................ .........................40 ...........40 2. Elementary combinatorics and graph theory....................................... theory..................................................... ............................ ............................ ............................ ................40 ..40 3. Discrete probability, recurrence relations, and number theory ........................... ......................................... ............................ ............................40 ..............40 VI. OTHER TOPICS ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ ..................40 ....40 V. REFERENCES REFERENCES ............................ .......................................... ............................ ............................ ............................ ............................ ............................ ............................ ............................ .......................41 .........41 Page 2 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes I. Software Systems and Methodology A. Data organization  1. Data types 2. Data structures structures and implementation implementation techniques B. Program control and structure  1. Iteration and recursion 2. Procedures, functions, methods, and exception handlers 3. Concurrency, communication, and synchronization C. Programming languages and notation  1. Constructs for data organization and program control 2. Scope, binding, and parameter passing 3. Expression evaluation D. Software engineering  1. Formal specifications and assertions 2. Verification techniques 3. Software development models, patterns, and tools E. Systems  1. Compilers, interpreters, and run-time systems Page 3 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes 2. Operating systems, including resource management and protection/security 3. Networking, Internet, and distributed systems 4. Databases 5. System analysis and development tools Page 4 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes II. Computer Organization and Architecture This part of the test focuses on the following courses. • • • • • Machine Structures (CS61C) Components and Design Techniques for Digital Systems (CS150) Computer Architecture (CS152) Introduction to Communication Networks (EE122) Graduate Computer Architecture (CS252) A. Digital logic design  • To summarize, most of the material on the CS GRE Test that is covered in CS 150 is about combinational logic. Finite state machines are very important too, but on the CS GRE they are tested more from the standpoint of CS 164 or CS 172. • James Donald estimates that generally no more than 12% (<= 9 questions) on the test are on CS 150 material. For the hardware stuff, CS 61C (or CS 152) can cover significantly more. In the below figure shows where in the design hierarchy we will be looking at. 1. Implementation of combinational and sequential circuits i. Combinational Logic Hopefully you’ve seen a little bit of digital design by now. If not, you’re in luck because the CS GRE does not dig very deep and is limited to mostly combinational logic Switch Logic and Basic Gates Page 5 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Here is a breakdown of the basic gates. You will not have to know details below gate-level analysis. • AND – This gate is high when both its inputs are high • OR – Gate is high when either of its inputs are high. • XOR – Gate is high if the first or second input is high, not both. •  NOT – Gate is high when input is low. •  NAND – NOT of the AND gate. •  NOR – NOT of the OR gate. • XNOR – NOT of the XOR gate. Although all of these gates can be manufactured separately, you can actually create any gate from the NAND gate. Lets look a little into how that might be done. To prove that these are equivalent, we can draw a truth table. Page 6 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Truth tables can be made from any digital circuit and, as we’ll see later, are complete descriptions of a circuit’s functionality. They can be written as an expression in Boolean Algebra using AND, OR, NOT. These three gates are the most fundamental gates. This example shows the truth table for simple circuit. *Note that the truth table is a unique signature of a Boolean function. Many alternative gate realizations may exist for any given truth table. Minimization of gate is possible as we will see later.  Boolean Algebra It turns out that Boolean expressions, truth tables and the digital design are all related. Below is a diagram of their relationships. Truth tables are pure definitions for a Boolean function. A Boolean expression is helpful for manipulation using Boolean algebra. Digital gates can be thought of as feasible ways of  implementing these Boolean functions. Boolean Algebraic Structure • Set of elements B • Binary operations {OR, AND} => {+, *} • Unary Operator {NOT} => {‘} (also seen as ~ or a bar on top of the element. • Such that the following axioms hold. Page 7 of 41 Eta Kappa Nu – Mu Chapter 1. 2. 3. 4. 5. 6. 7. CS GRE Notes Set B contains at least 2 elements, a,b, such that a != b Closure: a + b is in B a * b is in B Commutativity: a+b=b+a a*b=b*a Associativity: a + (b + c) = (a + b) + c a * (b * c) = (a * b) * c Identity: a+0=a a*1=a Distributivity: a + (b * c) = (a + b) * (a + c) a * (b + c) = (a * b) + (a * c) Complementary a + a’ = 1 a * a’ = 0 As you can see, Boolean algebra is defined and manipulated much like regular algebra. Axioms and Theorems of Boolean Algebra • • • • • • • • • • • • Identity 1. X + 0 = X 1D. X • 1 = X  Null 2. X + 1 = 1 2D. X • 0 = 0 Idempotency: 3. X + X = X 3D. X • X = X Involution: 4. (X')' = X Complementarity: 5. X + X' = 1 5D. X • X' = 0 Commutativity: 6. X + Y = Y + X 6D. X • Y = Y • X Associativity: 7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z) Distributivity: 8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = (X + Y) • (X + Z) Uniting: 9. X • Y + X • Y' = X 9D. (X + Y) • (X + Y') = X Absorption: 10. X + X • Y = X 10D. X • (X + Y) = X 11. (X + Y') • Y = X • Y 11D. (X • Y') + Y = X + Y Factoring: 12. (X + Y) • (X' + Z) = 12D. X • Y + X' • Z = X • Z + X' • Y (X + Z) • (X' + Y) Concensus: 13. (X • Y) + (Y • Z) + (X' • Z) = 13D. (X + Y) • (Y + Z) • (X' + Z) = X • Y + X' • Z (X + Y) • (X' + Z) De-Morgan’s Law Page 8 of 41 Eta Kappa Nu – Mu Chapter (a + b)’ = a’ b’ a + b = (a’ b’)’ CS GRE Notes (a b)’ = a’ + b’ (a b) = (a’ + b’)’ Basic Steps: 1. Change all variables to their complements. 2. Change all AND operations to ORs. 3. Change all OR operations to ANDs. 4. Take the complement of the entire expression. For example: F (w,x,y,z) f’(w,x,y,z) = w’ + x’ + = w’ + x’ + = w’ + x’ + = w’ + x’ + = w’ + x’ + = wx(y’z + yz’) = w’ + x’ + (y’z +yz’)’ (y’z)’(yz’)’ (y + z’)(y’ + z) yy’ + yz + z’y’ + z’z 0 + yz + z’y’ + 0 yz + y’z’ //negate operators and plus We can also see De Morgan’s law in action at the gate level. In the following diagram, we see how De Morgan’s law is applied at the gate level. Sum Of Products (SOP) - This is useful (read: easiest) for deriving a (usually not optimal) Boolean expression given a truth table. The general idea is to sum all the cases (OR) where the function is true. For each case, AND together all the elements. If the element is false, we want to AND the NOT of that element. Page 9 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Sample Truth Table Problem: Solution: C The easiest way to do this problem is to just write the truth tables of each of the choices until you get one that is identical. The better way is to use Sum of Products. Here’s how to do it. First write the truth table for the function. Here x2 = C, x1 = B, x0 = A. C B A F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 F = AB’C’ + A’B’C + AB’C + A’BC = AB’(C’ + C) + A’C(B’ + B) = AB’(1) + A’C(1) = AB’ + A’C = x1’x0 + x2x0’ //Sum of products //Reverse distribution //Complimentary axiom Two-level Logic Extension of what you already know. The figure to the right denotes the sum of products that you just used above. This will  prove crucial in simplifying Boolean functions. In the image to the left is a visualization of a Boolean function with three variables (represented by the 3 digit binary number  at each corner). If the shaded area represents the function, we Page 10 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes are able to simplify its expression (rather than the shortsighted sum of pairs). ii. Sequential Logic The most basic component of sequential logic is a flip flop which basically stores 1 bit of  data and is clocked. There are many kinds of FF but the most common kind is the D-flip flop It takes 1 input. On the clock edge, Q takes the value of D at that time. Flip flops are the  basic part of registers. Below is the timing diagram for the D flip-flop In general, register, devices used to store and/or process data, are implemented with some kind of flip-flop that is used to store data. One example of these is the processor register in CPUs. 2. Optimization and analysis Karnaugh Maps These are also useful for deriving a Boolean expression from a truth table but better than sum of pairs as it can give a minimal expression. Page 11 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Gray-code – 00, 01, 11, 10. Another scheme for counting (other than sequential) but allows that only 1 digit change at each iteration. Provably infinitely extendable. 000, 001, 011, 010, 110, 111, 101, 100 How to use K-Maps Steps 1. Set up k-map table. 2. Fill in data from truth table. 3. Circle groups (rectangles and powers of 2 only!) 4. Derive Boolean expression! For example: F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15) F = C + A’BD + B’D’ Page 12 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes K-maps can also take advantage of don’t cares (the value doesn’t change the resultant expression). As seen below, you can draw your circles around don’t cares  Finite State Machines (FSMs) / Finite State Automaton Here’s a general overview of what they are, their parts and how those parts work together. FSMs are also a very important topic in Computability / Complexity and the study of programming languages. This section will only talk about implementing FSMs with digital logic. Overview – Finite state machines can be represented by a finite state diagram and accompanying transitions. There are 3 major types of FSMs • Acceptors – either accept input or not. (most common) • Recognizers – Variant of an acceptor (think of acceptance as recognition). This is useful for regular expression matching. • Transducers – Generate output from given input. Here is an example of a Determinisitic finite automaton (DFA). Note the start state, the accept state and the transitions. There are other types of DFA’s such as Non-deterministic finite automatons (NFAs) but in  practice are not easily translatable into a circuit. These FSMs are represented in digital logic in two distinct groups. Page 13 of 41 Eta Kappa Nu – Mu Chapter • CS GRE Notes Moore Machine – output is determined by the current state alone. We can see this in acceptors and recognizers but in general the output can be anything. Formal Definition A Moore machine can be defined an n-tuple { Q, Σ, ∆, δ, λ , q0 } consisting of  • • • • • • a finite set of states ( Q ) a finite set called the input alphabet ( Σ ) a finite set called the output alphabet ( ∆ ) a transition function (δ : Q x Σ → Q ) mapping a state and an input to the next state an output function ( λ : Q → ∆ ) mapping each state to the output alphabet. a start state (q0) The number of states in a Moore machine will be greater than or equal to the number of  states in the corresponding Mealy machine. In digital design, this Moore machine looks like the following: There are 3 major components in finite state machine design. 1. State logic 2.  Next state logic – based on its state and input 3. Output logic – based on its state Much like Boolean functions, FSMs are completely defined in their state transition table. An example state transition diagram is given below. Page 14 of 41 Eta Kappa Nu – Mu Chapter • CS GRE Notes Mealy Machine – output is determined by the current state and its input. Below is an example of a Moore machine in which the first number on the transition is the input, and the second number is the output based on that transition. In digital design it looks like this. The combinational logic contains the state and takes in input and gives the next state and output. Moore machines are, in general, simpler and easier to implement in digital design. One-hot encoding – This is a general technique to design an FSM. Each state has its own flip-flip which is high if and only if the machine is in that state. Therefore, only one FF is high at any given time (because you can only be in one state per cycle in a DFA). Page 15 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Other ways of storing state include a binary encoding of the states. B. Processors and control units  This section of the test stresses mostly CS61C and CS152 material. But don’t worry, the questions are very basic but broad. The following sections will focus mainly on the MIPS instruction set architecture although all the theory is applicable to any ISA. The following diagram shows where in the design hierarchy Moore’s Law – The speed of a processor doubles every 18 months. Not a scientific law, more of  an observation. This trend helps companies plan their processing power. Page 16 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes 1. Instruction sets At the very bottom of computer architecture an d machine structures themselves is the instruction set designed for it. There may not be any one instruction set architecture (ISA) that is the best. • Most desktop computers today use the x86 instruction set. • Most embedded computing devices use the MIPS architecture. • There are many other major players in the market such as the SPARC architecture (Sun), PowerPC (IBM), Motorola 6800, ARM, IA-64 etc. The design of the CPU as well as the corresponding system is heavily dependent on the ISA (MIPS branch delay slots, fixed length instructions). The ISA defines the machine langu age for  that CPU (read: assembly language). Here is a table of some of the instructions of the MIPS architecture. They won’t ask questions on a specific hardware but you should be aware of one and how assembly-level instructions behave in the pipeline. 2. Computer arithmetic and number representation To do these problems you need to understand how computers internally store numbers. Make sure you know how to convert between decimal, octal (base 8), hex (base 16) and of course  binary (base 2). Why do we use these bases (as opposed to others?) There exist many different ways of representing signed numbers. One naïve way is to do it is to use one bit to be the sign bit. The drawback is that there exist 2 numbers for zero (namely all 0’s Page 17 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes and all 1’s) and it makes addition and subtraction more difficult. The most convenient to store signed numbers is the use of two’s complement. 2’s complement - method of signifying negative numbers in binary. It is also an operation which may be applied to positive binary values in order to perform subtraction using the method of  complements, effectively allowing subtraction of one binary number from another using only the addition operation. This is useful in microprocessors for which subtraction is unavailable or too complex to perform efficiently. In the two's complement method, a signed binary numeral uses the leftmost bit as the sign bit and the remaining bits to indicate the value of the numeral. If the sign bit is 0, the remaining bits are interpreted according to the customary rules of the binary numeral system. If the sign bit is 1, the remaining bits contain a numeral in two's complement form. Consequently, a signed 8-bit binary numeral can represent any integer in the range -128 to +127. 7 If the sign bit is 0, then the largest value that can be stored in the remaining seven bits is 2 − 1, or 127. How to represent a number in 2’s complement. 1. Convert the number to standard binary form (with leading 0’s) 2. Invert all the digits 3. Add 1 As you can see, all positive numbers are represented the same as in standard binary form.  Negative numbers are different, however. For exa mple lets convert the 8-bit number 5(decimel) to -5(decimal): 0000 0101 //binary form 1111 1010 //invert digits = 1111 1011 = -5//add one. To do a subtraction A – B, we just do A + ~B where ~B is the 2’s complement 11111 111 (carry) 0000 0101 (5) + 1111 1011 (-5) =========== 0000 0000 (0) // 5 – 5 = 0 1’s complement - Addition is done in the standard way (carry will overflow into nothingness). Subtraction is done in much the same way as 2’s complement except any carry bit is added back  into the answer. Using n bits, how many numbers can be represented in 2's complement? n Total 2 numbers can be represented. Half are positive, half are negative. But remember 0 is first positive number. n-1 n-1 => -2 to 2 - 1 Page 18 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Floating Point Fixed point: decimal point is fixed Floating point: IEEE standard This is an improvement over the fixed point which allows the “point” to “float” over a large range of digits. Single precision (32-bit) [sign bit, exponent, significand] (float) sign: 1 bit, 1 for negative, 0 for positive numbers exponent: 8 bits, bias of 127 [-126…127] significand: 23 bits, implied 1 sign exp-127 value: -1 * (1.significand) * 2 Special Values: • Zero: all bits 0 • Denorms: exp 0, significand is less than 1 (no implied 1) • Infinity: exp 255 (all 1’s), significand 0 (division by 0) •  NaN: exp 255, significand not 0 (0/0, inf/inf)  Double precision (64-bit) [sign bit, exponent, significand] (double) Sign: 1 bit. Exponent: 11 bits, bias of 1023 Significand: 52, exp bias 1023  Rounding: 4 IEEE options: - up to infinity: always round up - down to -infinity: always round down - truncate: drop the last bits, round towards 0 - round to even: normal rounding, but if the value is exactly halfway in between, round to the nearest even number  Overflow and underflow: overflow: if both numbers are positive and result is neg ative underflow: if both numbers are negative and the result is 0 or positive. saturating arithmetic: instead of rolling over on overflow or underflow, the result is set to be the maximum or minimum possible value. (Integer.MAX_VALUE) Page 19 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes 3. Register and ALU organization Processors are made of x main components. • PC – Program counter, usually the address of the instruction. • Instruction Memory – usually a cache. • Register File • ALU – Arithmetic Logic Unit • Data Memory – Also a cache with write buffer. Below is a rough diagram of an unpipelined processor. The program counter feeds the address of the next instruction to the instruction memory. The instruction memory looks up the next instruction which goes into the instruction register. The instruction is then decoded and transferred to the register file for lookups of the affected registers. You can look up a maximum of 2 processor registers which go into registers A and B. These go to the ALU which uses the values of A and B to calculate the ALUOut which is stored in the ALUOut register. This is then used to write back to the register file. Pipelined Processors These processors use pipelining to achieve more performance. • Pipelined processors have multiple stages but same overall functionality as a single-cycle  processor. Idea is to split the datapath up into parts which can be overlapped in time. • Increased throughput at the cost of increased latency. For our purposes, this is an okay tradeoff. • Throughput – Amount of instructions you can execute per time. (i.e. inst/sec) • Latency – How long an instruction takes to complete from start to finish. • Most common is the 5-stage pipeline. 5-Stage Pipeline Page 20 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Stages: • IF: Instruction Fetch – Use PC to fetch an instruction from the instruction memory. • ID: Instruction Decode – Decode the instruction and read values from register file. • EX: Execute – Execute instruction using the ALU. (optional. e.g. lw) • MEM: Memory – Read or write from data memory. • WB: Write Back – Write result back to the register file. Pipelining allows for less logic per stage and thus a high clock frequency. Let’s look at the  pipelining from a higher perspective. Page 21 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes The whole point about pipelining is to split the data path into components which we can use simultaneously. As you can see from the shaded re gion, all 5 stages of the pipeline are being used at the same time but on different instructions. Once the pipeline is filled, it will output one instruction per cycle. Caveats • Hazards: o Structural – When a component in a pipeline needs to be used by more than 1 thing per cycle. One example of this is Instruction and Data memory both need access to shared data (SDRAM). This is resolved by stalling the pipeline and a rbitrating requests between the two. o Data RAW – Read after Write – Need to forward data ahead in pipeline. WAW – Write after Write – Not a problem if instructions are sequential. WAR – Write after Read – Not a problem if sequential. RAR – Read after Read – Not a problem. • Forwarding – Sometimes we need to know the answer to an instruction before it is written back to the register file. Forward the data still in the pipeline!      • Stalling – Sometimes we cannot resolve a data dependency because it is needed before we can determine the solution. o Load followed by a branch o Logical/arithmetic followed by a branch. Page 22 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Is resolved by stalling… The basic point is that data can only travel forwards in time. Performance There are many measures of performance but the one that really matters is execution time. Factors of System Performance 1. cycles per instruction (CPI) – usually comparable against processors of the same architecture. 2. clock rate 3. instruction count • Performance = 1 / execution • Execution Time = inst_count * CPI * 1/clock_rate Page 23 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Solution: C Amdahl’s Law When improving one item, you can only improve the total time by the fraction that task requires. Useful in choosing what part of a processor to improve. 4. Data paths and control sequencing Solution: B C. Memories and their hierarchies  In general, this is what the computer memory hierarchy look s like. Page 24 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes 1. Performance, implementation, and management 2. Cache, main, and secondary storage 3. Virtual memory, paging, and segmentation D. Networking and communications  1. Interconnect structures (e.g., buses, switches, routers) 2. I/O systems and protocols 3. Synchronization E. High-performance architectures  1. Pipelining superscalar and out-of-order execution processors Material in this section refers mainly to CS152/CS252. Almost all processors in desktop computers use these high-performance architectures. In order to see why we need more advanced processors, must identify weaknesses in the  pipelined processor. • Only executes 1 instruction per cycle. • Stalls due to data hazards. • Structural hazards Super-Scalar Processors Idea is to have more than one pipeline. Capable of executing > 1 instruction per cycle (theoretically). Page 25 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Here is an example of a super-scalar processor with 3 pipelines. It’s able to execute any three of  the execution stages as necessary. This processor has a maximum instructions per cycle of 3. Drawbacks: • Heavily increased forwarding and hazard detection logic • Still vulnerable to dependencies in instructions which cann ot be avoided w/o a time machine. Out-of-Order Processors (OOO) These are some of the most advanced processor designs that allow for instructions to be executed out of order. Basic Parts: • Instruction Fetch – Usually implemented as a queue of instructions to be executed. Works well with branch prediction. • Reservation Stations – These are the functional units such as adders, multipliers, dividers, floating point units etc… • Reorder Buffer – This is used to resolve dependencies. Because things can complete out of order, the reorder buffer makes sure an instruction isn’t committed until it is completed. Page 26 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Life cycle: Instructions are tossed from the instruction queue into reorder buffer and a reservation station or reservation station queue. The reorder buffer (ROB) holds the true ordering of instructions. Dependencies are resolved because when an instruction completes executing in a reservation station, the value of that computation is broadcast onto the CDB or Common Data Bus. This is read by the other reservation stations as well as the reorder buffer. When an instruction is complete at the bottom of the ROB, it is “committed.” Committing includes flushing to memory. Speculative Processors / Dynamic Scheduling In general, speculation terms of computer architecture is branch prediction. Because branches can cause unnecessary holes in a pipeline (especially if it is long), most processors will guess their result. The processor will proceed with this assumption at full speed until proven wrong. If   proven wrong, things get a little messy. Any instruction after a branc h must NOT be committed  back to the register file and definitely not to memory. In most pipelines, this results in a flush . Flushing the pipeline effectively nullifies instructions in the pipeline usually by replacing all the pipeline stage signals to zeroes. When wrong, branch prediction does about as bad as no branch prediction. However, when right, it keeps the pipeline full and throughput high. There are many kinds of branch prediction (global, local) that predict (in real world situations) at about 80-90% accuracy. Page 27 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Solution: C Efficiency = speedup / # processors = (T single_processor / T parallel_processors) / # processors T single_processor = 8 T parallel_processor = 4 Efficiency = (8/4) / 4 = 50% 2. Parallel and distributed architectures III. THEORY AND MATHEMATICAL BACKGROUND This makes up the largest section of the test. This covers: • CS170 – Introduction to Algorithms • CS172 – Computability and Complexity • CS174 – Combinatorics and Discrete Probability (Randomized Algorithms) These notes briefly address major subjects in theoretical computer science which are often tested on the CS GRE Subject Test. They do not address mathematical background, including some of  the material presented in CS170 on graph theory and number theory (which are both likely to appear on the GRE), nor do they address material that is rarely or never cov ered by the test (which includes a substantial fraction of Berkeley's CS170 and CS172, as well as e_ectively all of CS174). Acronyms: • BST – Binary Search Tree • DAG – Directed Acyclic Graph • DFA – Deterministic Finite Automaton • DP – Dynamic Programming Page 28 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes • PDA – Push-down automaton. • LP – Linear Programming •  NFA – Non-deterministic Finite Automaton •  NP – Non-Deterministic Polynomial Time • (ND)TM – (Non-deterministic) Turing Machine A. Algorithms and complexity  Asymptotic Growth  Notation • Upper Bounds: o O ( f ( n )) - grows at most as fast as  f ( n ) . o o ( f ( n )) - grows strictly slower than  f ( n ) . o g ( n) g ( n ) = O ( f ( n )) means lim n →∞  f ( n) is finite. Lower Bounds: o Ω ( f ( n )) - grows at most as slow as  f ( n) . o ω ( f ( n)) - grows strictly faster then  f ( n) . • o  f ( n) g ( n ) = Ω ( f ( n )) means lim g ( n) n →∞ is finite. Combined: o Θ( f ( n )) - grows asymptotically the same as  f ( n) . • o g ( n) g ( n ) = Θ( f ( n )) means lim n →∞ Θ(1) < Θ(log n ) < Θ(log1000 n) < Θ(n 0.001  f ( n) is finite and non-zero. n ) < Θ( n ) < Θ( n log n ) < Θ(n1000 ) < Θ(1.001n ) < Θ(2 2 ) Typical worst-case running times O(1) Hashes. Single operations; arithmetic fixed-length integers. Binary search in sorted list or BST. Search in unsorted list. DFS / BFS, bucket sort Quick/Shell/Merge sort. Dijkstra’s. Bubble, Insertion Sort. Some DP problems. (Edit Distance) O (log n ) O ( n) O (n log n) 2 O( n ) O( n ≈ 3 2.3− 2.8 O( n ) ) Clever matrix multiplication  Naïve matrix multiplication. Data Structures Important data structures you should know: Page 29 of 41 Eta Kappa Nu – Mu Chapter • • • • • • • • CS GRE Notes Graphs (cyclic, acyclic, directed, undirected) – G = (V, E). V: Set of vertices E: Set of edges. Priority Queues Make-Set, Find-Set, Union Binary Trees Linked Lists Hash Tables Solution: C Solution: D 1. Exact and asymptotic analysis of specific algorithms Sorting 2 • Bubble Sort – O( n ) . Stable. Sorts in-place. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list via the swaps. 2 • Insertion Sort - O( n ) worst case. O ( n ) best case. Stable. Similar to bubble sort, but is more efficient as it reduces element comparisons somewhat with each pass. An element is compared to all the prior elements until a lesser element is found • Merge Sort - O( n log n) worst and average case. • Heap Sort – In-place. O ( n log n ) . Unstable. The heap places an ordering upon elements added to it, so the largest elements will be placed at the top of the heap (we term this heap Page 30 of 41 Eta Kappa Nu – Mu Chapter • CS GRE Notes a max-heap ), or the smallest elements will be placed at the top of the heap (we term this heap a min-heap ). The heap data structure also allows us to perform the operation of  extracting the minimum or maximum element in the heap, reordering what elements are left in the heap. Radix Sort – O(n * k) where k is the average key length. Requires O(n) additional space. o take the least significant digit (or group bits) of each key. o sort the list of elements based on that digit, but keep the order of elements with the same digit (this is the definition of a stable sort). o repeat the sort with each more significant digit. Example: 170, 45, 75, 90, 2, 24, 802, 66 • sorting by least significant digit (1s place) gives: • 170, 90, 2, 802, 24, 45, 75, 66 • sorting by next digit (10s place) gives: • 2, 802, 24, 45, 66, 170, 75, 90 • sorting by most significant digit (100s place) gives: • 2, 24, 45, 66, 75, 90, 170, 802 • • 2 Quick Sort - O ( n log n) . O ( n ) in worst case. Unstable. The Quicksort algorithm uses a recursive divide and conquer strategy to sort a list. The steps are: 1. Pick a pivot element from the list. 2. Reorder the list so that all elements less than the pivot precede all elements greater  than the pivot. This means that the pivot is in its final place; the algorithm puts at least one element in its final place on each pass over the list. This step is commonly referred to as "partitioning". 3. Recursively sort the sub-list of elements less than the pivot and the sub-list of  elements greater than the pivot. If one of the sub-lists is empty or contains one element, it can be ignored. Bucket Sort – Solution: D String Algorithms Bloom Filters Page 31 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Graph Theory and Algorithms Shortest-Path Dijkstra’s Algorithm - O (VE ) . The algorithm works by keeping for each vertex v the cost d[v] of the shortest path found so far. Initially, this value is 0 for the source vertex s and infinity for  all other vertices, representing the fact that we do not know any path leading to those vertices. When the algorithm finishes, d[v] will be the cost of the shortest path from s to v or infinity, if no such path exists. Min-cut / Max-flow Theorem – The maximal amount of flow is equal to the capacity of a minimal cut. • Randomized Min-cut • Ford-Fulkerson Algorithm • Edmond’s-Karp Algorithm Minimum Spanning Tree • Kruskal’s Algorithm – O ( E lg V ) . Greedy. Starts with a forest which consists of n trees. Each tree, consists only by one node and nothing else. In every step of the algorithm, two different trees of this forest are connected to a bigger tree. In every step we choose the side with the least cost, which means that we are still under greedy policy. If the chosen side connects nodes which belong in the same tree the side is rejected, and not examined again because it could produce a circle which will destroy our tree. • Prim’s Algorithm – Only works on connected graph with positive edge weights. It  builds upon a single partial minimum spanning tree, at each step adding an edge connecting the vertex nearest to but not already in the current partial minimum spanning tree. 2. Algorithmic design techniques (e.g. greedy, dynamic programming, divide and conquer) Greedy Algorithms Page 32 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Algorithms that, at each step, do whatever looks best at the time. They work on a restricted class of problems, but tend to be very efficient when they do. E.g.: given a subspace of a vector space and a basis for it, just keep picking vectors out of the subspace that haven't been spanned by other vectors. GRE questions are unlikely to ask much more than definitions. Dynamic Programming Vaguely-defined paradigm of approaching a problem instance of size n by solving all possible smaller sub problems, building up from smallest cases to cases of size n. Common in string comparison algorithms, such as edit distance (UNIX diff), string alignment (e.g. in biology), longest common subsequence. Consider DP whenever the problem looks otherwise difficult, and the answer for any instance of size n depends on small (e.g. linear) number of instances of size < n. A typical question may sketch a DP algorithm and ask for its running time. Divide and Conquer A divide & conquer algorithm is one that, given a problem instance of size n, splits it into a cases of size n=b, recursively solves each of them, and then combines the results in f(n) time. Then, the running time T(n) of the algorithm is described by the recurrence relation T (n ) = aT (n / b ) +  f ( n) The Master Theorem fixes the asymptotic behavior of T as follows. log a log a If  f ( n) = O(n b − ) (for some ε > 0), then T ( n) = Θ( n b ) ε  If  f (n) = O( n log b a If  f ( n) = O(n log b a +ε  ) , then T ( n) = Θ( n log b a log n) ) , and af ( n / b ) /  f (n ) ≤ 1 for sufficiently large n, then T (n ) = Θ( f ( n)) Example problem: Solution: C Linear Programming A Linear Programming problem is a set of linear ine qualities and a real-valued “objective function" over a set of variables; a solution is a setting of the variables which maximizes (or  minimizes) the objective function while still satisfying all of the inequalities. The set of feasible solutions is a polyhedron in n-dimensional space (if there are n variables); it can be shown that an optimal solution can always be found at a vertex of the polyhedron (note that a 2-D  polyhedron is just a polygon). If an extra c onstraint is added that all variable may only take on integer values, the problem becomes “Integer Programming" (and solutions become restricted to grid points). Linear programs are solvable in worst-case polynomial time by a technique known as the ellipsoid method, but are in practice solved by the "simplex" method which is fast on average but is exponential in the worst case; solution of integer programs is, on the other hand,  NP-Complete. Many problems have natural representations as linear or integer programs. A typical question may ask you to solve a simple LP problem. Page 33 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Simplex Algorithm – Exponential in worst case but fast in practice. Stochastic, Probabilistic Algorithms Randomized Min-cut Heuristic Algorithms 3. Upper and lower bounds on the complexity of specific problems 4. Computational complexity, including NP-completeness Complexity Classes For any given function f(n), you can define classes TIME(f(n)), SPACE(f(n)), NTIME(f(n)), and  NSPACE(f(n)) of languages which can be decided by a Turing machine (deterministic & nondeterministic respectively) using O(f(n)) time and space , respectively (“space” refers to memory f(n) or the number of cells used on the tape.) It can be shown that NTIME(f(n)) ⊆ TIME(2 ) and 2  NSPACE(f(n)) ⊆ SPACE(f(n) ) (Savitch’s Theorem). Since non-determinism yields extra  power, TIME(f(n)) ⊆ NTIME(f(n)) and SPACE(f(n)) ⊆ NSPACE(f(n)) are trivial. More general k  classes are defined for large groups of functions. Specifically, P is defined as ∪ TIME(n ) – the set of all languages decidable in polynomial time by TM – and NP is defined similarly for   NTIME – the set of all languages decidable in polynomial time by a n NDTM; coNP is the set of  complements of languages in NP. PSPACE is defined similarly for polynomial space; and other  classes such as EXPTIME, NEXPTIME, and EXPSPACE for larger functions. NP-Completeness A language which is in NP and can be reduced  from any language in NP by a poly-time reduction is called NP-Complete, since deciding this langua ge in polynomial time would allow one to decide any language in NP in polynomial-time. Many well-known combinatorial  problems are known to be NP-complete. If you have a language A which is known to be NPcomplete, and a language B in NP which may or may not be NP-complete, you will show that B is NP-complete if you reduce from A to B, but not the other way around. Most NP-completeness questions in the GRE concern solely the direction of this reduction. Here are some examples of   NP-Complete problems you might encounter. • Traveling Salesman • 3-SAT, N-SAT – satisfiability. • K-clique – Independent Sets • Vertex-cover  • Hamiltonian Path/Cycle • Integer linear programming • Sub-graph Isomorphism Page 34 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Solution: E Solution: D B. Automata and language theory  1. Models of computation (finite automata, Turing machines) (Non-)Deterministic Finite Automaton ([N]DFA) / Regular Expressions A DFA (Deterministic Finite Automaton) is a set of states with transitions defined on them,  based on input which comes in form of symbols from an alphabet set. One state is distinguished as the starting state, and a subset of states are considered accepting states. Whenever you're at some state, the next symbol determines the exac t next state you move to. If the machine is in an accepting state after processing some finite sequence o f symbols (a string), it is said to accept this sequence. The set of string accepted by an automaton is the language of the automaton; the automaton is also said to recognize this language. An NFA (Nondeterministic Finite Automaton) is an automaton whose configuration at any point is a set of states rather than a single state; transitions from any given state on any given symbol can go to a set of states as well. Any NFA can be converted into an equivalent DFA, but sometimes at exponential cost. Any language recognized by a DFA or an NFA can also be described by a regular expression (and vice versa). Page 35 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Languages described by regular expressions (or recognized by DFAs) are called regular  languages. A condition known as the pumping lemma is often used to show that a language is not regular. Virtually always, a language is rendered non-regular due to its reliance on \counting" some aspect of the string; the standard example is the language of strings containing n a's followed by n b's. The most important feature of DFAs and NDFAs are that they have a finite number of states and finite alphabet. Consequently, you cannot use DFAs to do any kind of counting. E.g. you could not use them to detect when a string has the same number of 0s and 1s. A DFA is a 5-tuple, (Q, Σ, δ, s, A), consisting of  a finite set of states (Q) a finite set called the alphabet (Σ) a transition function (δ : Q × Σ → Q). a start state (s ∈ S) a set of accept states (A ⊆ S) Regular Expression for the above DFA is: 1*(01*01*)*  NFAs are an extension of DFA that also allow epsilon transitions. On an epsilon transition, the machine can be in either of those states (as seen above, the state of  an NFA is defined by the set of states it could possibly be in. The NFA accepts if there exists a Page 36 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes  path to an accepting state. Although they seem more powerful, the languages described by NFAs is exactly that of DFAs and Regular Expressions / Language s. Regular Expressions Regular expressions consist of constants and operators that den ote sets of strings and operations over these sets, respectively. Given a finite alphabet Σ the following constants are defined: 1. (empty set ) ∅ denoting the set ∅ 2. (empty string) ε denoting the set {ε} 3. (literal character ) a in Σ denoting the set {"a"} and the following operations: 1. (concatenation ) RS denoting the set { αβ | α in R and β in S }. For example {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}. 2. (set union) R U S denoting the set union of  R and S. 3. (star)R * denoting the smallest superset of  R that contains ε and is closed under string concatenation. This is the set of all strings that can be made by concatenating zero or  more strings in R. For example, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }. Typical question categories are: o Given this automaton, which of these regular expressions is it equivalent to? (or vice versa.) o Given this English-language description of a regular langu age, which of these finite automata or regular expression does it correspond to? o Given an automaton (or a regular expression), find the value of a property of the language it recognizes (or generates)? o Given these language, which is regular (or non-regular, remember the counting argument!) Push-Down Automata / Context-Free Languages If an NFA is also allowed to maintain a stack, with which it can perform either of the standard  push or pop operations at each processing step, the resulting machine is known as a PDA (Pushdown Automaton); PDA's can accept any language accepted by an NFA (can you see why?), but also some others. A language is accepted by a PDA if and only if it can be generated by a context-free grammar, defined as a set of non-terminals (or variables) and productions (or substitution rules) mapping single non-terminals to sequences of non-terminals and terminals (i.e. symbols in the alphab et); one non-terminal is designated as the start variable, and a string of terminals is said to be generated by the grammar if it can be derived from the string containing just the start variable by repeatedly applying substitution rules to replace non-terminals. Page 37 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes CFGs are typically heavily covered on the GRE (unlike PDAs). A version of the pumping lemma may also be used to show that a language is not recognizable by a CFG. Often, a characteristic of  such languages is their reliance on counting two independent quantities; a classical example is n n n a  b c . There are two kinds of push-down automata, PDAs and NPDAs. Usually when we speak of  PDAs, we’re talking about the NPDA or non-deterministic variety because standard PDAs cannot recognize all context-free languages. PDAs are basically DFAs fitted with an infinite stack which can be used as another variable (with the state and input) to be used to determine the next move. A NPDA W can be defined as a 7-tuple: W = (Q,Σ,Φ,σ,s,Ω,F ) where • • • • • • • Q is a finite set of states Σ is a finite set of the input alphabet Φ is a finite set of the stack alphabet * σ is a finite transition relation (Q × ( Σ & {ε}) × Φ) × ( Q × Φ ) s is an element of Q; the start state Ω is the inital stack symbol F is subset of Q, consisting of the final states. Two possible acceptance criteria, empty stack and acceptance in final state. They are equivalent in all respects. Below is an example NPDA which accepts the language of binary strings with equal number of  0’s and 1’s (impossible to do with DFAs) Typical question categories are: • Given this grammar, which of these strings does it g enerate; or given a string as well, how is it derived from the start symbol (what is its parse tree)? • Given this string, which of these grammars generate it? If substitution rules are allowed to map sequences of terminals and non-terminals to longer  sequences of terminals and non-terminals, a more p owerful class of grammars, known as CSG (Context-Sensitive Grammars) results; any language generated by a CSG is recognized by a Page 38 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes LBA (Linear Bounded Automaton). These entities are not well-studied, and are generally only addressed on the GRE by definition questions. Turing Machines If a DFA is allowed to write on an (1-way) unbounded tape and move back and forth on it, the resulting machine is called a Turing Machine, and is equally powerful to any other model of  computation known to be physically implementable. A Turing Machine is equivalent in computational power to, among other things, a Turing Machine with multiple (infinite) tapes, most cellular automata, and PDA's with 2 o r more stacks. Replacing the DFA with an NFA yields a Non-Deterministic Turing Machine, which can only reco gnize Turing-recognizable languages, but may potentially do so faster than a TM in some cases. It is believed that it is not  possible to physically implement an NDTM. • Three possible outputs for a TM: accept, reject or infinitely loop. • Any language recognized by a TM may be described by a Universal Grammar, which is identical to a CSG, other than for the fact that its rules are not constrained to map strings of non-terminals and terminals to longer ones. Any such language is referred to as recursively enumerable or Turing recognizable. • If the machine is guaranteed to terminate and reject any string it doesn't accept, it is said to decide its language, and its language is referred to as recursive or Turing-decidable. RAM Machine 2. Formal languages and grammars (regular and context free) Solution: A Page 39 of 41 Eta Kappa Nu – Mu Chapter CS GRE Notes Solution: E 3. Decidability See the Turing Machines section. C. Discrete structures  1. Mathematical logic 2. Elementary combinatorics and graph theory 3. Discrete probability, recurrence relations, and number theory Countability A set A is countable if it is either finite, or there exists a one-to-one mapping with N (natural numbers). Here are some examples: • Countable: o Even natural numbers. o Prime numbers • Uncountable: o All real numbers [0,1) o Power Set of N (or anything infinite) o Cantor Set Solution: D VI. OTHER TOPICS This section tends to be random questions from a range of fields including: Page 40 of 41