Symbol Table

Question 1

what is the pair of things that a symbol table is made up of

Answer 1

key

value

Question 2

why can keys not be allowed to be null

Answer 2

because get() will return null if the key isn’t present

Question 3

should keys be changed once they’ve entered the abstract data type

Answer 3

no

Question 4

basic methods that should be included in a basic symbol table APi

Answer 4

void put(key key, value val)
value get(key key)
boolean contains(key key)
void delete(key key)
boolean isEmpty()
int size()

Question 5

what types can keys and values be

Answer 5

any generic type so long as they are comparable

Question 6

what three requirements make up equivalence relation

Answer 6

reflexive
symmetric
transistive

Question 7

what does it mean if two objects are reflexive

Answer 7

x.equals(x) is true

Question 8

what does it mean if two objects are symmetric

Answer 8

x.equals(y) iff y.equals(x)

Question 9

what does iff mean

Answer 9

if and only if

Question 10

what does it mean if two objects are transistive

Answer 10

if x.equals(y) and y.equals(z) then x.equals(z)

Question 11

what does it mean for an object to be non null

Answer 11

x.equals(null) is false

Question 12

default equality test in java

Answer 12

x == y

Question 13

why is the deafault equality test not the optimal way to compare

Answer 13

compares references to objects, returns true if both variables point to the same object, otherwise false

This may not always be what we are seeking

Question 14

How to speed up big compares

Answer 14

compare fields most likely to differ first

eg in dates, compare days before years

Question 15

standard recipe for user-defined compare methods

Answer 15

reference equality?
check against null?
check that they are of the same type and cast?

Question 16

additional methods that can be found in an ordered symbol table

Answer 16

min
max
floor(key)
ceiling(key)
rank(key)
select(key)
deleteMin()
deleteMax()

Question 17

what does ceiling return

Answer 17

smallest key greater than or equal to the passed key

Question 18

what does floor return

Answer 18

the largest key less than or equal to the key passed