Data Structures and Algorithms

O(n^2) indicates the algorithm's runtime grows quadratically with the input size, meaning it becomes slower as the input gets larger. For example, if the input size doubles, the runtime quadruples.

This algorithm splits the problem into smaller subproblems, solves them independently (recursively), and then combines the solutions. It's known for its efficient performance, especially for large datasets.

In-place sorting refers to algorithms that modify the original input data structure directly without requiring additional memory to store sorted data. This means the sorting happens within the original array or linked list.

Stable Sorting algorithms maintain the relative order of elements with identical values. If two elements have the same value, their sequential order in the output remains the same as in the input.

When a sorting algorithm requires extra memory, beyond the original input, to store the sorted data, it's considered not in-place sorting. This memory requirement is typically for temporary storage during the sorting process.

Unstable sorting algorithms do not preserve the relative order of elements with identical values. If two elements have the same value, their sequential order in the output might be different from the input.

Linear data structures are arranged in a sequential manner, where elements are accessed one after another in a defined order. Examples include arrays, stacks, queues, and linked lists.

Nonlinear data structures don't follow a linear sequence, allowing for more complex relationships between elements. Examples include trees, graphs, and hash tables.

For any node 'i' in the heap, the key of the parent node is greater than or equal to the key of the node 'i'. A[Parent(i)] ≥ A[i]

Occurs when the pivot divides the array nearly in half with each recursive call. This results in the best possible time complexity of O(n log n).

A data structure used in Counting Sort. Holds the frequency of each element in the input array.

A data structure that follows the Last-In, First-Out (LIFO) policy. Elements are added and removed from the top.

A data structure that follows the First-In, First-Out (FIFO) policy. Elements are added at the rear and removed from the front.

Two functions that add and remove elements from a stack. Push adds an element, Pop removes the top element.

Dynamic Programming breaks down a problem into overlapping subproblems, solves each subproblem only once, storing the solution in a table, and then combines those solutions to solve the original problem.

Dynamic Programming involves a time-memory trade-off because it uses additional memory to store the solutions of subproblems, which speeds up the overall process.

Matrix-chain multiplication is an algorithm used to calculate the minimum number of scalar products needed to multiply a chain of matrices.

The longest common subsequence (LCS) algorithm aims to find the longest sequence of characters that appear in the same order in two given sequences, not necessarily contiguous.

The two main methods for finding the longest common subsequence are brute-force, which exhaustively checks all possible subsequences, and the optimal substructure approach, which utilizes the dynamic programming principle to efficiently find the optimal solution.

The output of the LCS algorithm is the length of the longest common subsequence and the subsequence itself. This information is derived from the C table, which stores the lengths of subproblems, and the B table, which helps reconstruct the actual subsequence.

The C table stores the lengths of various subproblems of the longest common subsequence, while the B table, also called the directional table, helps reconstruct the longest common subsequence by indicating the direction from which each value was derived.

Diagonal arrows indicate matching characters, while up arrows mean that the current character of the first sequence is excluded, and left arrows indicate that the current character from the second sequence is excluded.