Anything from these chapters is fair game. I won't ask you nit-picky specifics or esoteric constructs, but I do expect you to know main concepts. For example, I might ask you to write code doing something that required a struct. In this case, I wouldn't take points off for not putting a semicolon at the end of the struct, but you should have the general format of a struct statement correct.

Also, make sure you understand the major differences between Java and C++.

I won't ask you for specific UNIX commands, but you should understand the UNIX concepts discussed in class. On the class web page in the "Other Resources" section, look over the "UNIX Overview."

Required Reading: 4.7 in DS book (B-Trees)

Optional Reading: Ch. 1-4 in DS book

Concept of an ADT [3.1]

Lists, Stacks, Queues (definitions, common operations, properties) [3.2 - 3.4.1]

Applications of a Stack: [3.3.3]

Balancing Symbols

Evaluating Postfix Expressions

Converting Infix to Postfix

Stack in a Compiler

Implementations of a Stack (analyzing various implementations) [3.3.2]

Big-Oh (informally) [2 -- but you don't need to know this much detail -- that's for Comp122!]

Context-Free Grammars (definition, terminology, what strings does this grammar produce?) [class handouts]

Chomsky Normal Form/Modified Chomsky Normal Form [class handouts]

General Trees (terminology) [4.1]

General Tree Implementations [class handout, 4.1.1]

"First Child/Next Sibling representation"

Traversals [4.6]

Binary Trees (definition, terminology) [4.2]

Expression Trees [4.2.2]

Binary Search Trees (terminology, operations) [4.3]

Recursion [1.3]

AVL Trees [4.4]

Splay Trees (optional -- won't be covered on test) [4.5]

B-Trees [4.7]

Shift-Reduce Parsing [Proj 1 handout]

An Alternate Operator Precedence Parsing Algorithm [Proj 1 handout]