Dear students

I talked in the class regarding activities that will be done in or outside the class. This is the first one which is outside the class. Please make a group of $4$ people to work on the problem.

Consider the problem of three sum: Given an array of n integers and an integer t$,$ find indices of three integers x$,$ y and z $($in three different indices$)$ such that x$+$y$+$z $=$t$,$ or return none if there are no such three integers.

The following algorithm solve the problem with time complexity of O$($n$^3)$

iterative version:

for i from $1$ to n$-2$

for j from i$+1$ to n$-1$

for k from j$+1$ to n

if A$[$i$]+$A$[$j$]+$A$[$k$]=$ t

return i$,$ j$,$ k

return none

recursive version:

ThreeSum$($A$,$t$,$i$,$j$,$k$)$

if i $>$ n$-2$

return none

else

if j$>$n$-1$

return ThreeSum$($A$,$t$,$i$+1,$ i$+2,$i$+3)$

if k$>$n

return ThreeSum $($A$,$t$,$i$,$ j$+1,$j$+2)$

if A$[$i$]+$ A$[$j$]+$ A$[$k$]=$ t

return i$,$j$,$k

else

return ThreeSum $($A$,$t$,$i$,$ j$,$k$+1)$

First, design a O$($n$^2)$ algorithm for the three sum problem.

Second, program using C language the two algorithms and compare the number of comparisons and the time in seconds.