$1.[$Searching$,5+10+15$ points$]$ The TV in your house is broken, so you were called upon to fix it $($being a STEM student means that you are able to fix any electronic device no matter your specialization$).$ After trying to find the issue yourself for $6$ hours and reading the documentation for $5$ minutes, you find out that only two chips are broken. There are n spare chips in your toolbox, and each chip ci increases the total voltage usage of the TV by vi units. You want the TV to use the same amount of voltage as before, meaning that the sum of the chips$$ voltage should be as close to vtarget as possible. $($a$)$ Suppose that the toolbox has two chips ci and cj such that vi $+$ vj $=$ vtarget. Devise a O$($n lg n$)$ algorithm that can find those two chips. The toolbox is full of chips, so a O$($n$2)$ algorithm will not do$.$ You don$$t need to provide proof of correctness and termination for this subquestion. Hashmap$-$based solutions will get no credit for the problem. $($b$)$ Since you are a UofT student, two hours later, you invent a black box, for which you know nothing about its run time, that finds all pairs of chips ci and cj that have their vi $+$ vj $=$ vtarget $($a chip can be used in more than one pairs$).$ Prove that the performance of this black box is bound by $($n$2)$ in the worst case.