Help me with the computer science question below

2. [10 marks] Reductions. A special case of the 3SUM problem from lecture 2 is called 3SUMO: given an array A[1...n] of numbers, decide whether there exist indices i, j, k {1,...,n} (duplicate indices are allowed) such that A[i] + A[j] + A[k] = = 0. Now, we consider the variant (3SUMO-3array): given three arrays of numbers B[1...n],C[1...n) and D[1...n), decide whether there exist indices i, j, k {1,..., n} such that B[i] + C[j] + D[k] = 0. In this question, you are asked to show that the two versions are equivalent by providing reductions from one to another in both directions. Recall that, when you are reducing from problem P1 to problem P2, you assume that you have a subroutine that solves problem P2, and you use this subroutine to design an algorithm for P1. 1 (a) [2 marks] Give a linear time reduction from 3SUMO to 3SUMO-3array and prove correct- ness. (b) 8 marks] Give a linear time reduction from 3SUMO-3array to 3SUMO and prove correct- ness. Hint: consider 3 arrays X[i] = 10 x B[i] + 1, Y [i] = 10 x C[i] + 2 and Z[i] defined in a similar way (but you need to figure it out). Then, somehow combine X, Y and Z. 2. [10 marks] Reductions. A special case of the 3SUM problem from lecture 2 is called 3SUMO: given an array A[1...n] of numbers, decide whether there exist indices i, j, k {1,...,n} (duplicate indices are allowed) such that A[i] + A[j] + A[k] = = 0. Now, we consider the variant (3SUMO-3array): given three arrays of numbers B[1...n],C[1...n) and D[1...n), decide whether there exist indices i, j, k {1,..., n} such that B[i] + C[j] + D[k] = 0. In this question, you are asked to show that the two versions are equivalent by providing reductions from one to another in both directions. Recall that, when you are reducing from problem P1 to problem P2, you assume that you have a subroutine that solves problem P2, and you use this subroutine to design an algorithm for P1. 1 (a) [2 marks] Give a linear time reduction from 3SUMO to 3SUMO-3array and prove correct- ness. (b) 8 marks] Give a linear time reduction from 3SUMO-3array to 3SUMO and prove correct- ness. Hint: consider 3 arrays X[i] = 10 x B[i] + 1, Y [i] = 10 x C[i] + 2 and Z[i] defined in a similar way (but you need to figure it out). Then, somehow combine X, Y and Z