Computer Science Test 8 Nddc Scholarship

Both Bubble Sort and Insertion Sort are naturally 'stable' algorithms. Stability ensures that elements with equal keys retain their original relative order after the sort is complete. Since both algorithms only swap adjacent elements (in Bubble Sort) or shift elements (in Insertion Sort) when a strict inequality exists, they never cause equal elements to jump over one another, thus preserving their original sequence.

The Sieve Technique, often used in Selection algorithms like Quickselect, involves partitioning the data and recursing on a single sub-problem. In the standard analysis, if we reduce the problem by a constant fraction (like 1/3 or 1/2), the work done forms a geometric series. While the recurrence might be expressed in terms of the sub-problem size (like \(n/k\)), the overall sum of the work across all phases results in a linear time complexity, often represented as being proportional to \(n\). In the context of specific academic models for these reductions, the total work is often denoted as linear, or \(T(n)\).

Stability is a property of sorting algorithms where duplicate elements (elements with the same key) appear in the output in the same relative order as they appeared in the input. For example, if there are two '5's in a list, and 5a appeared before 5b, a stable sort guarantees that 5a will still be positioned before 5b in the sorted list. This is essential for multi-level sorting, where you might sort by one category (like date) and then another (like name).

One of the reasons Quick Sort is often the preferred sorting algorithm in practice is that its 'hidden constants' are very small. Even though Merge Sort and Heap Sort have the same \(O(n \log n)\) theoretical complexity, Quick Sort's inner loops are very simple and efficient, allowing it to perform fewer actual operations per element than its competitors on most real-world hardware.

In the Quick Sort algorithm, the 'divide' step is where all the actual sorting work occurs through partitioning. The array is partitioned into two sub-arrays such that all elements in the left sub-array are less than or equal to the pivot, and all elements in the right sub-array are greater than the pivot.
Because the partitioning happens in-place, once the recursive calls on the sub-problems are complete, the entire array is naturally in its sorted order. Unlike Merge Sort, which requires a specific 'merge' function to combine sorted halves, Quick Sort requires no additional work to combine the results. Note: While the provided option A is often cited in basic texts, in professional algorithm analysis, the absence of an explicit combine step is the defining characteristic of Quick Sort.

In a DFS traversal, a back edge is an edge \((u, v)\) that connects a vertex \(u\) to an ancestor \(v\) in the DFS tree. The presence of a back edge always indicates at least one cycle. However, a single back edge can be a part of multiple distinct cycles depending on the connectivity of the graph.
Similarly, multiple back edges might be required to form certain types of complex cycles. Therefore, while every back edge identifies a cycle, there is no fixed mathematical ratio or linear relationship that says the number of back edges must equal or be a fraction of the total number of cycles. They are related concepts, but not numerically identical.

To compute the transpose of a directed graph (reversing the direction of all edges), the algorithm must iterate through every vertex in the adjacency list and, for each vertex, iterate through its list of edges.
For every edge \((u, v)\) found in the original list, a new edge \((v, u)\) is created in the transposed list. This process visits every vertex \(V\) and every edge \(E\) exactly once. Consequently, the total time complexity is linear relative to the size of the graph representation, which is expressed as \(O(V + E)\).

Prim’s algorithm uses a priority queue to keep track of the minimum weight edge connecting a vertex outside the tree to a vertex inside the tree. When using a binary heap implementation of a priority queue, the operation to extract the minimum element (Extract-Min) involves removing the root and then 're-heaping' the remaining elements to maintain the heap property.
The height of a binary heap containing \(V\) vertices is \(\log V\). Since the re-heaping process follows a path from the root to a leaf, the time complexity for a single extraction is logarithmic, specifically \(O(\log V)\).

Dijkstra’s algorithm is a fundamental 'Greedy' algorithm used in graph theory. It is designed to solve the Single-Source Shortest Path (SSSP) problem, meaning it calculates the shortest distance from one specific starting vertex to all other reachable vertices in the graph.
The greedy nature of the algorithm is seen in its selection process: at every step, it chooses the unvisited vertex with the smallest tentative distance, assuming that this local choice will contribute to the global shortest path. This approach is highly efficient for graphs with non-negative edge weights.

Kruskal's algorithm is a classic example of the 'Greedy' paradigm. To find the Minimum Spanning Tree, the algorithm first sorts all the edges of the graph in non-decreasing order of their weights.
It then iterates through the sorted edges and adds an edge to the MST if it does not form a cycle with the edges already included. By always picking the smallest available edge that satisfies the non-cycle condition, the algorithm makes a locally optimal choice at each stage with the goal of reaching a globally optimal minimum total weight for the spanning tree.