Description
4.Programming [70 pt]
Make sure to write your name and BU ID in a comment at the top of the program,
along with your collaborator’s name and BU ID, if any. To use the compiler on the lab
computers, run “module load gcc” first. Submit only prob4.h.
a) [35 pt]
Implement the function findMedian in prob4.h. Similar to Question 2, the
function should return the median of all numbers between two sorted vectors v1
and v2. However, in this case, the sizes of v1 and v2 may differ. Below some
example input and output.
2
Input: v1 = [1, 2], v2 = [3]
Output: 2
Input: v1 = [1], v2 = [2]
Output: 1.5
Your algorithm should have an asymptotic running time faster than �(� + �)
where � and � are the sizes of the two vectors.
Test your code thoroughly and document your code clearly.
b) [35 pt]
Implement the function maxCollinearPoints in prob4.h. Given a set of points, it
should find the maximum number of points that lie on the same line and
return this set of points. If there is more than one set, return one of them. You
may assume that all the input points are unique and there are at least two
points in the input set. You may find it useful to define lines with slopes and
y-intercepts. Below is an example input and output.
Input: {(1,1), (1,4), (2,3), (3,2)}
Output: {(1,4), (2,3), (3,2)}
Test your code thoroughly and document your code clearly. The most
time/space efficient solution(s) will receive 5 bonus points.