CPSC 131 - FINAL EXAM Study Guide

Edge List Space Time Efficiency

O(n + m)

Edge List v.incidentEdges() Time Efficiency

O(m)

Edge List v.isAdjacentTo(w) Time Efficiency

O(m)

Edge List insertEdge(v, w, o) Time Efficiency

O(1)

Edge List insertVertex(o) Time Efficiency

O(1)

Edge List eraseVertex(v) Time Efficiency

O(m)

Edge List eraseEdge(e) Time Efficiency

O(1)

Edge Lists verticies() Time Efficiency

O(n)

Edge Lists edges() Time Efficiency

O(m)

Edge List e.isIncidentOn(v) Time Efficiency

O(1)

Edge List e.endVertices() Time Efficiency

O(1)

Edge list e.opposite(v) Time Efficiency

O(1)

Adjacency List Space Time Efficiency

O(n+m)

Adjacency List v.incidentEdges() Time Efficiency

O(deg(v))

Adjacency List v.isAdjacentTo (w) Time Efficiency

O(min(deg()v, deg(w)))

Adjacency List insertVertex(o) Time Efficiency

O(1)

Adjacency List insertEdge(v,w,o) Time Efficiency

O(1)

Adjacency List eraseVertex(v) Time Efficiency

O(deg(v))

Adjancey List eraseEdge(e) Time Efficiency

O(1)

Adjancey List verticies() Time Efficiency

O(n)

Adjacency List edges() Time Efficiency

O(m)

Adjacency List e.isIncidentOn(v) Time Efficiency

O(1)

Adjacenccy List e.endVerticies() Time Efficiency

O(1)

Adjacenccy List e.opposite() Time Efficiency

O(1)

Adjacency Matrix Space Time Efficiency

O(n^2)

Adjacency Matrix v.incidentEdges() Time Efficiency

O(n)

Adjacency Matrix v.isAdjacentTo (w) Time Efficiency

O(1)

Adjacency Matrix insertVertex(o) Time Efficiency

O(n^2)

Adjacency Matrix insertEdge(v,w,o) Time Efficiency

O(1)

Adjacency Matrix eraseVertex(v) Time Efficiency

O(n^2)

Adjacency Matrix eraseEdge(e) Time Efficiency

O(1)

Adjacency Matrix vertices() Time Efficiency

O(n)

Adjacency Matrix edges() Time Efficiency

O(1)

Adjacency Matrix e.isIncidentOn(v) Time Efficiency

O(1)

Adjacency Matrix e.endVerticies() Time Efficiency

O(1)

Adjacency Matrix e.opposite(v) Time Efficiency

O(1)

Rooted Tree

Where each node can be traced back to an ancestor node right at the top, or ROOT node

Ancestor Node

The node prior to the observed node, or the primary node at the top, A node on the path from the root to n

Rootless Node

No common ancestor is shared, and you cannot find a common root.

Child Node

Lowermost node in a binary search tree, or AVL tree

Parent Node

Node directly observed above the child node, A node, including the root, which has one or more child nodes connected to it.

Grandparent Node

Node directly observed above the parent node of a child node, this process continues upward until the root/ancestor node of the observed node.

Balanced Tree

A tree in which the right and left subtrees of any node have heights differing by 1 at most. Of whose lowest nodes have a BF of 0, and whose root has a BF of 0 to 1 at most.

O(log2n)

Logarithmic time; each step of the algorithm cuts the amount of work left in half. The common time efficiency of trees. The further right you go, the more flat the outward angle becomes, its more efficient as the data set grows.

Binary Tree Requirements

It needs to be a rooted tree, and EACH NODE must have either 0 or 1-2 direct children. A node cannot have more than 2 children. Also note that sibling nodes are not connected, only parent-child nodes.

General Rule for Binary Trees

If the value that you're adding is less than the value of the node presently examined, it goes to the left as a Left Child, if it's greater than the node presently examined, it goes to the right as a Right Child.

Sub-Tree

If you're looking at a specific node, and observing something like its BF alone, separate of the tree, it is a part of a tree that could be considered a tree itself if separated

Logarithmic Time

O(log2n). Or Log Base 2 of N, reducing the amount of observations through a set of data

Imbalanced Tree Time Efficiency

An Array at O(n), it's a valid binary tree, each node has at least one child, and the lowest child node would have a BF of 0. But it's imbalanced, it would have a speed of O(n), with an extremely long branch, it's an SLL in all but name.

Balance Factor

A property of a node that is computed by subtracting the height of the left subtree from the height of the right subtree via absolute value, if the BF is more than 1, then it's an imbalanced tree.

Data Poisoning

When a Binary Tree doesn't balance itself, which is then sent a string of linear data. Effectively attempting to disrupt the Binary Tree itself.

Can a Valid Binary Tree be empty?

Yes, if there's no root node, its null, so you'd add a node. But even then without any nodes, you could technically say this "tree" has a BF of 0, so it's balanced.

Depth of Node

The length of a path from the root/greatest-ancestor node to the lowest node. Say we had a SLL of 1, 2, 3, 4, Node 4 would have a depth of 4, and so on for example.

Arithmetic Expression Tree

Essentially a tree that is used to calculate an arithmetic expression, where some nodes would constitute as the operands. Note that you go from the lowest node on each side upward.

Traversing Trees

Traversal visits the nodes of a tree in a systematic manner, all of which are effectively algorithms, with three different forms of movement.

Preorder Traversal

The Parent Node/Root Node goes first, and the children go in order from the Left Node to the Right Node.

Inorder Traversal

Where the Parent/Root Node comes between the children in order. Left Node, Root Node, Right Node.

Postorder Traversal

Where the Parent/Root node goes after the children nodes. Left Child, Right Child, Root Node.

p.left() and p.right()

Returns left or right node on a tree/BST or AVL

p.parent()

Returns parent node

p.isRoot() / p.is_leftChild()

Returns boolean result to determine if the node IS the left Child, similar process for right Child, and root Node.

p.isExternal()

Determines if the node at the end of the root/branch is indeed an external child node

Perfect Tree: efficiency O(log2n)

all internal nodes have 2 children and all leaf nodes are at the same level of depth

Complete Tree

All levels, except possibly the last level, are completely full, and all nodes in the last level are as FAR LEFT as possible, A tree in which there are no missing nodes when looking at each level of the tree. The lowest level of tree may not be completely full, but may not have any missing nodes. All other levels are full.

Full Tree

Every node has 0-2 children, A tree in which every level of the tree is completely full, with no missing nodes.

std::map

A key-value based storage system, a data structure that runs a tree under the hood within a c++library

Key Data Type

1st part of a Map set, where this data type acts as the accessor to the value within the pair.

Value Data Type

2nd part of a Map set, where this data type, of any kind, is accessed by the Key.

Does STD::MAP have the speed of a Tree?

Yes, by retrieving assets via Key/Value pairs, accessing assets/data can be done with the speed of a tree.

Applications for STD::MAP

Think of a phone book, or a catalogue, rolodex, or an indexing system where data types of varying specifications are managed through a specific key, a Template possibly.

How do you populate data into the MAP

By adding to value area.

Address a;

Aline1 = "Address"

Acity = "FULLERTON"

Azipcode = 939432;

// Everything above this is the value.

Something like string name - "Tom Titan" would be the key.

In order to assign it, it looks like this.

myRolodex[aname] = a;

So variablename[stringname] = assigned data

Accessing

Address a;

String aname = "Tom Titan";

A = myRolodex[aname]; //Assign the data to the appropriate key

cout << aname << " is at "l

cout << a.line1 << a.line2 << a.city << a.zipcode <

Searching a Map

In the event a key isn't there, std::map is from the STL, meaning it has helper functions, the find helper functions is particularly useful.

EX: if (myRolodex.find(aname) == myRolodex.end())

{

// aname is not in the map

}

Else {

Address a;

a = myRolodex[aname];

cout << aname << " is at "l

cout << a.line1 << a.line2 << a.city << a.zipcode <

Erasing A value in a map

myRolodex.erase(it);

In this example, it requires you send it an iterator

Prior to that you'd need to find it

string aname = "Tom Titan"; //You are removing the value

map

myRolodex.find(aname);

If (it == myRolodex.end()) {

Then there isn't the name in the map

else

"myRolodex.erase(it);"

AVL Tree

A BST with a few extra rules to make sure it's balanced, A self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1.

AVL Tree Time Complexity

Roughly at, or slightly less fast O(log) speed. "Not log time, but close enough to log time." Faster than O(n) time.

AVL Insertion

Similar to a new key-value insert as in a BST , and is always done by expanding an external node. As soon as you insert a node though, it will trigger a maintenance helper function to balancer the BF if it has a BF of 2, O(logn)

Z-Node

In structure portion of the AVL tree, say we generate a tri-node called x,y,z, and each node has an assigned value, 62, 50, 78, note that this is an unbalanced sub-tree, so it would then be reorganized into 50,62,78.

Single Rotation

One rotation is needed to rebalance the subtree, from here there are two variations, Single Left Rotation, and Single Right Rotation. Often rebalancing a tri-node that was originally a straight line.

Double Rotation

Two rotations to either the left or the right depending on visual identification, where the node that can balance the tri-node structure would typically be at the bottom. Rotated upward in either a double right, or double left rotation.

AVL Single Restructure Time Efficiency

O(1), in worst case it's O(n) depending on the size of the tree itself.

AVL Find Time Efficiency

O(log n) Remember that only a perfectly balanced tree with give you O(log n time), and an AVL tree can be CLOSE to log time, but not exactly. Keep an eye on this during the exam.

If you're given a tree and asked if it's a valid BST and AVL, int his case you'd say yes, but if asked for time complexity...

Do NOT select O(log n) time, it'd be slightly worse

Select "Close to Log Time" or significantly faster than Linear Time, whichever is the closest rough approximation.

AVL Put Time Efficiency

O(log n) time. Similar to Find, but this is an alias for insert, if we assume the tree is AVL, the cost to balance it would be O(log n), with each iteration being O(1)

Again, roughly, the end result is O(log n) time, if he says "exactly", its log time, if he doesn't specify or say "roughly", it's not log time.

AVL Erase Time Efficiency

O(log n), simple as that.

Hash Functions

A function that should produce output data that's difficult to predict, without collisions, with different input data. An example we've been using for a while is modulo (%)

Abstract Hash Function Example

By function alone, there is an input, and an output

We want to mess with the input, and get deterministic output

Step 1. Invert all Bits

Step 2. Reverse all Bits

Step 3. Invert the first Bit (again)

Step 4. Keep only the last, smallest TWO, Bits

//This isn't a good hashing function, but it is a VALID one.

Input Pattern: 1011

Applying rule 1, we invert the bits: 0100

Applying rule 2, we then flip it: 0010

Applying rule 3, we invert the first bit: 1010

Applying rule 4, we then keep only the smallest two bits: 10

The final answer after this hashing function, is 10.

If you did all 1's: 1111

1: 0000

2: 0000

3: 1000

4: 00

Hash Function Applications

Typically security applications, if you make a more sophisticated set of instructions for your hash function, you'd make something that makes it really hard to predict the output, or difficult to insert poison data. DO NOT USE MD5.

Deterministic with Hashing Algortithms.

Fixed and known in advance, representing a high level of certainty when planning. These should be able to result in similar outputs, essentially that the hash should be its own unique finger prints.

Things not to use for Hash Tables

Vectors or STD::Maps, the thing is that hash tables are faster than amps, if you implement a map it's going to be much slower. These should be self-sufficient functions for the most part above the hood.

Your employer asks if the function implemented should be a Tree, or a Hash Table, what are the base arguments for either?

Binary Search Trees are great provided that they're perfectly balanced at exactly O(logn) speed. Hash Tables run O(1) provided they're not too overloaded, the trade off is in regards to speed and organization. BST and Trees in general will output your data in alphanumerical order, and keep things in order when being ran, however it means we're moving at a slower speed, if we ignore order and go for the deterministic hash table, then we go faster while sacrificing order.

Keep in mind that the more input a Hashtable gets, the slower it becomes, and this would apply for Trees as well, the more unbalanced it becomes, the slower it gets. Both resulting in a worst case of O(n).

Say we have a hash table, no collisions, what's the time efficiency of getting or setting?

O(1)

Say the hash table has some collisions, is this technically O(1) time knowing there's some collisions, but not 0, what's the time efficiency?

The Best answer isn't O(1) time, it's close to it, or "it depends on how overloaded it is, the less, more to O(1), if it's more, more to O(n)"

Hash Table Load Factor

Estimate of how slow your hashtable is operating

If it's 0.1, it's about a 10th full, if it's a good function, that hash function is close, if not AT, O(1) time

Or if you have a load factor of 1

Each table has an item of 1, then it'll increase the number of collisions as you add more items

Or if it's an LF of 10, then that's a HEAVY load, and VERY SLOW

Each row has 10 items, so LOTS of collisions.

-gives a sense of how full a hash table is. It's also the expected length of a chain (if we're using chaining)

load factor less than 1 => mostly empty spaces, wasting space

load factor more than 1 => collisions

α = n/m (m => table size, n=> elements)

-as long as you set you're table size to m=n, we are guaranteed O(1) operations

Load Factor Applications

Make it a member variable of the class

Adding 1 item to the HT increases the size

Capacity is, again, the amount of rows at any given time

Maybe call a help function to recompute the load factor

Possibly call change capacity

Make any rule you want to really

".66, so if the HT has .66 or worse, call ChangeCapacity to increase the capacity"

What should the LF be in this situation: Your employer asks where it would be appropriate to apply a Load Factor

If you have spare memory, why not cut off the LF lower so the HT is really fast. Sacrificing memory for more speed

On the other hand, if your office has a budget or maxed server, not a lot of spare memory?

In this case, make the cut off of LF a little higher

The speed can take a hit for the sake of preserving memory, unless you REALLY have to

LF cut off would be a 2

Load Factor Exam Probability 2

What's acceptable, to save memory and sacrifice speed?

Or sacrifice memory if it's available for the sake of speed

The LF won't resize until each row has about 20 elements into it, it'll be slow but it can save some memory

Might waste some, but not as much if it were to go faster

General LF

Call a function that loads the LF

Calls a function that might change the capacity of the table depending on the LF

Same with decreasing the capacity

"There's a low bound to the LF"

If LF is above a cut off point, the table is slow, resize, change capacity

If the table isn't used, or the LF is low, then we change the capacity to make the hash table smaller to save RAM

Built in trade-off

Where do we put the maintenance functions?

When adding or remove, update the LF, and possibly change the capacity if it's below a threshold.

Something of a similar approach to the vector

LF isn't on the project, Load Factors are on The Final Exam

Or just, count the number of collisions in the table

Hash Table Collision

-two different inputs generate the same hash value/index

-fixed via chaining, open addressing, or double hashing

Decreasing Collisions

Collisions can be decreased provided that a slot in the hash table is beyond 1. Meaning that if only 1 unit is inside the Linked List of a particular slot, nothing is being collided into since the spot is filled. Same if the slots would just be empty, if nothing is there, then no collisions are there.

On the other hand, if there is more than 1 unit within a given LL of a slot, then a collision may occur.

Collision Shorthand Rule of Thumb

If the number of collisions is equal to your capacity, it's slowing down.

This is dependent on how you set the Threshold, the LF.

For each time you do an addition to the Hash Table, update the number of collisions, same if you decrease from the HT.

Changing Capacity of a Table

You'd effectively have to make a new table. Make a temp iterator, iterate through each slot and linked list (size_t for outer, iterator for inner), and copy everything over to the resized table.