Algorithms and Data Structures Flashcards

Question

DFS Depth First Search

Answer 1

DFS Depth First Search O(V + E) where V and E are total vertices and edges O(1) to O(V**2) depending on how dense the graph is You start at the root and explore as far as possible for each branch before backtracking. It uses the Stack instead of queue ``` // recursive imple of preorder traversal procedure preorder(treeNode v) { visit(v); for each child u of v preorder(u); } ``` ``` // to check neighbors first instead of child procedure dfs(vertex v) { visit(v); for each neighbor u of v if u is undiscovered call dfs(u); } ``` ``` class Graph { public: // a vector of vectors to represent an adjacency list vector> adjList; ``` ``` // Graph Constructor Graph(vector const &edges, int N) { // resize the vector to hold N elements of type `vector` adjList.resize(N); ``` ``` // add edges to the undirected graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; ``` ``` // Function to perform DFS traversal on the graph on a graph void DFS(Graph const &graph, int v, vector &discovered) { // mark the current node as discovered discovered[v] = true; ``` ``` // print the current node cout << v << " "; ``` ``` // do for every edge `v —> u` for (int u: graph.adjList[v]) { // if `u` is not yet discovered if (!discovered[u]) { DFS(graph, u, discovered); } } } ```

Answer 2

Inorder, Preorder, Postorder Tree Traversals All are: O(n) Inorder, LNR Left subtrees going up, N (root), next Right subtree and repeat Preorder, NLR N(root), Left subtrees, next right subtree and follow Left subtrees again and repeat Postorder, LRN Left Subtree, Right Subtree, then N (root) should be next Left now and repeat

Answer 3

Kruskal’s Minimum Spanning Tree Algorithm Given an undirected, connected, and weighted graph, construct a minimum spanning tree. A greedy algorithm by finding a subset of edges covering every vertex, so the sum of weights on the edges are at a minimum. It includes edges unless they create a cycle (A > B > C > A), as they will be discarded. ``` #include #include #include #include using namespace std; ``` ``` // Data structure to store a graph edge struct Edge { int src, dest, weight; }; ``` ``` // Comparison object to be used to order the edges struct compare { bool operator() (Edge const &a, Edge const &b) const { return a.weight > b.weight; } }; ``` ``` // A class to represent a disjoint set class DisjointSet { unordered_map parent; public: // perform MakeSet operation void makeSet(int N) { // create `N` disjoint sets (one for each vertex) for (int i = 0; i < N; i++) { parent[i] = i; } } ``` ``` // Find the root of the set in which element `k` belongs int Find(int k) { // if `k` is root if (parent[k] == k) { return k; } ``` ``` // recur for the parent until we find the root return Find(parent[k]); } ``` ``` // Perform Union of two subsets void Union(int a, int b) { // find the root of the sets in which elements // `x` and `y` belongs int x = Find(a); int y = Find(b); ``` parent[x] = y; } }; ``` // Function to construct MST using Kruskal’s algorithm vector kruskalAlgo(vector edges, int N) // no-ref, no-const { // stores the edges present in MST vector MST; ``` ``` // initialize `DisjointSet` class DisjointSet ds; ``` ``` // create a singleton set for each element of the universe ds.makeSet(N); ``` ``` // sort edges by increasing weight sort(edges.begin(), edges.end(), compare()); ``` ``` // MST contains exactly `V-1` edges while (MST.size() != N - 1) { // consider the next edge with minimum weight from the graph Edge next_edge = edges.back(); edges.pop_back(); ``` ``` // find the root of the sets to which two endpoints // vertices of the next edge belongs int x = ds.Find(next_edge.src); int y = ds.Find(next_edge.dest); ``` ``` // if both endpoints have different parents, they belong to // different connected components and can be included in MST if (x != y) { MST.push_back(next_edge); ds.Union(x, y); } } return MST; } ```

Answer 4

Floyd Warshall's All-Pairs Shortest Path Algorithm O( |V**3| ) where V is vertices A graph where its edge weights w(u, v) can be negative, you find the shortest directed path with weights d(s, v) from every source S for all vertices. ``` let dist be V × V matrix of minimum distances initialized to INFINITY for each vertex v dist[v][v] = 0 for each edge (u, v) dist[u][v] = weight(u, v) ``` for k from 0 to |V| – 1 for i from 0 to |V| – 1 for j from 0 to |V| – 1 if (dist[i][k] + dist[k][j]) < dist[i][j] then dist[i][j] = dist[i][k] + dist[k][j] The adjacency matrix containing the shortest distance is: 0 -1 -2 0 4 0 2 4 5 1 0 2 3 -1 1 0 The shortest path from: – vertex 0 to vertex 1 is (0 2 3 1) – vertex 0 to vertex 2 is (0 2) – vertex 0 to vertex 3 is (0 2 3) – vertex 1 to vertex 0 is (1 0) – vertex 1 to vertex 2 is (1 0 2) – vertex 1 to vertex 3 is (1 0 2 3) – vertex 2 to vertex 0 is (2 3 1 0) – vertex 2 to vertex 1 is (2 3 1) – vertex 2 to vertex 3 is (2 3) – vertex 3 to vertex 0 is (3 1 0) – vertex 3 to vertex 1 is (3 1) – vertex 3 to vertex 2 is (3 1 0 2)

Answer 5

Dijkstra’s Algorithm We know that the Breadth-first search BFS can be used to find the shortest path in an unweighted graph or even a weighted for same cost for each edge. But if edges are weighted differently, then BFS generalizes to Uniform-Cost Search. Instead of expanding nodes to their depth from the root, UCS expands the nodes in order of their cost from the root. A variant is called Dijkstra's Algorithm. It finds the shortest path between that node and every other node. The algorithm is stopped once the fastest route to the destination node has been determined

Answer 6

Linked List In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). ``` // C++ code for linked list merged sort class Node { public: int data; Node* next; }; ``` /* function prototypes */ Node* SortedMerge(Node* a, Node* b); void FrontBackSplit(Node* source, Node** frontRef, Node** backRef); ``` /* sorts the linked list by changing next pointers (not data) */ // Base case -- length 0 or 1 void MergeSort(Node** headRef) { Node* head = *headRef; Node* a; Node* b; ``` ``` /* Base case -- length 0 or 1 */ if ((head == NULL) || (head->next == NULL)) { return; } ``` ``` /* Split head into 'a' and 'b' sublists */ FrontBackSplit(head, &a, &b); ``` /* Recursively sort the sublists */ MergeSort(&a); MergeSort(&b); ``` /* answer = merge the two sorted lists together */ *headRef = SortedMerge(a, b); } ``` ``` /* See https:// www.geeksforgeeks.org/?p=3622 for details of this function */ Node* SortedMerge(Node* a, Node* b) { Node* result = NULL; ``` ``` /* Base cases, will return the other if null */ if (a == NULL) return (b); else if (b == NULL) return (a); ``` ``` /* Pick either a or b, and recursion */ if (a->data <= b->data) { result = a; // -> points to struct or union, as next is a struct result->next = SortedMerge(a->next, b); } else { result = b; // -> points to struct or union, as next is a struct result->next = SortedMerge(a, b->next); } return (result); } ``` /* UTILITY FUNCTIONS */ /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. If the length is odd, the extra node should go in the front list. Uses the fast/slow pointer strategy. */ void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) { Node* fast; Node* slow; slow = source; fast = source->next; ``` /* Advance 'fast', slow, then fast one node */ while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } ``` ``` /* 'slow' is before the midpoint in the list, so split it in two at that point. */ // frontRef is source, backRef is next which is slow, // slow is now the next which is a null last slot *frontRef = source; *backRef = slow->next; slow->next = NULL; } ``` ``` /* Function to print nodes in a given linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } ``` ``` /* Function to insert a node at the beginging of the linked list */ void push(Node** head_ref, int new_data) { // allocates a new node, puts in data, link list to node, // moves head to point to new node Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } ```

Answer 7

Singly Linked List VS Doubly Linked List A singly-linked list contains some data and a link to the next element, which allows keeping the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node.

Answer 8

Quick Sort for Singly Linked List ``` // here the sorting happens exclusively at the end node struct Node* quickSortRecur(struct Node* head, struct Node* end) { // base condition // if ever head or NOT head is the end, return head if (!head || head == end) return head; ``` Node *newHead = NULL, *newEnd = NULL; ``` // Partition the list, newHead and newEnd will be // updated by the partition function struct Node* pivot = partition(head, end, &newHead, &newEnd); ``` ``` // If pivot is the smallest element - no need to recur // for the left part. if (newHead != pivot) { // Set the node before the pivot node as NULL struct Node* tmp = newHead; while (tmp->next != pivot) tmp = tmp->next; tmp->next = NULL; ``` ``` // Recur for the list before pivot newHead = quickSortRecur(newHead, tmp); ``` ``` // Change next of last node of the left half to // pivot tmp = getTail(newHead); tmp->next = pivot; } ``` ``` // Recur for the list after the pivot element pivot->next = quickSortRecur(pivot->next, newEnd); ``` return newHead; } ``` // The main function for quick sort. This is a wrapper over // recursive function quickSortRecur() void quickSort(struct Node** headRef) { (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); return; } ```

Answer 9

Trie aka Digital Tree or Prefix Tree A type of search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key. A trie for keys "A", "to", "tea", "ted", "ten", "i", "in", and "inn". Each complete English word has an arbitrary integer value associated with it.

Answer 10

Graph A graph is a data structure that consists of the following two components: 1. A finite set of vertices also called nodes. 2. A finite set of ordered pair of the form (u, v) called an edge. The pair is ordered because (u, v) is not the same as (v, u) in the case of a directed graph(di-graph). The pair in the form of (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost. ``` // A utility function to add an edge in an // undirected graph. void addEdge(vector adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } ``` ``` // A utility function to print the adjacency list // representation of graph void printGraph(vector adj[], int V) { for (int v = 0; v < V; ++v) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); } } ``` ``` // Driver code int main() { int V = 5; vector adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj, V); return 0; } ```

Answer 11

Hashing There is input that goes into a hash function that gives a hash value that is unique to itself. First block in a blockchain is called Genesis block, it will be added to the new transactions in the new block, thus making it an unbreakable dependency secure, immutable, and transparent network. https://www.youtube.com/watch?v=2BldESGZKB8

Answer 12

Bit Manipulation ``` AND 0 AND 0 = 0 1 AND 0 = 0 0 AND 1 = 0 1 AND 1 = 1 AND is represented by the ampersand - 1 & 1 = 1 ``` ``` OR 0 OR 0 = 0 1 OR 0 = 1 0 OR 1 = 1 1 OR 1 = 1 OR is represented by the vertical bar (pipe) - 1 | 1 = 1 ``` ``` XOR 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 1 XOR 1 = 0 XOR is represented by the upwards caret - 1 ^ 1 = 1 ``` ``` XOR, int main() { int x = 10, y = 5; // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) cout << "After Swapping: x =" << x << ", y=" << y; return 0; } ``` ``` void swap(int* xp, int* yp) { *xp = *xp ^ *yp; *yp = *xp ^ *yp; *xp = *xp ^ *yp; } ```

Answer 13

The stack can do function calls and local variables/primitives, but not objects. It can use a a pointer of Object myObject; and points to a part in the heap. In C to use Heap: malloc, calloc, realloc, free In C++ to use Heap: new, delete Heap/dynamic memory is a large space and determines if memory is still used/no longer referenced or becomes trash that can be used for new memory. You need heap when you need states to stay around.

Answer 14

Recursion Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration). Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code.

Answer 15

Dynamic Programming Simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Recursion solves such recursive problems by using functions that call themselves from within their own code. If a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have an optimal substructure. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature, this relationship is called the Bellman equation. ``` Examples are: Dijkstra's Algo for the shortest path Fibonacci sequence a type of balanced 0-1 matrix checkerboard sequence alignment tower of Hanoi egg dropping puzzle matrix chain multiplication ```