Decrease and Conquer

Briefly explain the Decrease and Conquer design approach.

What is meant by the Decrease and Conquer technique? Explain its variations.

The Decrease and Conquer design approach is a general algorithm design strategy based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.

Once this relationship is established, it can be utilized either in top-down or bottom-up:

• Top-down: This method naturally leads to a recursive implementation, solving the larger problem by first solving a smaller one.

• Bottom-up (incremental approach): This approach is typically implemented iteratively, starting with a solution to the smallest problem instance;.

There are three main variations of the Decrease and Conquer technique:

1. Decrease by a Constant:

In this variation, the size of a problem instance is reduced by the same constant amount on each iteration of the algorithm, (typically one) on each iteration of the algorithm.

An example is calculating aⁿ, which can be seen as (aⁿ⁻¹ * a). Insertion sort is also a direct application of this technique.

• Insertion Sort: works by assuming a smaller portion of the array (A[0...n-2]) is already sorted and then finding the correct position for the next element (A[n-1]) and inserting it. It performs well on almost-sorted arrays.

• Generating Combinatorial Objects: This includes algorithms for generating permutations and subsets.

2. Decrease by a Constant Factor:

This technique reduces a problem instance by the same constant factor on each iteration, most commonly by half.

Algorithms in this category often achieve logarithmic time efficiency due to the rapid size reduction. Examples include binary search and exponentiation by squaring (aⁿ = (aⁿ/²)²).

3. Variable Size Decrease:

In this variation, the pattern of size reduction varies from one iteration of the algorithm to another.

Euclid's algorithm for computing the greatest common divisor (gcd(m, n) = gcd(n, m mod n)) is a good example, as the second argument (m mod n) decreases, but not by a fixed constant or constant factor.

Insertion Sort

Page 160

Write an algorithm for Insertion Sort.

The Insertion Sort algorithm is a direct application of the decrease-by-one technique for sorting an array. It works by assuming that a smaller portion of the array is already sorted and then inserting the next element into its appropriate position within the sorted part.

The algorithm is generally implemented iteratively (bottom-up), although it is based on a recursive idea.

It iterates through the array, starting from the second element (index 1) up to the last element (index n-1).

In each iteration, an element A[i] is taken and inserted into its correct place among the preceding elements that have already been sorted.

ALGORITHM InsertionSort(A[0..n − 1])
//Sorts a given array by insertion sort
//Input: An array A[0..n − 1] of n orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order

for i <- 1 to n − 1 do
	v <- A[i]
	j <- i − 1
	while j ≥ 0 and A[j] > v do
		A[j + 1] <- A[j]
		j <- j − 1
	A[j + 1] <- v
return A

Time Complexity: O(n²) worst case, O(n) best case (already sorted).

Depth-First Search (DFS) and Breadth-First Search (BFS)

Page 148

Give the pseudocode for DFS.

ALGORITHM DFS(G)
// Implements a depth-first search traversal of a given graph.
// Input: Graph G = (V, E)
// Output: Graph G with its vertices marked with consecutive integers
//         in the order they are first encountered.

// Initialization
mark each vertex v in V with 0     // Mark all as "unvisited"
count <- 0

// Main loop to visit all vertices, even in disconnected graphs
for each vertex v in V do
	if v is marked with 0 then    // If v is unvisited
		dfs(v)                    // Start traversal from v

PROCEDURE dfs(v)
// Recursively visits all unvisited vertices connected to vertex v
//  and numbers them using the global variable 'count'.

count <- count + 1
mark v with count           // Mark v as its discovery number

// Recursively visit all unvisited neighbors
for each vertex w in V adjacent to v do
	if w is marked with 0 then  
		dfs(w)

Time Complexity: O(V + E) for a graph with V vertices and E edges.

Write two differences between DFS and BFS.

The Depth-First Search (DFS) and Breadth-First Search (BFS) are two fundamental graph traversal algorithms, systematically processing all vertices and edges of a graph.

Data Structure Used

• DFS primarily uses a stack to manage its traversal. Vertices are pushed onto the stack when first visited and popped off when they become a dead end.

• BFS primarily uses a queue for its traversal. The queue is a FIFO (first-in first-out) structure.

Traversal Mechanism and Order

• DFS proceeds by going as far as possible along each branch before backtracking. It goes to an unvisited adjacent vertex, continuing this process until a dead end (a vertex with no unvisited adjacent vertices) is encountered. Then, it backs up one edge and tries to continue from there.

• BFS proceeds in a concentric manner, visiting all directly adjacent vertices first, then all unvisited vertices two edges away, and so on, until all vertices in the current connected component are visited.

Vertex Orderings Yielded

• DFS yields two orderings of vertices: the order in which vertices are first reached (pushed onto the stack) and the order in which they become dead ends (popped off the stack).

• BFS yields one ordering of vertices because of its FIFO queue structure; the order in which vertices are added is the same as the order they are removed.

Applications

• Both DFS and BFS can be used to check connectivity and acyclicity of a graph.
• DFS is particularly helpful for finding articulation points of a graph.
• BFS can be used for finding a path with the fewest number of edges between two given vertices.

Efficiency

• For graphs represented by an adjacency matrix, both DFS and BFS have a time efficiency of Θ(|V|²).
• For graphs represented by adjacency lists, both DFS and BFS have a time efficiency of Θ(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges. For sparse graphs (where |E| ∈ O(|V|)), the adjacency list version is more efficient.