Notes for my data structures final, now taught as COMP 210.read more
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 Adjacency Matrix Adjacency List 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.