The Worst Topics Flashcards
What order does pre order tree traversal go in?
N L R
What order does in order tree traversal go in?
L N R
What order does post order tree traversal go in?
L R N
Name this notation and the traversal required to get this
2 + 3
Infix
In order traversal
Name this notation and the traversal required to get this
2 3 +
Reverse Polish
Post order
Name this notation and the traversal required to get this
+ 2 3
Polish
Pre order
What is open addressing?
Use hashing to find a candidate bucket, have a strategy to remap colliding keys and find them afterwards
What is secondary hashing?
Use a second hash function to pick the bucket, if there is still a collision, then revert to linear probing
What is linear probing?
Walking along the bucket until you find a free space to place the key/value pair
What is separate chaining?
The bucket is a list of key/value pairs. We hash to the bucket and then add it to the list at the position.
What is extendable hashing?
Process of splitting the bucket, consuming another bit of the hash code, and placing values in the newly split parts of the bucket
What features do we want from a hash function?
- Two keys that are close together, map far apart
- Low chance of two keys mapping to the same value
- Spread of the keys across the hash bucket
Describe the parsing pipeline
Source Text
Tokeniser
Parser
Parse tree
Describe the process of tokenising using a FSA
Tokenise the input source, generating a steam of tokens for the grammar, some tokens can carry values with them
FSA keeps track of the characters used, attaches them to the recognised symbol
Describe the process of recursive descent parsing
Treats each production as a small recogniser that looks at the token stream and tries to recognise itself
Try it and see it method
What is the job of terminal recognisers in recursive descent parsing?
Check if the current token in the token stream is the expected one
What is the job of non terminal recognisers in recursive descent parsing?
Checks compound patterns, repetitions etc and saves and rewinds the token stream
What are the four functions needed for recursive descent parsing?
nextToken()
advanceTokenStream()
getTokenStreamPosition()
setTokenStreamPosition()
Describe the process of table driven parsing
Start with the tokens, see which productions could have given rise to them
Build the tree as a constraints problem
What are the advantages of table driven parsing?
- Smaller and faster
- No need for back tracking
What are the disadvantages of table driven parsing?
- Less clear
- Can be tripped up easily
Describe the divide step in a divide and conquer algorithm
Take a problem S and split it into two smaller problems S1 and S2
Describe the recurse step in a divide and conquer algorithm
Recursively solve S1 and S2, either directly (the base case of the recursion) or by further division
Describe the conquer step in a divide and conquer algorithm
Combine the solutions to S1 and S2 into a solution to S
Define polymorphism
Some values and variables may have more than one type
What are the two categories of polymorphism?
Ad hoc and Universal
What are the two types of Ad hoc polymorphism?
Overloading
Coercion
What are the two types of Universal polymorphism?
Inclusion
Parametric
What are the advantages of polymorphism
- Allows methods to perform similar tasks accessed under a common name
- Allows you to define multiple constructors
- Less repetition of code
Describe overloading polymorphism
Same function name is used to denote different types, operators can be applied to operands of different types e.g. +
Describe coercion polymorphism
Instance of one type forced to be interpreted as another e.g. if * could only be applied to real numbers, int types converted
Describe inclusion polymorphism
Instance of a subtype can be manipulated as if it was an instance of the supertype
Describe parametric polymorphism
Code features an implicit or explicit type parameter, coed can be used for value of any suitable type, does not depend on value at run time
Describe the collections framework
Unified architecture for representing and manipulating collections
Contains algorithms, interfaces and implementation
Benefits of the collections framework
- Reduced programming effort
- Reliable and optimised
- Standard interfaces, so less to learn
- Implementation of each interface interchangable
What are the three design goals of the collection framework
- Produce a reasonably small API (size and conceptual weight)
- Small number of core interfaces
- Only have methods if they are truly fundamental or there is a compelling performance reason
Describe a factory
A factory is an OO design pattern that deals with creating objects without specifying the exact dates of object that is to be created
What are the benefits of using factories?
- Allows for a lot more long term flexibility, able to easily change application
- Makes your code more testable, can mock interfaces and decoupled design
- Makes rest of code easier to write, modify and maintain
What is a parse tree?
Illustrated, pictorial version of the grammatical structure of the sentence.
Diagrammed form of a sentence, and gives an concrete idea of the syntax of that particular sentence
