Decrease and Conquer

• Decrease the problem instance to smaller instances of the same problem.
• Conquer the problem by solving these smaller instances.
• Extend the solution of smaller instances to obtain a solution to the original problem.
• Exploit the relationship between a solution to a given instance of a problem, and a solution to its smaller instance.
• 3 types:
  • Decrease by constant
  • Decrease by constant factor
  • Variable size decrease
• Can be implemented either top-down or bottom-up.

Insertion Sort

• Based on the idea that one element from the input elements is consumed in each iteration to find its correct position.

• Sorted array grows in each iteration.

• Procedure:

  • Compare the current element with the largest value in the sorted array
  • If current element is greater, then it leaves the element in its place, and moves to the next element.
  • Else, it finds the correct position in the sorted array and moves it to that position.

  

Algorithm InsertionSort(A[0..n-1])
// sorts a given array by insertion sort

	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

• Time efficiency:

  $C_{worst} = \frac{n(n-1)}{2} \in \Theta(n^2) \\C_{avg} = \frac{n^2}{4} \in \Theta{n^2} \\ C_{best} = n-1 \in \Theta(n)$

• This is an efficient algorithm if the array is partially sorted.

Topological Sorting

• DAG → Directed Acyclic Graph
• Topological sorting arranges the vertices of a directed graph in a linear order such that for any edge (u, v) in the graph, vertex 'u' comes before vertex 'v' in the ordering. It's a way to order tasks or events where some tasks depend on others, ensuring that you always perform a task before any task that depends on it.
• A digraph has topological sorting iff it is a DAG.
• There are two algorithms:
  1. DFS
     • Perform DFS traversal, noting the order in which the vertices are popped off the traversal stack.
     • Print the stack in reverse order.
  2. Source-Removal
     • Repeatedely identify and remove a source (vertex without incoming edges), and all the edges incident to it.
     • Repeat until no vertex is left, or there is no source among the remaining vertices.