Problem 1. Consider a problem where you are given an array a[ ] of integers of length n, such that the indices are 0,1,,n1. You are also given an integer s. The problem is to determine if there are two integers in the array that sum to s. In other words, does there exist indices i and k such that a[i]+a[k]=s. A brute force approach would be to try all pairs of indices (i,k) and determine if there is a case where a[i]+a[k] =s. But the time complexity would be quadratic with n. (a) [1 pt] Suppose you can use a hash table with chaining such that the table size is 4n. The functions/methods for this table are - insertHashTable(key): Inserts a key in the hash table - findHashTable(key): Returns 'True' if the key can be found in the hash table, and returns 'False' otherwise. Provide an algorithm 'sumExists(key)' that returns 'True' if there are two indices i and k such that a[i]+a[k]= s, and returns 'False' otherwise. Write your algorithm in pseudo code. It should have average time complexity of O(n). You may assume that the average time complexities of insertHashTable and findHashTable are O(1). (b) [1 pt] Provide another implementation of the algorithm 'sumExists(key)' which doesn't use a hash table, but can use the following: - mergeSort(int a[ ], int n ): Sorts the array a[], with length ' n ', using merge sort. The time complexity of your algorithm should be O(nlogn). Write your algorithm in pseudo code