Transform and Conquer

• In the Transformation stae, the problem’s instance is modified to be more manageable.
• 2 stages:
  1. Transform → Convert problem to a simpler instance of the same problem
  2. Conquer → Solve the problem
• There are 3 major variations of Transform and Conquer:
  1. Instance Simplification: Transformation to a simpler or more convenient instance of the same problem
  2. Representation Change: Transformation to a different representation of the same instance
  3. Problem Reduction: Transformation of an instance of a different problem for which an algorithm is already available

Checking Unique Elements in Array

• The brute force algorithm has a worst-case efficiency of $O(n^2)$

• A better approach to this would be to find the uniqueness of the element by pre-sorting (instance simplification)

  ALGORITHM PresortElementUniqueness(A[0...n-1])
  
  	sort array A
  	for i <- 0 to n-2 do:
  		if A[i] = A[i+1] return false
  	return true
  

• Time complexity → $T(n) = T_{sort}(n) + T_{scan} n = O(n \space log n)$

Heap and Heap Sort

• Heap → Partially ordered data structure that is suitable for implementing priority queues. It is a binary tree with keys assigned to its nodes, one key per node.

• Conditions for heap:

  1. Shape → Binary tree is complete. All its levels are full besides the last level
  2. Parental Dominance → The key in each node is greater than or equal to the keys in its children

• Properties of heap:

  1. Binary tree is essentially complete
  2. Parental Dominance
  3. Height = $\lfloor log _2 \space n \rfloor$
  4. Root always has the largest (or smallest) element
  5. A node of a heap with all its descendants is also a heap
  6. A heap can be implemented as an array by recording its elements in the top-down order, from left to right. It is convenient to store the heap’s elements in positions 1 through n of such an array. H[0] is left unused or used to place a sentinel whose value is greater than every other element in the heap.
     1. Parental node keys occupy the first n/2 positions
     2. Leaf keys occupy the last n/2 positions
     3. Children of a key in an array’s parental position i will be in position 2i and 2i+1

  Algorithm HeapBottomUp(H[1...n])
  // Constructs a heap from the elements of a given array
  
  for i <- floor(n/2) downto 1 do:
  	k <- i; v <- H[k]
  	heap <- false
  	
  	while not heap and 2k <= n do:
  		j <- 2k
  		
  		if j < n // there are 2 children
  			if H[j] < H[j+1]:
  				j <- j+1
  			if v >= H[j]:
  				heap <- true
  			else H[k] <- H[j]; k <- j
  	H[k] <- v
  

• Heap sort is a 2-stage algorithm:

  1. Heap construction
  2. Maximum deletions

  • Arrays are eliminated in decreasing order

    

• Complexity of Heap sort ≤ $2n \space log_2n$

• Heap sort can be used to implement priority queues and Dijkstra’s algorithm.

Red-Black Trees

• A balanced tree that assures O (log n) time in worst case.
• BST with one extra tree per node.
• These are binary trees where a particular node has a color (red/black) as a particular attribute.
• These colours are used to ensure that the tree remains balanced during insertions and deletions.