Algorithm Time Complexities Quiz

concepts

algorithm

True

<p>Quicksort</p> Signup and view all the answers

<p>In-place sorting is a sorting algorithm that transforms the input without requiring additional space or memory. It modifies the input array directly. An example of in-place sorting is insertion sort.</p> Signup and view all the answers

<p>Not in-place sorting is a sorting algorithm that requires additional space (memory) to transform the input. The memory used is equal to or greater than the original input size. An example of not-in-place sorting is merge sort, which requires a temporary array during the sorting process.</p> Signup and view all the answers

<p>Stable sorting preserves the relative order of elements with the same value in the sorted output array. For example, in merge sort, if elements with the same value are in a specific order in the input array, they will retain that order in the output array. Unstable sorting does not guarantee the preservation of the order of elements with the same value. In quicksort, elements with the same value may end up in a different order in the sorted output array.</p> Signup and view all the answers

<p>In a max-heap, the value of each node is greater than or equal to the values of its child nodes. This property ensures that the largest element resides at the root of the heap.</p> Signup and view all the answers

<p>The best case time complexity for quicksort occurs when the pivot element consistently divides the array nearly in half at each recursive step. This leads to a logarithmic time complexity of O(n log n).</p> Signup and view all the answers

<p>Auxiliary Array (extra storage)</p> Signup and view all the answers

<p>A stack uses a Last-In-First-Out (LIFO) policy. The last element added to the stack is the first element to be removed, similar to a stack of plates where you take the top plate first.</p> Signup and view all the answers

<p>A queue uses a First-In-First-Out (FIFO) policy. The first element added to the queue is the first element to be removed. Think of a queue at a checkout counter where the person who arrived first gets served first.</p> Signup and view all the answers

<ol> <li>Push 123 onto the stack: [123]</li> <li>Push + onto the stack: [123, +]</li> <li>Push 45 onto the stack: [123, +, 45]</li> <li>Push * onto the stack: [123, +, 45, *]</li> <li>Pop * from the stack: [123, +, 45] (45 is the operand)</li> <li>Pop 45 from the stack: [123, +] (123 is the operand)</li> <li>Compute 123 + 45 = 168: [168, +]</li> <li>Pop + from the stack: [168] (operand)</li> <li>The final answer is 168.</li> </ol> Signup and view all the answers

<p>Push</p> Signup and view all the answers

<p>The top attribute of a stack keeps track of the most recent element pushed into the stack. It usually points to the memory location of the top element.</p> Signup and view all the answers

<p>Dequeue</p> Signup and view all the answers

<p>Tail</p> Signup and view all the answers

<p>A tree structure consists of the following attributes:</p> <ol> <li>Root: The topmost node in the tree (starting point of the hierarchy).</li> <li>Parent: A node that is directly above another node in the tree hierarchy, which is its child.</li> <li>Child: A node that is directly below another node in the tree hierarchy, which is its parent.</li> <li>Leaf: A node that has no children.</li> <li>Key: A value associated with each node, used for searching or ordering.</li> <li>Edge: A connection between two nodes in the tree, representing a parent-child relationship.</li> </ol> Signup and view all the answers

<p>The binary search tree property states: For every node 'x' in a binary search tree, if 'y' is a node in the left subtree of 'x', then 'y.key' ≤ 'x.key'. Conversely, if 'y' is a node in the right subtree of 'x', then 'y.key' ≥ 'x.key'.</p> Signup and view all the answers

<p>Postorder: 25, 35, 30, 45, 60, 50, 40</p> Signup and view all the answers

<p>Height 2 - start from root at 0</p> Signup and view all the answers

<p>The root is black.</p> Signup and view all the answers

<p>A sentinel is essentially a boundary marker or a special value used to simplify algorithm logic during the sorting process, particularly in merge sort and red-black trees. It's a way to mark the beginning or end of an array or part of a tree structure to make comparisons and operations cleaner in the algorithms.</p> Signup and view all the answers

<p>Chaining in hash tables is a technique used to resolve collisions, when multiple keys hash to the same index or slot in the hash table. A linked list is associated with each index, so whenever a collision happens, the new element is added to the linked list at that index.</p> Signup and view all the answers

<p>Break the problem into several overlapping subproblems</p> Signup and view all the answers

<p>Dynamic programming involves a trade-off between time and memory. By storing previously calculated solutions to subproblems, the algorithm reduces the amount of time spent in redundant computations, but this requires additional memory to store the intermediate solutions.</p> Signup and view all the answers

<p>We use the matrix-chain multiplication algorithm to calculate the minimum number of scalar products required to multiply a chain of matrices.</p> Signup and view all the answers

<p>The two methods for finding the longest common subsequence (LCS) are brute force and the optimal substructure property.</p> <ol> <li>Brute Force: This entails examining all possible subsequences of the given sequences, comparing them, and selecting the longest one. It's computationally expensive.</li> <li>Optimal Substructure Property: This approach involves finding the longest subsequences for the sequences up to the current position i and j and then constructing the LCS based on the maximum of previously calculated values.</li> </ol> Signup and view all the answers

<p>The output we want from the LCS algorithm is the length of the longest common subsequence and the actual subsequence itself. This result can be obtained by filling in the table B and C, which store the directional information and the lengths of the common subsequences, respectively, and then utilizing a backtracking function (print-lcs) to reconstruct the actual subsequence.</p> Signup and view all the answers

<p>The C table, used in the longest common subsequence algorithm, stores the lengths of the common subsequences for the subproblems. The B table, also known as the direction table, is used to backtrack and reconstruct the actual longest common subsequence. Each entry in B indicates the direction (upward, leftward, or diagonally) to follow while reconstructing the LCS from the previously calculated values in the table.</p> Signup and view all the answers

<p>In the longest common subsequence (LCS) algorithm, the arrows in the B table indicate the direction to follow while backtracking to construct the LCS:</p> <ol> <li>Diagonal Arrow: Indicates that the current characters of both sequences match, contributing to the LCS.</li> <li>Up Arrow: Indicates that the current character of the first sequence is not a part of the LCS at the current position, meaning the algorithm has moved upward in the table to derive the value.</li> <li>Left Arrow: Indicates that the current character of the second sequence is not a part of the LCS at the current position, meaning the algorithm has moved leftward in the table to derive a value.</li> </ol> Signup and view all the answers

<p>B-Trees are balanced search trees specifically designed to function well on disk or direct access secondary storage devices, making them suitable for managing large datasets that are too large to fit into memory. They are commonly used in databases and file systems to store and query data efficiently.</p> Signup and view all the answers

<p>B-Trees copy pages from the disk into main memory as needed during operations, for example, during a search or insertion. Afterwards, it writes back onto the disk the pages that have been changed, ensuring consistency and integrity of the saved data.</p> Signup and view all the answers

<p>Every node other than the root in a B-Tree must have at least t-1 keys and at most 2t-1 keys, where 't' is a fixed minimum number of keys that a node must contain, called the minimum degree of the B-Tree.</p> Signup and view all the answers

<p>Every node in a B-Tree may contain at most 2t-1 keys, where 't' is the minimum degree of the tree, ensuring a balanced structure and efficient data management in large datasets.</p> Signup and view all the answers

<p>Disjoint sets represent a collection of non-overlapping sets, each containing distinct elements. The function <code>Make-Set(x)</code> creates a new set containing only element 'x', which is its representative. This function initializes a set with only one element, effectively establishing an independent set within the collection.</p> Signup and view all the answers

<p>Undirected</p> Signup and view all the answers

<p>The maximum number of edges that can connect a set of nodes in a graph is given by the formula: |E| &lt;= |V|² , where |E| represents the number of edges and |V| represents the number of vertices. This means the maximum possible number of edges is the square of the number of vertices.</p> Signup and view all the answers

<p>Adjacency list</p> Signup and view all the answers

<p>Depth-First search (DFS) traverses a graph by exploring as far as possible along each branch before backtracking. It starts at a root node, then visits an unvisited adjacent node, continues to follow unvisited adjacent nodes until it reaches a node with no unvisited adjacent nodes or a node that has already been visited. Once it has visited all nodes reachable along that path, it backtracks and explores other branches of the graph.</p> Signup and view all the answers

<p>A strongly connected component in a directed graph is a subset of vertices where every pair of vertices 'u' and 'v' within that component has a path from 'u' to 'v' and another path from 'v' to 'u'. In other words, any vertex in the component can be reached from any other vertex within the same component.</p> Signup and view all the answers

<p>Transposing a graph involves reversing the direction of all edges within the graph. For a directed graph, if there is an edge going from vertex 'u' to 'v', then in the transposed graph, there will be an edge going from 'v' to 'u'.</p> Signup and view all the answers

<p>The goal of finding a minimum spanning tree (MST) for a graph is to identify a sub-tree that connects all the vertices of the original graph using the minimum possible total edge weight. It's effectively a tree that spans all the vertices with the lowest possible cost.</p> Signup and view all the answers

<p>Dijkstras</p> Signup and view all the answers

<p>Kruskal's algorithm works by repeatedly selecting the edge with the least weight from the remaining set of edges, as long as it does not create a cycle. Prims algorithm starts with a single vertex and iteratively adds the edge with the least weight to the spanning tree from all the edges connecting to the current tree.</p> Signup and view all the answers

<p>Kruskal's algorithm uses a greedy approach to build the minimum spanning tree by repeatedly selecting the edge with the least weight from the remaining edges that don't create cycles. It can be implemented using a disjoint set data structure for efficiently checking if adding an edge creates a cycle.</p> Signup and view all the answers

<p>Prim's algorithm is also a greedy algorithm that starts with a single vertex and iteratively expands the spanning tree by selecting the edge with the least weight connected to the current tree. It uses a priority queue to efficiently determine the edge with the least weight at each step, ensuring a minimum spanning tree with the least possible total edge weight.</p> Signup and view all the answers

<p>Bellman Ford</p> Signup and view all the answers

<p>Bellman Ford</p> Signup and view all the answers

<p>The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph, even those containing negative edge weights. The algorithm works by repeatedly relaxing the edges of the graph, which involves updating the shortest distance to a vertex if a shorter path is found. The algorithm initializes the distance to all vertices to infinity except the source, which is set to 0. Then, it iterates over all the edges of the graph, relaxing each edge until no further relaxations are possible. If there are negative cycles in the graph, the algorithm detects them and returns <code>False</code>.</p> Signup and view all the answers

<p>In the Bellman-Ford algorithm, we need to avoid negative cycles, which are cycles in a graph where the sum of edge weights is negative. Negative cycles can lead to an infinite loop of shortest path computations, causing the algorithm to run indefinitely.</p> Signup and view all the answers

<p>False</p> Signup and view all the answers

<p>Dijkstra's algorithm aims to find the shortest paths from a single source vertex to all other vertices in a weighted graph, where all edge weights are non-negative. It works by iteratively building a set of vertices for which the shortest paths from the source have been determined. It uses a priority queue to efficiently select the vertex with the least distance from the source that has not yet been selected. The algorithm expands the set of vertices with known shortest paths until all vertices are included in the set.</p> Signup and view all the answers