Minimum Spanning Trees Warm up: Given an undirected graph, how do we determine if it contains any cycles? We use DFS from any source vertex and keep going until we see a marked node. ...

BFS vs DFS DFS finds a path from some source to every reachable vertex. BFS finds a shortest path from s to every reachable vertex. Both efficiencies of the algorithms under an adjacency lis...

Prioritiy Queues A priority queue is another type of an abstract data type. It serves as a collection of items. We may add items to this bag and remove items, but we may only interact...

BFS, DFS, Graph Traversals and Implementations To implement any graph algorithms like DFS, we need: An API (Application Programming Interface) for graphs. Defines a...

Graphs and Traversals Tree Traversals is a means of iterating over the items within a tree. There are different orders that we may visit the nodes in. Main orderings Level Order: ...

Hashing II Two implementations for sets and maps RB Tree based approach: Requires items to be ocmparable and has logarithmic time operations. ...

Hashing The motivation behind hashing is that insertion, removal, and contain checks all occur in $O(1)$ time in the best case. This offers efficiency bonuses greater than that of the tree-bas...

Tree Rotations Inserting the same elements in different orders into a BSt produces different BST structures. A B-Tree equivalent of rotating left or right means to join the left or right child...

Tree Rotation We may reotate trees left or right to keep trees balanced. In fact, in any BST, it is possible to move to a different configuration using “rotation”. rotateLeft(G): let x be the ...

BST Tree Height Trees range from a best case of being “bushy” to worst-case being “spindly”. Bushy trees minimize the height to around log(N) where N is the number of nodes in the tre...