Please answer both 1 and 2, thanks! Also, it can be written in Pseudocode

Problem 4. (20 pts) This is your first programming assignment in this semester. To see in what format we expect you to submit your solution, please see the guidelines posted on piazza. Your program will answer the question whether a given sequence of integers contains three elements that sum to zero. You will write two algorithms (functions) called zerosum and zerosumfaster. The functions should take as input a sequence of n integers x1,x2, , xn (each integer may be positive or negative and the sequence may contain duplicates). You may assume the sequence is given in form of an ordered list. The function should output either a set of three distinct indices {i, j, k} such that zi + + zk = 0 if such a set exists, and "No" otherwise (Note that you need to output the original indices and not the value of the integers.) If there are multiple qualifying triples the function will only output the first it finds 1. First find an algorithm, named zerosum, that can solve this problem in time O(n2 log n) without using any data structures more advanced than lists and sets 2. It is possible to speed up your algorithm to run in O(n2) time by using some more advanced data structure Find this algorithm, called zerosumfaster Whenever you are asked to give an algorithm you need to prove that it is correct and analyze its running time Please write the proof of correctness in the text of your homework submission. You may write the running time analysis either in the text or as comments in your code. Make sure that your comments are verbose enough to understand your argument (e.g. writing O(n) without explanation is not acceptable. Writing "for loop has O(n) iterations, each requires a constant number of additions" is a good explanation.)