Description
1.Heap [10 pt]
Given eight numbers {n1, n2, …, n8}, show that you can construct a heap (either minheap or max-heap) using eight comparisons between these numbers (e.g., comparing n1
and n2 would be one comparison).
2.Median [10 pt]
Describe an efficient algorithm for finding the median of all numbers between two
sorted arrays each of size �. Your algorithm should be asymptotically faster than �(�).
Analyze the running time of your algorithm.
3.Hashing [10 pt]
Given a sequence of inputs 531, 43, 63, 79, 4, 99, 89 and the hash function h(x) = x
mod 10, show the resulting hash table for each of the following cases of conflict
resolution.
(a) Chaining
(b) Linear probing
(c) Quadratic probing
(d) Using a second hash function h2(x) = 7 – (x mod 7)
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.
