Graph-Concepts, Data Structures(BST, RBT,MST, Binary Heap)

Disclaimer: Most of the content below will be cited. If any sentence is not cited, I want to clarify that this article is only for knowledge purpose and I will not be earning any money from it.

Related Story : Sorting Algorithms — Basics

Sorting Algorithms- Properties/Pros/Cons/Comparisons

BFS vs DFS

Similarity

• Both the algorithms are used to traverse graphs and creates a tree for the path of its traversal.

Differences

• BFS is a vertex based algorithm, whereas DFS is an edge based algorithm
• BFS uses Queue data structure for its working while DFS uses Stack data structure for its working
• Structure of the constructed tree for BFS is Wide and short while structure of the constructed tree is Narrow and long

Binary Search Tree

• Basic operations like Search in BST in the WORST CASE takes O(n), if the required vertex is on the leftmost or rightmost edge else O(log n) happens for AVERAGE CASE
• (True/False) For any binary search tree T with at least 3 nodes, there is always at least two different series of INSERTs that would produce Tree

False-> If all the nodes are on left or right edge

Red Black Tree

• RB-tree with n internal nodes has height ≤ 2log(n + 1) | True
• RB Tree operations’ like SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR, INSERT, DELETE takes O(log n) time
• Initializing a red-black tree 􏰙with n nodes
  => INSERT each node key into an initially empty BST: T.C : sum of log i from i=1…n = O(n log n)
• Get max value from RB tree : Run MAXIMUM operation
• Produce Top 3 scores in time O(log n) [Larger values are at bottom]
  => Call MAXIMUM, followed by PREDECESSOR on it, and followed by PREDECESSOR one more time
• Produce bottom 3 scores in time O(log n) =>
  Call MINIMUM, followed by SUCCESSOR on it, and followed by SUCCESSOR one more time
• Get a value before/right above and after/right below a node =>
  Call PREDECESSOR and SUCCESSOR on node x.
• From root to farthest leaf : at least h/2 nodes are black
• bh(root) ≥ h/2
• Let x be an internal node in a valid RB-tree with two children x.L (left) and x.R (right). If bh(x.L) = bh(x.R), then x.L and x.R must be the same color.
• Let x be an internal node in a valid RB-tree with two children x.L (left) and x.R (right). If bh(x.L) != bh(x.R), then x.L and x.R must be the different color.

Binary Search Tree vs Red Black Tree
Similarity:

• Both are binary search trees.

Differences:

• Binary search trees have no guarantee/bound (in general) on the height of a tree. RB-trees have a bound: O(log n)

MST (Minimum Spanning Tree)

• (True/False) MST can be created from a directed graph | False

MST is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, WITHOUT ANY CYCLES and with the minimum possible total edge weight

• (True/False) If the edge with maximum weight belongs to a cycle, then there exists some MST that does not contain this edge.

True . We will not take the maximum weight edge when creating MST from the graph

• (True/False) In an undirected graph, the shortest path between two nodes lies on some minimum spanning tree

False -It could be possible that sum of weight of shortest path may be greater than sum of weigts of longer path, so the shorter path has not been included in MST

• If the edges in a graph have different weights, then the minimum spanning tree is unique.
• There cannot be more than one minimum spanning trees if the weight of the edges are all distinct
• If all weights are the same, every spanning tree is minimum
• Adding a constant to every edge weight does not change the minimum spanning tree | True
• (True/False) A minimum spanning tree should contain all edges of the graph

False | rather all vertices should be included

• Adding an edge to a spanning tree connecting two existing vertices of a graph G always creates a cycle

Cycle Property vs Cut Property

Similarity

• Both methodologies creates partition of the vertices in a graph to determine whether edges in cut-set will or will not be included in a minimum spanning trees

Differences

• In Cycle Property, we get the maximum weighted edge on any Cycle C in graph G, that will not belong to any MST of G, whereas
• In Cut Property, we get the minimum weighted edge that will definitely belong to every MST

Binary Heap:

• In a Binary Heap, the value on the left child is less than the value of the right child. | False
  => That is true for BST
  => The only condition for heap invaraint is the Parent should be either more than the child (Max Heap) or less (Min Heap). No condition on left / right node

Index of left child of a node at x = 2x [2,4,6,8…. 2n]
=> Location of 10th index will be fixed in any binary heap

Index of right child of a node at x = 2x+1 [3,5,7,9…. 2n+1]1

If creating from scratch, nodes will be filled from left bottom, going towards right bottom

Binary heaps (min-heaps) are usually implemented using 1D array.
=> For creating max-heap, reverse the array so the scores are sorted in decreasing order [O(n)]
=> OR create a binary heap and call heapify n/2 times [O(n)].

List of Heap operations : INSERT, MAX, EXTRACT-MAX, INCREASE-KEY, DELETE, DECREASE-KEY

Updating min/max-heap
=> Call INCREASE-KEY and DECREASE-KEY
=> OR Delete the node with old data, insert key with new data.

Extract max Operation Working
=> Make the root as the last element in array and reduce the size of heap by one. Then Heapify.

Produce Top 3 scores :
Method 1: Maximum, Extract Max -> Maximum, Extract Max -> Maximum
OR Delete the root three times (to obtain top 3 scores), and INSERT THEM BACK.
Method 2: Examine up to seven nodes in the first three levels of the heap O(1)

Produce Bottom 3 scores of a Max-Heap:
=> Maintain an extra max-heap where the keys are negative values of the scores and get top 3 scores of this min heap

One cannot find the node right above/below a particular node in a max-heap or min-heap, like in BST, in O(log n) time.

Distance between two nodes on a tree:
=> This distance is the number of edges between them on the shortest path
=> It is not the number of levels between them.

If number of nodes ≥ 2, there is a unique Max-Heap containing same set of keys | False

1 1
/ != \ Not Unique
/ \
2 2

In a Max Heap, the largest value is root i.e index 1 and 2nd largest is at index 2, 3rd largest is at index 3, smallest is at index n | False
=> 2nd largest could be index 2 or index 3, for 3rd largest we’ll look at first 7 nodes, smallest can be any of the leaf nodes

Min-heaps (priority queues) and Union-find
Similarity:
Both are data structures useful for MST algorithms (Prim’s and Kruskal’s, respectively).
Differences:
Min-heaps are used by Dijkstra’s or Prim’s algorithm as they are useful for extracting MIN values.

Greedy algorithm
=> Find a minimum/maximum something
=> A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum

=> Greedy solutions doesn’t have inversions because the solution is sorted in some form in intermediate/final stage| True
=> Greedy algorithm runs in exponential time | False
=> it can run in polynomial run time as well as polylog (involved sorting is n.log(n))

Greedy stays ahead vs Exchange argument
Similarity: Both are proof techniques for Greedy algorithms
Differences:
Greedy-stays-ahead compares Greedy algorithm’s solution with an optimal solution. Exchange argument argues that if something is “out of order” in any solution, then we can make it better by swapping the two.

Sorting elements as subroutine will take O(n log(n)) runtime, not just O(log (n))

Activity Selection Problem