Please complete the python code and show that code provides correct requested outputs.

from random import uniform

def computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$:

assert n $>=1$

assert len$($c$\_$matrix$)==$ m

assert all$($len$($c$\_$list$)==$ n for c$\_$list in c$\_$matrix$)$

assert len$($d$\_$values$)==$ m

r$\_$values $=[$uniform$(-1,1)$ for i in range$($n$)]$

# your code here

raise NotImplementedError

def testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$:

# always check pre$-$conditions: saves so much time later

assert len$($c$\_$matrix$)==$ m

assert all$($len$($c$\_$list$)==$ n for c$\_$list in c$\_$matrix$)$

assert len$($d$\_$values$)==$ m

assert len$($x$\_$values$)==$ n

# Check how many inequalities satisfied

num$\_$ineqs $=0$

for $($c$\_$list, d$)$ in zip$($c$\_$matrix, d$\_$values$)$:

if sum$([$cj $*$ xj for $($cj$,$ xj$)$ in zip$($c$\_$list,x$\_$values $)])<=$ d$+1$E$-3$:

num$\_$ineqs $=$ num$\_$ineqs $+1$

assert num$\_$ineqs $>=$ m$/2,$ f$\text{'}$ Half number of inequalities to be sat: $\{$m$/2\}$ your solution satisfies: $\{$num$\_$ineqs$\}$ inequalities $\text{'}$

print$(\text{'}$Test Passed'$)$

return

n $=5$

m $=24$

c$\_$matrix $=[$

$[1,-1,0,1,-1],$

$[1,2,0,0,2],$

$[-1,0,1,1,1],$

$[1,0,0,0,-1],$

$[-1,0,0,-1,-1],$

$[1,0,0,1,1],$

$[1,0,-1,1,0],$

$[0,2,1,0,2],$

$[-1,1,1,-1,0],$

$[1,1,1,0,1],$

$[-1,1,1,0,0],$

$[1,1,1,1,0],$

$[-1,1,0,1,-1],$

$[1,-2,0,0,-2],$

$[1,0,1,-1,-1],$

$[1,0,1,0,1],$

$[-1,0,0,1,1],$

$[-1,0,0,1,1],$

$[1,-1,1,1,1],$

$[0,-2,-1,0,2],$

$[-1,-1,-1,-1,0],$

$[-1,1,-1,0,1],$

$[1,0,0,1,0],$

$[-1,0,-1,0,-1],$

$]$

d$\_$list $=[$

$-5,3,-4,-2,-3,-1,$

$-5,3,-4,-2,-3,-1,$

$5,-3,4,2,3,1,$

$5,-3,4,2,3,1,$

$]$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$list$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$list, x$\_$values$)$

print$(\text{'}5$ points'$)$

from random import uniform, randint, seed

## Warning: these are large instances. If your solution takes more than $120$ seconds, then

## chances are that you will not receive any credit for this problem.

def gen$\_$random$\_$instance$($n$,$ m$)$:

c$\_$matrix $=[[$randint$(-5,5)$ for i in range$($n$)]$ for j in range$($m$)]$

d$\_$values $=[$randint$(-10,10)$ for i in range$($m$)]$

return $($c$\_$matrix, d$\_$values$)$

seed$(100001)$

print$(\text{'}$Test # $1\text{'})$

n $=10$

m $=55$

$($c$\_$matrix, d$\_$values$)=$ gen$\_$random$\_$instance$($n$,$ m$)$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$

print$(\text{'}$Test # $2\text{'})$

n $=35$

m $=230$

$($c$\_$matrix, d$\_$values$)=$ gen$\_$random$\_$instance$($n$,$ m$)$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$

print$(\text{'}$Test # $3\text{'})$

n $=100$

m $=550$

$($c$\_$matrix, d$\_$values$)=$ gen$\_$random$\_$instance$($n$,$ m$)$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$

print$(\text{'}$Test # $4\text{'})$

n $=80$

m $=900$

$($c$\_$matrix, d$\_$values$)=$ gen$\_$random$\_$instance$($n$,$ m$)$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$

print$(\text{'}$Test # $5\text{'})$

n $=70$

m $=445$

$($c$\_$matrix, d$\_$values$)=$ gen$\_$random$\_$instance$($n$,$ m$)$

$($k$,$ x$\_$values$)=$ computeApproximateSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values$)$

print$($k$)$

print$($x$\_$values$)$

testSolution$($n$,$ m$,$ c$\_$matrix, d$\_$values, x$\_$values$)$

print$(\text{'}15$ points!$\text{'})$Implement a function comput e$$pproximat esolution with inputs

$,$ : number of variables.

m : number of inequalities

c$\_$matrix : a list of list of coefficients of the LHS of inequalities

$\left[\begin{array}{cc}{c}_{11},\text{d}\text{o}\text{t}\text{s}\text{,}{c}_{1n}& ?\\ c_{21},\text{d}\text{o}\text{t}\text{s}\text{,}{c}_{2n}& ?\\ \text{d}\text{o}\text{t}\text{s}& ?\\ c_{11},\text{d}\text{o}\text{t}\text{s}\text{,}{c}_{an}& ?\end{array}\right]$

Please note python indexes starting from $0.$

d$\_$ualues : a list of RHS coefficients: $d_1,$dots,$d_a$

Your function should retum a pair: $(k,[x_1,$dots,$x_n])$