Notes for my data structures final, now taught as COMP 210.

```Everything we covered:

Efficient implementation of ADTs
Math background
Proofs - by induction
Recursive programs and their analogies

Linear ADT’s - lists, stacks, queues, dequeues
array and linked implementations

Priority Queues
heap implementation

Sorting - run time - O(n), O(nlogn) memory - in place / not
Heapsort
Insertion sort
Merge sort

Dynamic Dictionaries
Binary trees
BST
Balanced BST’s
AVL tree
Hash Tables
Chaining
Probing - quadratic, double hashing, cuckoo hashing

Graphs
Definitions
Representation
Topological sort/cycle detection

Needs some review:

O(n) is similar to <= (grows no faster than a given function. So this is an upper bound.)

Omega(n) is similar to >= (grows at least as fast as a given function. So this is a lower bound. )

Theta(n) is similar to == (grows at the same rate. This is true if both O(n) and Omega(n) is true).

Secondary hashing is when you have another has function, and if you hit a collision, you hash in accordance to i*that hash function where i increments. It’s sort of like probing but with a hash function as the basis instead of just a number.

Cuckoo hashing is having the items bounce back and forth between two tables, based on independent hash functions.

An algorithm for top sort is just start with the node that doesn’t depend on anything, and then do it, and then decrement the in degrees of all the nodes that it connects to, and then do it again until everything’s done.

————————————————————————
How to do rotations? Just memorize.

Primary and secondary clustering, how to think about it?

Heaps: where you have every node is smaller than its children. Fill in from left to right, making switches when appropriate. When you delete from the top (which is the only place you can delete from), you take the last node that you put in, put it at the top (in the new hole), and then percolate down.

```