COP3503C - Computer Science 2 - Exam 2 Review

What to do after BS Tree Deletion - Successor Rule (Swapping out with nearest greater value and deleting node after changing into leaf position) and other things too. :)

Case 1 (x’s sibling is Red)

1. Change x’s sibling w color status to Black.

2. Change x’s parent color to Red

3. Perform a rotation on x’s parent in the direction of x.

4. Reassign w to the new sibling of x (x stays in the same place.)

Case 2 (x’s sibling is Black, and its children are both Black)

1. Change x’s sibling w color status to Red

2. Reassign x’s pointer to x’s parent.

Left Case 3 (x’s sibling w is Black, w’s left child is Red, and w’s right child is Black)

1. Change x’s sibling w left child color status to Black.

2. Change x’s sibling w color status to Red.

3. Perform a Right rotation at w.

4. Reassign w to the post-movement child node that w used to occupy.

5. Proceed to Left Case 4.

Left Case 4 (x’s sibling w is Black, w’s right child is Red)

1. Change x’s sibling w color status to the parent.

2. Change x’s parent color status to Black.

3. Change w’s right child color status to Black.

4. Perform Left Rotation on x’s parent.

5. Reassign x to point to the root.

Right Case 3 (x’s sibling w is Black, w’s right child is Red, w’s left child is Black)

1. Change w’s left child color status to Black.

2. Change w’s color status to Red.

3. Perform Right Rotation on w.

4. Reassign w to the post-movement child node where w used to occupy.

5. Proceed to Right Case 4.

Right Case 4 (x’s sibling w is Black, w’s left child is Red)

1. Change w’s color status to the parent.

2. Change w’s parent color status to Black.

3. Change w’s left child color status to Black.

4. Perform a Right Rotation on x’s parent.

5. Reassign x to point to the root.

What is a Bloom Filter?

A Bloom Filter is a space-efficient probabilistic data structure that allows you to determine if a certain item potentially belongs into a set.

What is the main component of a Bloom Filter? What does it do?

The main component of a Bloom Filter is the Bit Array, a 1D array that stores either 0 or 1

These bits are utilized to determine if content has been added, where the bit is set to 1 if the new item was added.

What are two properties of Hash Functions that help with Bloom Filters?

1. The number of elements per bucket/slot is always going to be constant.

2. Searching in the Hash Table will be O(1).

What items are required for a Bloom Filter?

The following items are needed for a proper Bloom Filter:

An array size m where the initial value of all elements is set to 0.

k hash functions.

How do you insert a value into a Bloom Filter?

Insertion into the Bloom Filter is straightforward. Let’s assume there are k hash functions:

Step 1: Perform k hashes with the item to add.

Step 2: Based on each hash result, assign the bit array indexes to 1.

What are runtimes for Bloom Filter Insertion and Bloom Filter Search?

The runtime for Bloom Filter Insertion and Bloom Filter Search is O(k), where k is the number of hash functions.

The hashing itself is constant time.

How does Bloom Filter Search work?

Searching in a Bloom Filter requires using k hash functions. For each hash result, we check the bit array to see if the value is 0. If one of the values is set to 0, then we know that the item does not exist in the set.

What is the probability that one of the bits is set to one in the bit array?

1/m, where m is the number of bits.

What is the probability that one of the bits is not set to one in the bit array?

1 - (1/m), where m is the number of bits.

What is the probability that one of the bits is not set to one after k hashes in the bit array?

(1 - (1/m))^k, where m is the number of bits and k is the number of hash functions.

What is the probability that one of the bits is not set to one after k hashes and n insertions in the bit array?

(1 - (1/m))^nk, where m is the number of bits, k is the number of hash functions, and n is the number of insertions.

What is the probability for a False Positive?

p(E) = (1 - (1 - (1/m))^nk)^k where p(E) is the probability of a false positive, m is the number of bits, k is the number of hash functions, and n is the number of insertions.

Based on the probability for a False Positive for a Bloom Filter, what conclusions can we make about the false positivity rate, regarding the number of hash functions?

The conclusions that we can make from the false positive probability p(E) = (1 - (1 - (1/m))^nk)^k are that a large value k hash functions would cause the false positivity rate to be small.

However, a large value k (increasing the number of hash functions) is not sufficient and practical, since the bloom filter is meant to be space efficient and memory light.

How can we calculate the optimal number of hash functions for a Bloom Filter?

The optimal number of hash functions needed, k, is set as k = ln(2) * m/n, where m is the number of bits with n items to be inserted.

What is the space complexity of the Bloom Filter?

O(m), where m is the number of bits.

What are disjoint sets?

Disjoints sets are any two sets A and B where A and B’s intersection (the set of all elements that are in both) is the empty set.

What is the disjoint set data structure?

A disjoint set data structure maintains a collection S = {S1, S2, ..., Sk} of disjoint dynamic sets, where each set can be identified by a representative, which is a member of the set.

What are the 3 operations where you can modify or access information about the disjoint set?

Make-Set(x), Union(x, y) and Find-Set(x).

What is the Make-Set Operation?

Make-Set(x) creates a new set whose only member is x. Since the sets are disjoints, so it is required that x does not belong to any other set.

What is the Union Operation?

Union(x, y) unites disjoint sets that contain x and y, pointing x’s representative to y’s representative.

What is the Find-Set operation?

Find-Set checks to see if a set contains the element x. If so, then the method would return an address to the representative of the set.

What is the runtime for the non-heuristic versions of the Disjoint Set Operations?

Make-Set is O(1), Find-Set is O(1), Union is O(n), for n elements in the set.

What is the root of the tree in a Disjoint-Set Forest?

The root of the tree is known as the representative, which is found as the only node in a tree that is pointing to itself.

What does each node and tree represent?

Each node in a Disjoint-Set Forest contains one member, and each tree represents a set.

Describe the heuristics that improve the running time of a Disjoint Set Forest.

Union by Rank works by connecting the root with smaller rank points (less nodes pointing to the representative) to the root with larger rank (more nodes pointing to the representative).

Path compression works by minimizing the height of the tree by making all nodes point to the root.

How do the heuristics work in the context of the heuristic Union operation? What changes from the normal, non-heuristic Union operation?

Union By Rank is in Union by changing the Union rules so that Union(x, y) ensures that whichever of x or y has the smaller rank (smaller rank means which one has less nodes pointing to their representative) points to the bigger rank one. Path Compression is also in Union By Rank, since heuristic Union calls heuristic Find-Set, so as the trees join together, both trees up to x and y, respectively for each tree, will go through path compression, and each node down to x and y will point to their representatives (compresses from root down), before comparing ranks (rank is how many nodes are pointing to each of them.)

This changes from the normal Union operation, which just joins their sets together and placing x’s representative to point to y’s representative.

How do the heuristics work in the context of the heuristic Find-Set operation? What changes from the normal, non-heuristic Find-Set operation?

Heuristic Find-Set uses path compression, which, in Find-Set(x), will start at the representative (root) and work its way down, moving every point from the representative to x. Every point that is not pointing to the representative, is then moved to point to the representative.

What is the definition of a greedy algorithm?

A greedy algorithm incorporates the concept of making the best decision at the current moment (without looking at the big picture overall).

Greedy algorithms make a greedy choice, and results in looking at only one subproblem.

What is the greedy solution to the change making problem?

The Change Making Problem:

We are provided a coinage system (such as pennies, nickels, dimes, and quarters). Each coin has an integer value (1, 5, 10, and 25). Given a value n, we want to know how many coins to give. Lets assume that we have unlimited coins to use.

The greedy solution is starting with the largest coin value c. Then we use the coin c and recursively solve for n - c cents (starting with subtracting every quarter possible, every dime possible, until you get to pennies) until all coins are observed.

What are Huffman Codes?

Huffman Codes are greedy algorithms that represent data as a sequence of characters. The objective is designing a binary character code for each character. That allows for the creation of codewords in binary.

What is the action that saves so much memory in Huffman Codes?

Huffman Codes count the frequency of a letter in the data and assigns shorter codes to more frequent letters, thus reducing overall memory usage.

What is the method for finding an optimal Huffman code (using binary strings) for a file F containing a set of characters with given frequencies?

To find an optimal Huffman code (using binary strings) for a file F containing a set of characters with given frequencies:

1. You sort every value from smallest to largest and list them out.

2. You connect the two smallest values (values to the left of the list) and combine their frequencies into one joint frequency.

3. The joint frequency now is the root of all values and all individual frequencies are connected like subtrees to the joint frequency.

4. Repeat steps 1-3 until the entire frequency set is all connected in one big tree.

What are some terms regarding Huffman Codes?

Encoding means concatenating binary codewords (ex: abba = 01011010).

Decoding means traversing the binary sequence from left to right until the first character is recognized (ex: for abba = 01011010, a = 0, b = 101).

What is the objective of Huffman Codes?

The objective of Huffman Codes is to find an optimal prefix code.

How are the codewords decided in the binary tree conversion of a Huffman Code (after you go through steps 1-4 to convert the frequencies and binary strings into a tree-like minheap)?

Each left subtree line has a 0 on it, and every right subtree line has a 1 on it. When finding the codeword for each letter, where each node represents the key:value pair of each letter and its frequency, append each subtree line digit on the way down to your node, and that combined string is your binary code word.

What is the runtime for a Huffman Code?

The queue in the algorithm is a minimum priority queue using the minimum heap O(log(n)).

The runtime itself then, is O(n log(n)).

What is the greedy choice in the Huffman Code Algorithm?

The greedy choice in the Huffman Code Algorithm is to always select the two nodes (or characters) with the smallest frequencies to combine them into a new node. This new node's frequency is the sum of the two selected nodes’ frequencies. By prioritizing the least frequent nodes, the algorithm minimizes the overall length of the encoding, resulting in a more efficient prefix code. This choice is repeated until all nodes are combined into a single tree, ensuring that characters that occur more frequently are assigned shorter binary codes.

Describe a few details about the Skip List Data Structure.

A few details about the Skip List is that it is a probabilistic data structure, maintains a list of n elements in O(log(n)) with high probability, and that the bottom list (Local List) contains all nodes while other lists contain a subset of nodes (Express List).

How does the Search Operation of a Skip List work?

The Search Operation of a Skip List works by starting with the highest express list, and then traversing that highest one until node x in Search(x) is found or passed. If the node was passed in the highest one, go down to the 2nd highest one, and continue traversing until the node is found or not found.

How many sorted lists does it take to mimic the behavior of a binary tree?

log(n) sorted lists mimics the behavior of a binary tree.

How many linked list structures (Local List and Express Lists) are in the perfect/optimal skip list structure?

The perfect skip list structure should have log2n linked list structures, where n is the number of elements in the Local List.

What are the two basic rules that every skip list data structure must follow?

The two basic rules every skip list data structure must follow are every list must always be sorted, and the bottom list (Local List) must contain all elements. The other lists above are known as express lists.

How does insertion into a Skip List’s Express List(s) work?

Insertion works by us flipping a coin, and if we get heads, we can insert this node to an express list, and promote it to the next level. If we get tails, then we stop inserting to an express list and stop promoting it. Each node will get inserted into the next higher level based on the coin flip which ½ (50%).

How does deletion from a Skip List’s Express List(s) work?

Deletion in a Skip List works by just removing the node from all lists in which your node x from Delete(x) is present.

What is the average and worst runtime for skip list insertion, skip list deletion, skip list search, and skip list space efficiency?

Skip List Insert’s average runtime is O(log(n)) and worst case is O(n), Skip List Delete’s average runtime is O(log(n)) and worst case is O(n), Skip List Search’s average runtime is O(log(n)) and worst runtime is O(n), and Skip List space efficiency average runtime is O(n), with worst case O(n log(n)).

What is the High Probability Theorem in a Skip List?

The High Probability Theorem in a Skip List states that with high probability, every search in a skip list costs O(log(n)).

What is a heap? What are the two types of heaps?

A heap is a type of array which can be seen as a nearly complete binary tree and where the keys must satisfy the heap property. The two types of heaps are minheaps, in which the parent node is always less than or equal to its children, ensuring that the smallest element is always at the root, and maxheaps, in which the parent node is always greater than or equal to its children, ensuring that the largest element is always at the root.

What is a treap? What property allows for a quicker runtime?

A treap is a binary search tree with the property that the node priorities satisfies heap property. The heap property allows for a possible O(log(n)) where n is the number nodes in the tree.

What does each node in a treap store?

Each node in a treap stores a left child pointer, a right child pointer, data (using BST property) and its priority (Randomly Assigned). In a treap diagram, each circle (node) will contain two values, one on top (the data is on top), and one on the bottom (the priority is on the bottom)

Why do Treaps have a rotation operation? When will they stop rotating?

Treaps have a rotation operation in order to keep the log(n) runtime, since it changes the structure in balancing itself. Treaps will rotate until the heap property is satisfied (minheap or maxheap).

How do we organize values in a treap?

A treap is organized as a heap first, with each priority value being rearranged based on the manner of heap its in (maxheap = the parent node is always greater than or equal to its children, minheap = the parent node is always less than or equal to its children). After that, it’s just finding how to move the necessary nodes so that what makes sense for the heap property also looks good as a tree.

What are the operations in a Treap?

The operations in a Treap are Insertion, Deletion, Search, Left Rotaion, and Rght Rotaiton.

How does Insertion into a Treap work?

Insertion into a Treap works by first doing the standard BST insertion (same way as inserting a value into a BST, if its less than the parent go left, if its greater than the parent go right, until the node becomes a leaf). Once the node is inserted into the Treap, assign a priority (randomized) to it. Perform rotation(s) until priorities satisfy the heap priority (max-heap (each child is less than their parent) or min-heap (each child is greater than their parent)).

How does Deletion from a Treap work?

Deletion from a Treap has a different procedure than deleting from a BST. First you find the node to delete, and once the node is found, determine if it is a leaf. If it is a leaf, then just delete. Otherwise, replace the priority level to positive/negative infinity and rotate the node down until it is a leaf and then delete.

What is the successor rule in BST Deletion?

This means, based on your wanting to be deleted node’s value, you find the nearest value greater than it (from your value, go right once, and then as far left as possible).

What is the predecessor rule in BST deletion?

This means, based on your wanting to be deleted node’s value, you find the nearest value lesser than it (from your value, go left once, and then as far right as possible).

What do you do in BST Deletion if your node is a leaf?

In BST Deletion, if your node is a leaf, simply delete the leaf, and change the leaf, x, to point to a NIL pointer. No structural changes needed.

What do you do in BST Deletion if your node has one child?

In BST Deletion, if the node you have to delete has a child, replace your node with the child, and change x to point to the child.

What do you do in BST Deletion if your node has two children?

You use the successor rule (swap out the node with the node of closest greater value, found by heading right from your value and going left-down as far as possible and swapping with that value) and using cases 1 (leaf node, x points to NIL) or 2 (node with one child, replace node with child and x points to child) until deletion.

Or the predecessor rule (swap out the node with the node of closest lesser value, found by heading left from your value and going right-down as far as possible and swapping with that value) and using cases 1 (leaf node, x points to NIL) or 2 (node with one child, replace node with child and x points to child) until deletion.

Do a Red Black Tree Problem

Done.

Do a Red Black Tree Problem

Done.

Do a Red Black Tree Problem

Done.

Do a Red Black Tree Problem

Done.

Do 2 Red Black Tree Problems.

Done.

Do 5 Red Black Tree Problems, and if you mess up, you have to restart the whole process by reading and writing each case, and then doing the problems.

Done.

Do 5 Red Black Tree Problems, and if you mess up, you have to restart the whole process by reading and writing each case, and then doing the problems.

Done.

Do a Huffman Code Practice Problem

Done.

Do 4 Huffman Code Practice Problems, if you mess up, you have to review concepts and start the process over.

Done.

Practice a Disjoint Sets Problem

Done.

What is the formula for the optimal number of express lists in a skip list?

h = log2n, where n = number of elements in the skip list.

What is the false positive rate of a Bloom Filter?

P(E) = (1 - (1 - 1/m)^nk)^k, where m = number of bits in bit array, n = number of insertions into the array, and k = the number of hash functions.

How do you insert in a Treap?

You insert the value and organize it like a binary tree, and then once it gets to its leaf position, move the node up based on priority (heap property)(minheap = all nodes are greater than their parent)(maxheap = nodes all lesser than their parent).

How do you delete in a Treap?

You delete a node in a treap by changing the priority of your node to positive/negative infinity and then rotate it down until it becomes a leaf, and then delete the node like normal.

Why would putting in a delete function into a Bloom Filter be inherently detrimental? What would happen?

Implementing a delete function in a Bloom filter is inherently detrimental because it could accidentally remove bits set by multiple elements, leading to false negatives—something Bloom filters are explicitly designed to prevent. Since Bloom filters do not track which element set which bit, deletions are impossible without affecting other stored values. Also, a delete function would significantly increase memory, since you would have to find a way of tracking the bits stored to each insertion.

Greedy Algorithms/Huffman Codes. Look at them.

Done.