Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structures and Algorithms (Trees (Heap Tree - The highest priority…
Data Structures and Algorithms
Sorting
Selection Sorting - Finds the smallest element and replaces it with the element in index 0, then next smallest and index 1 etc.
Radix Sort - Sorts items into "bins" by evaluating a first piece of data eg. day, then sorts the individual bins by a second set of data eg. month.
Stability - If 2 items of the same value are sorted, the algorithm is stable if it sorts them into the same order they were originally.
Data Types
Doubly Linked List - A list which can be iterated both directions, because 2 pointers are used. One points to the next element, 1 to the previous.
Priority Queue - A queue which is ordered by each item's priority.
Trees
Balancing BST's
B-Trees - A tree where multiple values are stored in each node. The parent node will have values which act as separators for its children.
Binary Search Tree - Elements are ordered by the lowest on the farthest left branch.
Quad Tree - Each node has either 0 or 4 children. Used for grey scale pictures where each node has a value from 0 to 255.
Heap Tree - The highest priority item is at the root of the tree, with the lowest ones as roots. Each level must be full before moving down to the next level.
Inserting elements - they are first added as the next leaf, then bubbled up.
Deleting elements - the node is replaced with current lowest leaf node, then bubbled down.
Creating from a list - The tree is created from the list in the order they occur. The tree is then bubbled up.
Binomial Heap Tree - A collection of trees, ordered by their priority, except build for efficiency of sorting and searching. When 2 trees of the same size are reached, they are combined to go up to the next tier.
Hash Tables
Buckets - Each position in the hash table is an array of values. So adding a value to the same position just appends to the array. Fast and easy but uses uneccesary memory.
Direct Chaining - When adding to a spot thats already filled, the item is added via a linked list. Slightly slower to find but is much better for memory.
Linear Probing - If the slot is already filled, then it looks for a previous empty spot. Is very efficient for memory but makes searching much less efficient and difficult. Becomes less efficient the more filled up the data structure gets.
Double Hashing - A version of linear probing that uses a second hash function to find a space when the target space is filled. Eg. If an item is hashed to 3, it will try to put it 3 spaces down until it finds one. Avoids clusters.
Definitions
Invariant - A condition that does not change during execution of the program. Eg. i > 0.
Graphs
Dijkstra's - Finds the shortest path from a to b by finding the shortest route to each other node first.
Prim's - Finds the smallest spanning tree between all nodes. It does this by picking the smallest arc and then the next smallest arc which is connected to the already existing tree, avoiding loops.
Kruskal's - Same as prim's except it will use the next smallest arc on the graph, avoiding loops until every node is linked.
Connectivity - A graph is said to be connected if all nodes of the graph can be reached.
Planar - The graph can be drawn with no arcs crossing over each other.
