Latest Lists

list of unordered elements?

Given a list of unordered elements and two numbers Devise a divide & conquer based algorithm Count( ) which returns the tuple (c1,c2) where is c1 the number of elements in list A which are less than x and c2 which is the number of elements in list that are greater than y For example, if input list is [5, 3, 2, 10, 9, 16, 4, 5, 11] and x-10 ,y=7 then the procedure returns (6,4). (a) Write the pseudocode for Count( ). Do not use global variables in your code; (b) Write the recurrence relation for the code you wrote in (a); and (c) What is the time complexity of this code?

Public Comments

1. Given a list of unordered elements l and two numbers x,y Well let's just recursively break list l into roughly halves, until we get a list of only one element. and pass down (x,y) Count() should take a list argument, and return a tuple (nx,ny) where nx=no. of entries >x, ny=no. of entries >y Python is a good language to implement this because it can directly handle tuple arguments, no messing with pointers and structs for handling arguments like in C/C++. (a) Write the pseudocode for Count( ). Do not use global variables in your code In fact here's working Python, and it only needs 5 lines of code. def Count(l, x, y): # Base case if len(l)==1: return ( l[0] <x, l[0]>y ) # Recursive case else: midpt = len(l)/2 return Count(l[0:midpt-1], x,y) + Count(l[midpt:], x,y) (b) Write the recurrence relation for the code you wrote in (a); and (c) What is the time complexity of this code? O(N) ; where N = length of input list.