Reply
Sun 4 Oct, 2020 08:58 am
Complexity
2) Consider the following code.
void f(m){ // where m is a 2d matrix with fixed rows and columns for d in 0..m.rows(){
if m[d][d]==0{
int i=row_index_with_highest_value_in_column(m,d,d+1); if m[d]!=0{
swap_rows(m,d,i);
} else {continue;}
}
f=m[d][d];
for i in 0..m[d].cols(){ m[d]/=f;} for i in d+1..m.rows(){
f=-m[d];
for k in d..m.cols(){ m[k]+=m[d][k]*f; }
}
}
}
Please estimate the time complexity T(r,c)=… for this procedure. Please give the order of
complexity (O) of T(r,c)
• r is the number of rows
• c is the number of columns
• You may assume that the procedure “swap_rows” has time 3
• You may assume that the procedure “row_index_with_highest_value_in_column” being the maximum
of a list has linear time cost (n) in the number of elements it must search through.
Algorithms
3) Given a set of 2d data points it is always possible to plot a polynomial function through them
all. For instance [(1,5),(7,10),(-5,1),(-6,-6)] can be fitted by
Y=6.74 - 1.6097x-0.198x²+0.071x³
Can you find an algorithm to find these equations in general for any set of points? Discuss the
time
complexity.