CS330 HW03

Problem 2 §

Subproblem (a) §

Idea: a majority element must be majority in either of the two halves of an array

Algorithm:

# array to check
A[1..n]
 
function Count(l, r, elem)
	# base case
	if l = r
		return 1
 
	# divide array into two, and count there
	m = ceiling((l+r)*0.5)
	l_count = PCount(l, m, elem)
	r_count = PCount(m+1, r, elem)
 
	# return the sum of left and right counts
	return l_count + r_count
 
function MajorityElem(l,r)
	# base case
	if l = r
		return A[l] 
 
	# check left, right half majority
	m = ceiling((l+r)*0.5)
	left_majority = MajorityElem(l, m)
	right_majority = MajorityElem(m+1, r)
 
	## check consensus
 
	# check no consensus first; if one is null return the non-null
	if left_majority == NULL and right_majority != NULL:
		return right_majority
	if left_majority != NULL and right_majority == NULL:
		return left_majority
 
	# there cannot be a both no consensus case
 
	# consensus agrees
	if left_majority == right_majority:
		return left_majority
	
	# consensus disagrees
	else if left_majority != right_majority:
 
		# count the majority
		left_count = Count(l, r, left_majority)
		right_count = Count(l, r, right_majority)
		
		# if tied, no consensus
		if left_count == right_count
			return NULL
		
		# winner exists, return the winner
		return left_count > right_count ? left_majority : right_majority
		

• Count function: $T(n)\le 2T\left(\frac{n}{2}\right)+O(1)=O(n)$
• MajorityElement function: $T(n)\le 2T\left(\frac{n}{2}\right)+2\cdot O(n)$
  • First term: recursive calls
  • Second term: calls Count
  • Solution: $T(n)=O(n\log n)$ (same recurrence relation as mergesort)
• Correctness (Brief argument):
  • Base case: in $n=1$ the element is majority element
  • IH: Assume MajorityElement(k/2) is correct.
  • IS:
    1. If one of them has no majority but the other ones does, the one with majority must be the true majority because of an element exists in more than half of the total array it must be that in one of the halves it will be the majority.
    2. If both halves have a majority, then the one that has more counts in the total array wins
    3. There cannot be a both halves no-majority case as explained in (1)

Subproblem (b) §

Parallel version of algorithm

# array to check
A[1..n]
 
function PCount(l, r, elem)
	# base case
	if l = r
		return 1
 
	# divide array into two, and count there
	m = ceiling((l+r)*0.5)
	spawn l_count = PCount(l, m, elem)
	spawn r_count = PCount(m+1, r, elem)
	sync
	
	# return the sum of left and right counts
	return l_count + r_count
 
def MajorityElem(l,r)
	# base case
	if l = r
		return A[l] 
 
	# check left, right half majority
	m = ceiling((l+r)*0.5)
	parallel left_majority = MajorityElem(l, m)
	parallel right_majority = MajorityElem(m+1, r)
 
	## check consensus
 
	# check no consensus first; if one is null return the non-null
	if left_majority == NULL and right_majority != NULL:
		return right_majority
	if left_majority != NULL and right_majority == NULL:
		return left_majority
 
	# there cannot be a both no consensus case
 
	# consensus agrees
	if left_majority == right_majority:
		return left_majority
	
	# consensus disagrees
	else if left_majority != right_majority:
		# count the majority
		left_count = PCount(l, r, left_majority)
		right_count = PCount(l, r, right_majority)
				
		# if tied, no consensus
		if left_count == right_count
			return NULL
		
		# winner exists, return the winner
		return left_count > right_count ? left_majority : right_majority
 

• PCount analysis
  • Span: $T_{\infty }(n)\le T\left(\frac{n}{2}\right)+O(1)=O(\log n)$
  • Work: $W_{\infty }(n)\le 2T\left(\frac{n}{2}\right)+O(1)=O(n)$
  • majority element determination can be run in parallel
• Span: $T_{\infty }(n)\le T\left(\frac{n}{2}\right)+O(\log n)=O({\log }^{2}n)$
  • First term: parallel recursive call
  • Second term: compare the majority
  • Solution
    • Using the master theorem, we see ${\log }_{b}a={\log }_{2}1=0$ and the for the residual term $c_{crit}=0$.
    • This is the second case from which we infer $T_{\infty }(n)=O({\log }^{2}n)$
• Work: $W_{\infty }\le 2T\left(\frac{n}{2}\right)+O(n)=O(n\log n)$

Problem 3 §

function PCountAndArrange(l,r) => int
	# base case; if zero, return count 1; else return count 0
	if l=r
		return A[l] == 0 ? 1 : 0
 
	# recursive call & count
	m = ceiling((l+r)*0.5)
	k = spawn PCountAndArrange(l, m)
	n = spawn PCountAndArrange(m+1, r)
	sync
	zerocount = k + n
 
	# rearrange the left half zeros with right half numbers
	parallel for i = m-k+1 .. m
		B[i+k] = A[i]
	parallel for i = m .. m+k
		B[i-k] = A[i]
	parallel for i = m-k+1 .. m+k
		A[i] = B[i]
 
	# return the count
	return zerocount
	

• Processor count: $O(n)$
  • PCountAndArrange recursive calls take $O(n)$ processors
  • rearrange takes $O(n)$ processors for each parallel for loop
• Span: $T_{\infty }(n)\le T\left(\frac{n}{2}\right)+O(1)=O(\log n)$
• Work: $W_{\infty }(n)=2T\left(\frac{n}{2}\right)+O(n)=O(n)$
  • First term for recursive call
  • Second term for rearranging

Problem 4 §

# A[(int, int)] is the structure of the array
 
function FindMaximal()
	max_y = -Infinity
	
	
	# Sort the points in decreasing order by x-coordinate
	ReverseMergeSort(A[])
	max_y = A[0]
	result = [A[0]]
	
	# traverse in reverse x direction (right to left)
	for p in A
		# if y is bigger than anything seen before it's maximal
		if p.y > max_y then
			result.append(p)
			max_y = p.y
			
	return result

• ReverseMergeSort $O(n\log n)$
• FindMaximal $T(n)=O(n)+O(n\log n)=O(n\log n)$
• Correctness (Brief argument):
  • The rightmost element must be the maximal element
  • If the current element has a higher y value than any other element on the right side of it, it must be a maximum
  • If the current element has a lower y value than another point on the right of it, it is dominated by that point and thus cannot be a maximum

# A[(int, int)] is the structure of the array
 
function isDominant((x1,y1),(x2,y2))
	# first is dominant
	if (x1 >= x2 and y1 > y2) or (x1 > x2 and y1 >= y2)
		return 1
	# second is dominant
	if (x2 >= x1 and y2 > y1) or (x2 > x1 and y2 >= y1)
		return -1
	# none are dominant
	else
		return 0
		
 
function PSortedSubtract(A[1..n],B[1..m])
	parallel for i = 1..n
		if BinarySearch[A[i],B] == False
			C.append(A[i])
 
function PFindDoms(l, r)
	# base case
	if l=r
		return l
	
	# get indicies of domannt points from left and right half
	m = ceiling((l+r)*0.5)
	ldoms = spawn PFindDoms(l,m)
	rdoms = spawn PFindDoms(m+1,r)
	sync
 
	nondoms = []
	parallel for i = l..m
		parallel for j= m+1..r
			# either one is dominant drop the non-dominant
			if isDominant[A[i],A[j]] == 1
				nondoms.add(j)
			if isDominant[A[i],A[j]] == -1
				nondoms.add(i)
				
	PMergeSort(nondoms)
	
	return SortedSubstract((ldoms + rdoms), nondoms)
 
function FindMaximal()
	# mergesort based on the x values of the array
	XMergeSort(A)
	return FindDoms(l, r)
 

• isDominant span: $O(1)$
• PSortedSubtract
  • span: $T_{\infty }(n)=O(\log n)$
  • work: $W_{\infty }(n)=O(n\log n)$
• PFindDoms
  • span: $T(n)=T\left(\frac{n}{2}\right)+O(1)+O({\log }^{3}n)+O(\log n)=O({\log }^{4}n)$
    • first term: parallel recursion
    • second term: parallel comparison of dominant points
    • third term: PMergeSort
    • fourth term: SortedSubtract
    • Second case using master theorem: $O({\log }^{4}n)$ time.