|
Hi,
you really should be able to figure it out yourself.
Just imagine you were to execute the code for some value of n and estimate the
number of important operations; and then for a value twice as large.
The ratio between those two "measures of complexity" should be visible in the big O.
|
|
|
|
|
bosszy wrote: What is there bigO
You should really do your own homework. What do you think it is? You should really try it rather than waiting for an answer. The answer is really easy, and if you can't figure it out, then, well, don't know what to tell you.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
Paul Conrad wrote: don't know what to tell you
you don't know either? 
|
|
|
|
|
Luc Pattyn wrote: you don't know either?
Heck yeah, I know the answer to it (it is a polynomial), but not going to announce it for him to cheat on his assignment.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
|
Assuming n>0, if you want to know how often "sum += j;" is executed, it's n cubed exactly -- never mind the big O.
|
|
|
|
|
I am trying to implement Choleski's algorithm for a 5 by 5 matrix. When I run compare the results to Sci Lab, I find that my answer is different. Therefore, I am assuming that I am wrong. The code below is based on an algorithm given in the book "Numerical Analysis" by Burden, Faires
and Reynolds. Here is code:
void
Cholesky(double a[5][5], double l[5][5] )
{
const int n = 5;
l[0][0] = sqrt(a[0][0]);
for( int j=2; j<=n; j++ )
l[j-1][0] = a[j-1][0]/l[0][0];
for( int i = 2 ; i<=(n-1); i++ ) {
double sum = a[i-1][i-1];
for( int k=1; k<=i-1; k++ )
sum -= (l[i-1][k-1])*(l[i-1][k-1]);
l[i-1][i-1] = sqrt(sum);
for( int j = i+1; j<=n; j++ ) {
double sum = a[j-1][i-1];
for( int k = 1; k <= (i-1); k ++ )
sum -= l[j-1][k-1] * l[i-1][k-1];
l[j][i] = sum/l[i-1][i-1];
}
}
double sum = a[n-1][n-1];
for( int k = 1; k<=(n-1); k++ )
sum -= l[n-1][k-1] * l[n-1][k-1];
l[n-1][n-1] = sqrt(sum);
}
I am hoping that somebody can tell me where my problem is. Thanks.
Bob
|
|
|
|
|
Hi Bob,
I think you should check your indices. I prefer the Numerical Recipes in C[^] version. See Chapter 2 Solution of Linear Algebraic Equations for other code. The Cholesky code for the Numerical Recipes routine is:
#include <math.h>
void choldc(float **a, int n, float p[])
{
void nrerror(char error_text[]);
int i,j,k;
float sum;
for (i=1;i<=n;i++) {
for (j=i;j<=n;j++) {
for (sum=a[i][j],k=i-1;k>=1;k--) sum -= a[i][k]*a[j][k];
if (i == j) {
if (sum <= 0.0)
nrerror("choldc failed");
p[i]=sqrt(sum);
} else a[j][i]=sum/p[i];
}
}
}
</math.h>
Try the NR code and see how it works.
|
|
|
|
|
Thanks for the response, it was very helpful.
Bob
|
|
|
|
|
BobInNJ wrote: Thanks for the response, it was very helpful.
No problem!
|
|
|
|
|
Hi,
BobInNJ wrote: l[j][i] = sum/l[i-1][i-1];
IMO this is where the problem is.
Some more comments:
1.
the first few lines are not really useful
l[0][0] = sqrt(a[0][0]);
for( int j=2; j<=n; j++ )l[j-1][0] = a[j-1][0]/l[0][0];
you could get them for free by starting the next for loop with i=1 instead of i=2
2.
you are aware you could do the same thing in place? i.e. you can store l in a, you don't really need a separate array for input and output.
|
|
|
|
|
Has anyone implemented clarke and wright algorithm with multiple truck capacities.If yes please help me with implementing the same. Thanks
Hemanth
|
|
|
|
|
Try this: Single-Depot VRP[^].
They don't give you the code but there's more than enough information to show you how to implement it.
|
|
|
|
|
plz help me in writing an algorithm of the following problem
Problem:
"Let S be a set of n disjoint line segments in the plane, and let p be a point not on any of the line segments of S. We wish to determine all line segments of S that p can see, that is, all line segments of S that contains some points q so that the open segment pq does not intersect any line segment of S. Give an O(nlogn) time algorithm for this problem that uses a rotating half line with its endpoint at p."
regards,
Irfan
|
|
|
|
|
Sounds like homework to me.
What have you done to solve this yourself? Any code that doesn't work? Google is your friend!
Dave.
|
|
|
|
|
you are a good algorithm writer as I think.
please help me in this regard. I could not find anything relevent to this problem.
kindly do this for me please.
I am waiting for your positive response.
regards,
|
|
|
|
|
Here is an algorithm that solves your particular problem and many others as well:
1. formulate your problem (you did very well at that)
2. open the Google search page and enter the entire problem description into the textbox
3. click the "Search" button
4. wait a few seconds to see a small number of hits out of an often huge number of hits.
5. scan the list, open the ones that look most promising.
6. if necessary, click for the next page of hits.
7. repeat steps 4,5,6 if no solution found yet.
For your particular problem, there are over 50,000 hits. Now only two possibilities remain:
A. some of those contain a decent answer; problem solved.
B. they all repeat the problem without offering the solution; it is therefore safe to assume nobody knows the answer, so don't waste your time and ours, go do something completely different instead.
Good luck.
|
|
|
|
|
Sorry, but this is the worst advice I can imagine. 
Do NOT search google! SOLVE the problem! And don't crib...
Greetings - Gajatko
Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.
|
|
|
|
|
gajatko wrote: Do NOT search google! SOLVE the problem!
I agree. But there is nothing wrong with researching the problem on google for the sake of better clarity or understanding of the problem, but using google just to find an answer to the problem is a whole different matter.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
Thanks. BTW I think that a glass of wine helps more than hours spent on googling around.
After this pointless and amazing[^] discusion, I'll try to finally figure out the thing. 
Greetings - Gajatko
Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.
|
|
|
|
|
gajatko wrote: After this pointless and amazing[^] discusion, I'll try to finally figure out the thing.
I remember seeing that. Total 
I would like to figure it out, too, but I have other priorities 
gajatko wrote: BTW I think that a glass of wine helps more than hours spent on googling around.
Yup, any alcoholic beverage can be useful when researching 
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
Nobody is going to do a homework problem for you - that defeats the entire point of homework. Homework is given to you so that you learn from it. Having somebody else hand you the answer is not learning. In fact, soliciting answers like this is equivalent to plagiarism because you basically hand in someone else's work. Plagiarism is a serious offense in most educational institutions.
That having been said, it is okay to ask for help when you have demonstrated some effort and are stuck on a particular aspect of the problem and its solution. So, if that is the case, you should discuss your work so far and point out the specific issue you are struggling with. You will receive much more constructive responses using that approach.
|
|
|
|
|
73Zeppelin wrote: Plagiarism is a serious offense in most educational institutions.
I second that. Saw a guy one time who got caught cheating on a test in the class before my class, and the instructor really laid down the law on him.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
You already have a clue: a rotating halfline. I'd try to represent the points in polar coordinates with P as a centre, then sort them by angles and do something with it.
Greetings - Gajatko
Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.
|
|
|
|
|
At last a sensible reply! The original question as phrased was out of order sure but perhaps the guy doesn't have a clue where to start asking how to do this, perhaps its difficult phrasing the question in a second language.
Why not just offer some advice as Gajatko has done and try to stimulate a discussion instead of simply ranting about homework blah blah blah. It always sounds to me like you all have a massive chip on the shoulders - nobody ever helped you with your homework is that it?
Nice one Gajatko
Apathy Rules - I suppose...
Its not the things you fear that come to get you but all the things that you don't expect
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
