Cheatography

# CSCE-350 Midterm 2 Cheat Sheet (DRAFT) by EmperorMoose

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Heaps

 Heap has root either < || > all children. 10,6,8­,2,­5,7­,4,1, read in rows, 10-roo­t,6/8 is next row, right to left When replace node, always pick the bottom rightmost. Then heapif­y(look for cp) Topo sort = inverse of pop

### Hashing

 map a file size n into a table size m use f(n) Open Hashing: Each Cell is a header of linked list of all keys assigned to it Closed Hashing: One key per cell. In case of collision, either linear probing (find next available free cell) or Double Hashing Key Compar­isons = depth of keys AVG number = Σ1/n(d­epth)

### String Matching

 String Matching: Horspool: create a shift table with contains values for how far to shift if a match is found. Always start from the right. EX for BARBER B=2,A=­4,R­=3,­B=2­,E=1, ELSE 6 Beyer Moore: Same, but also create a table for the substring matches

### Facts

 Insertion Sort: Compare items sequen­tially Topo sort is DFS, record PopPush MergeSort O(nlogn) QuickSort O(n^2) Tree Traversal: Preorder: Ro,L,R­|In­ord­er:­L,R­o,R­|Po­st:­L,R,Ro| AVL Tree cannot have a height difference > 1