Question

Q9. Problem-solving techniques (a) Describe the basic principles and efficient operation of the problem-solving technique "divide-and-conquer". 5 marks (b) Illustrate your answer to (a) with a problem that is amenable to this technique, and sketch a solution to this problem that uses the technique. 5 marks

Hi, This question is from python unit

Answer 1

(a)Basic principle of Divide and conquer
step-1 Break the given problem into smaller subproblems of same type.
step-2 Recursively solve these smaller subproblems
step-3 Appropriately combine the answers of subproblem to get answer of main problem.

(b)Take an example to find maximum element in given list using divide and conquer technique.
For this problem,we first divide problem into two smaller subproblems.
find maximum element in both subproblem and return maximum of them.

#Python Program
def findMax(low,high,list1):
if low==high:
return list1[low]
mid = (low + high)//2
max1 = findMax(low,mid,list1)
max2 = findMax(mid+1,high,list1)
if max1>max2:
return max1
else:
return max2

list1 = [5,1,7,9,10,15,2]

print("Maximum element in list1 is ", findMax(0,len(list1)-1,list1))

#Screenshots

File Edit Format Run Options Window Help def findMax (low, high, listi): if low==high: return listi[low] mid = (low + high) //2 maxl = findMax (low,mid, listi) max2 = findMax (mid+1, high, listi) if maxl>max2: return max1 else: return max2 listi = [5,1,7,9,10,15,2] print ("Maximum element in listi is ", findMax (0,len (list1)-1, list1)) Python 3.7.3 Shell - X File Edit Shell Debug Options Window Help Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 21:26:53) [MSC v.1916 32 bit (Inte 1)] on win32 Type "help", "copyright", "credits" or "license()" for more information. RESTART: C:/Users/IshuManish/AppData/local/Programs/Python/Python37-32/max.py Maximum element in listi is 15