Unformatted text preview:

UNC CH COMP 410 Topics covered on Second Midterm The Second Midterm exam will cover this material This is a guide not a guarantee The exam covers all material we have discussed in class up to and including Binary Heaps and Priority queues This means material from Midterm One is included as well as all concepts covered in the assignments and code we have written The following is a list of topics included in this material Topics from First Midterm And new Topics Basic Tree Terminology n ary tree a tree where every node has at most n children arity the number of children present on the node with the most children binary tree special form of n ary tree where every node has at most 2 children 0 1 or 2 children alternately a tree of arity 2 complete binary tree A binary tree in which every level except possibly the last is completely filled and all nodes all leaves are as far left as possible a binary heap structure is a complete binary tree full binary tree sometimes called a proper binary tree A tree in which every node other than the leaves has exactly two children perfect binary tree A binary tree in which every internal node has exactly two children and all the leaf nodes are at the same deepest level A perfect binary tree with height h has the maximum number of nodes that can be in a binary tree of height h perfect binary tree A no room for more nodes without increasing height of tree B C D E F G H I J K L M N O complete binary tree A every level but last is filled perfect and last level is left packed B C D E F G H I J K L full binary tree A every node not a leaf has 2 children every node has 0 children or 2 children B C D E J K Sets and Maps ADT ops behavior and ways to implement them lists trees hashing etc Hashing Hash Tables Hash Maps Pigeon hole principle chicken hole principle Hash Table hash function how to pick table size how to make an effective hash function what to do about collisions hash into linked lists or other collection data structures table size should be prime and same the size as elements expected probing to find an open cell in the table linear probing function quadratic probing function expo probing function table size should be prime and twice the elements expected Rehasing to extend the table size Hash Maps storing associated information object along with a hashed key Blockchain SHA 256 Cryptographic hash function basic block chain construction and operation nonce mining what it is how it s done complexity of the hashing used in mining blocks for Bitcoin application binary heap a binary heap is a completely different thing from the runtime heap runtime heap is not heap structured not related at all just unfortunate and maybe a bit confusing to share the name heap binary tree with two properties heap order property structure property always a complete binary tree with last level being filled from L to R but perhaps not full representation of binary heap as array heaps can be Min or Max operations getMin Max O 1 worst avg since it is at the root of the heap tree removeMin Max O log N worst case O log N average case add O log N worst case O 1 average case 75 of the heap elements in last 2 tree levels incElt decElt cost of searching for the Elt then plus cost of rearranging the heap array when the priority is incremented or decremented searching the array linearly is O N using a HashMap like Assn 4 is O 1 cost of rearranging the heap array in O log N build simple way is O N log N by doing N adds cleaver way is O N if you have all the elements on hand use special build priority queue limplementing priority queue with list BST implement priority queue using binary heap elements stored have value and priority priority is used to put elements into binary heap operations enq add item to PrQUE deq take item out of the PrQUE and that item is highest or lowest priority front produce element from queue that has highest or lowest priority size empty etc Sorting we have discussed and analyzed these sorting methods Bubble Sort rearranging the items in an array list to put them in order gold standard of badness since it s O N 2 worst case as well as avg case keeping a basic List sorted using inSort operation BST sort build a binary search tree and do in order traversal worst case analysis and average case analysis AVL sort BST with balancing avg and worst cases for sorting N elements sorting using hashing bucket sort Sorting with a binary heap heap sort special build a binary heap do repeated getMin delMin to create the ordered sequence worst case time complexity if we do repeated insert to construct heap worst case time complexity if we do special magic build to construct heap Tree representations linked cells implicit as array We have represented a tree binary tree as linked cells basic unbalanced BST also used for balanced methods like AVL Splay array binary heap in array representation the links are implicit and are obtained via array subscript arithmetic know why implicit array representation works ok for binary heap not for general case of binary tree Balanced BST Tree balancing AVL imbalance condition rotations to re balance rotations alter tree structure but maintain the order property worst case time complexity for insert remove contains show how AVL tree is altered by insert remove Splay another approach to balancing splaying done any time a node is accessed splaying is applying preserving rotations until accesses node is moved to the root amortized worst case time complexity show how splaying works in a tree for insert remove find etc


View Full Document

UNC-Chapel Hill COMP 410 - Midterm 2

Documents in this Course
Load more
Download Midterm 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?