Final

Question 1

Hashing

Question 2

Collision

Question 3

Open Hashing

Question 4

Closed Hashing

Question 5

Linear Probing

Answer 5

Upon collision, proceed to next available cell or cycle back to the first cell if the last cell is reached.

Question 6

Linear Probing - Search

Answer 6

Search according to the hash function, and if another value occupies the expected cell, continue to the next until the expected value or an empty cell is found.

Question 7

Linear Probing - Problems

Answer 7

Does not work if n (values) > m (keys)
Deletions are not straightforward

Question 8

B-Tree

Answer 8

Aims to use the hard disk for storage as opposed to RAM. The memory only holds the addresses/pointers to the data.

Question 9

B-Tree Definitions

Answer 9

A B-tree of order m is an m way tree.
# of keys in each non-leaf node = number of children -1, and keys partition the children like a search tree
All leaves on same level
All non-leaf nodes except root have >= ceil(m/2) children
Root has up to m children
Leaf contains no more than m-1 keys.
M should be odd (so there is a middle key)

Question 10

Dynamic Programming

Answer 10

Solving problems defined by recurrences with overlapping sub problems.
ex: Fibonnaci sequence

Question 11

Coin Row Problem

Answer 11

Row of n coins with positive integer values (not distinct)
Pick up maximum money without picking adjacent coins. Solve with dynamic programming

F(n) = max{F(n-2) + nth coin, F(n-1)}

Question 12

Change Problem

Answer 12

Find the minimum number of coins to reach a total value n.

Question 13

Blocking pair

Question 14

Augmenting path

Question 15

Stable marriage problem