Algorithms and Sorting Techniques Quiz

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering.
Algorithm to find topological sorting of a graph:
- Choose a vertex with no incoming edges (source node)
- Remove the vertex from the graph and add it to the ordering
- Repeat steps 1-2 until the graph is empty
Example: In a graph with vertices A, B, C, D, E, and F, where A -> B, B -> C, C -> D, D -> E, and E -> F, the topological sorting is A, B, C, D, E, F.

Selection sort algorithm to sort the characters of string 'advance algorithms':
- Initialize the minimum index as the current index
- Find the minimum element in the unsorted part of the string and swap it with the current element
- Repeat step 2 until the entire string is sorted
Example: Sorting the string 'advance algorithms' using selection sort produces the sorted string 'aaceadilgmnooprsrvy'.

Algorithm to compute a maximum matching in a graph:
- Find augmenting paths in the graph
- Update the matching by adding or removing edges from the augmenting paths
- Repeat steps 1-2 until no more augmenting paths can be found
Example: In a graph with vertices A, B, C, D, and E, and edges A-B, B-C, C-D, and D-E, the maximum matching is A-B, C-D.

All pairs shortest path problem: finding the shortest path between every pair of vertices in a weighted graph
Solution using dynamic programming:
- Create a 2D matrix to store the shortest distances between vertices
- Initialize the matrix with infinity and the diagonal elements with 0
- Update the matrix using the recursive formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Repeat step 3 until the matrix is filled

Insertion sort algorithm to sort the data: 65, 75, 5, 55, 25, 30, 90, 45, and 80:
- Initialize the first element as the sorted part
- Iterate through the remaining elements and insert each element into the sorted part
- Repeat step 2 until the entire data is sorted
Example: Sorting the data using insertion sort produces the sorted array: 5, 25, 30, 45, 55, 65, 75, 80, 90.

Applications of linear programming:
- Resource allocation and optimization
- Portfolio optimization and risk management
- Production planning and scheduling

Vertex cover problem: finding the minimum number of vertices that cover all edges in a graph
Set cover problem: finding the minimum number of sets that cover all elements in a universe
Reducing vertex cover to set cover problem:
- Create a universe of edges and a collection of sets, where each set corresponds to a vertex
- For each vertex, add the edges incident on it to the corresponding set
- Solve the set cover problem to find the minimum number of vertices that cover all edges

Triangular matrix: a square matrix where all elements below or above the diagonal are zero
Example: The matrix [[1, 2, 3], [0, 4, 5], [0, 0, 6]] is a triangular matrix.

Residual network: a network that represents the remaining capacity of each edge in a flow network
Construction of a residual network:
- Create a new network with the same vertices and edges as the original network
- For each edge, set the capacity to the original capacity minus the current flow
Example: Given a flow network with edges A-B, B-C, and C-D, with capacities 2, 3, and 4, respectively, and a flow of 1 unit from A to D, the residual network has capacities 1, 2, and 3, respectively.

LU decomposition: a factorization of a matrix into the product of a lower triangular matrix and an upper triangular matrix
Process of LU decomposition:
- Find the lower triangular matrix L and upper triangular matrix U such that A = LU
- Perform row and column operations to transform the matrix A into the upper triangular matrix U
- Read off the lower triangular matrix L from the row operations
Example: Given a matrix A = [[2, 4], [1, 3]], the LU decomposition is A = LU = [[1, 0], [0.5, 1]] [[2, 4], [0, 2]].

Flow: a function that assigns a non-negative value to each edge in a flow network
Flow network: a directed graph with a source node, a sink node, and capacities on the edges
Example: A flow network with a source node A, a sink node D, and edges A-B, B-C, C-D, with capacities 2, 3, and 4, respectively, has a flow of 2 units from A to D.

Divide and conquer paradigm: a problem-solving approach that breaks down a problem into smaller sub-problems, solves each sub-problem, and combines the solutions to solve the original problem
Example: The merge sort algorithm uses the divide and conquer paradigm to sort an array of elements.

Strassen's algorithm: a matrix multiplication algorithm with a time complexity of O(n^2.81)
The algorithm uses a divide and conquer approach to multiply two matrices
Example: Strassen's algorithm can be used to multiply two 2x2 matrices in 7 multiplications.

Analysis of approximation algorithms: studying the performance of algorithms that produce approximate solutions to optimization problems
Key concepts: approximation ratio, approximation scheme, and PTAS

Ford-Fulkerson algorithm: an algorithm to find the maximum flow in a flow network
The algorithm uses a residual network to find augmenting paths and update the flow
Example: The Ford-Fulkerson algorithm can be used to find the maximum flow in a flow network with a source node, a sink node, and edges with capacities.