Algorithms and Sorting Techniques Quiz

Graph Algorithms

• 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.

Sorting Algorithms

• 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'.

Maximum Matching

• 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

• 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

• 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.

Linear Programming

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

Vertex Cover and Set Cover Problems

• 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

• 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

• 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

• 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 and Flow Network

• 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

• 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

• 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

• 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

• 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.