Analysis Questions...

[kim6987]

if anyone know, plz help me

1.Show that X^62 can be computed with only 8 multiplications .

2.Programs A and B are analyzed and found to have worst-case running times no greater than 150NlgN and N^2, respectively. Answer the following questions, if possible:
1. Which program has the better guarantee on the running time, for large values of N (N > 10,000)?
2. Which program has the better guarantee on the running time, for small values of N (N < 100)?
3. Which program will run faster on average for N = 1000?
4. Is it possible that program B will run faster than program A on all possible inputs?

[Ganon11]

Why not show us what you have attempted on these problems, and we can help you that way, rather than giving you answers outright? (And what book are you using for your DSA class? Those questions look remarkably like my own homework)

[kim6987]

Why not show us what you have attempted on these problems, and we can help you that way, rather than giving you answers outright? (And what book are you using for your DSA class? Those questions look remarkably like my own homework)

really?
i've read it and I find it so difficult :( .
I do not understand the lecture much.
the due date of these ex. is Friday (midnight)
i'll read the lecture note again and try to do them.
if I can not do them or need some helps , I will ask you all again on Thursday.
thanks. yes , you'r rite, I should do by myself first :)

[JosAH]

really?
i've read it and I find it so difficult :( .
I do not understand the lecture much.
the due date of these ex. is Friday (midnight)
i'll read the lecture note again and try to do them.
if I can not do them or need some helps , I will ask you all again on Thursday.
thanks. yes , you'r rite, I should do by myself first :)

I'll give you a hint w.r.t. the first question:

[code=c]
int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;
// etc. etc.
[/code]

kind regards,

Jos

[kim6987]

about the ex.2 ,
the greater the value of 150Nlg2N and N^2, the more slowly the program run.
so just compute and compare the 150NlgN and N^2,
with small value of N (N<100),
4 example, N = 2^6 = 64
150NlgN = 150*64*lg2^6=15 0*54*6
N^2 = 64*64
we see 150NlgN > N^2 so A run slower than B

by constrast, with N>10.000 150NlgN < N^2 so A run faster than B

is this correct ?

but I still stuck at the question 4,

[kim6987]

I'll give you a hint w.r.t. the first question:

[code=c]
int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;
// etc. etc.
[/code]

kind regards,

Jos

thankssssss . I am finguring out your hint .

[kim6987]

Why not show us what you have attempted on these problems, and we can help you that way, rather than giving you answers outright? (And what book are you using for your DSA class? Those questions look remarkably like my own homework)

my book is "data structure and algorithm" by ALFREDV.AHO ...(1983)
I don't know why i'm learning C but the coursce book ( that book ) is in Pascal .

could you recommand some books of this subject in C ? ( I mean some links that I can download ;)

[kreagan]

about the ex.2 ,
the greater the value of 150Nlg2N and N^2, the more slowly the program run.
so just compute and compare the 150NlgN and N^2,
with small value of N (N<100),
4 example, N = 2^6 = 64
150NlgN = 150*64*lg2^6=15 0*54*6
N^2 = 64*64
we see 150NlgN > N^2 so A run slower than B

by constrast, with N>10.000 150NlgN < N^2 so A run faster than B

is this correct ?

Yes. I would suggest searching "Big O notation" if you are still confused.

but I still stuck at the question 4,

I would view the question as: "Is it possible that program B will run faster than program A on all possible NUMBER OF inputs?" You indirectly answered the question.

[kreagan]

my book is "data structure and algorithm" by ALFREDV.AHO ...(1983)
I don't know why i'm learning C but the coursce book ( that book ) is in Pascal .

could you recommand some books of this subject in C ? ( I mean some links that I can download ;)

I used Introduction to Algorithms by Thomas H. Cormen. Algorithms is about the math/technique than the language - it shouldn't matter if your book is in Pascal.

Instead of using books, I would suggest "Google". It's a really cool search engine (you might have heard of). You can type in the Algorithm, probably click on a wikipedia link (also something you should become familiar with), avoid the myspace link (not going to help you), and do a little reading. :)

[tuananh87vn]

I'll give you a hint w.r.t. the first question:

[code=c]
int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;
// etc. etc.
[/code]

kind regards,

Jos

int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;

I add:
int x^32=x^16*x^16
int x^64=x^32*x^32
int x^62=x^64*(1/x*x)


there're 8 asterisks (*) so it should be 8 multiplications . Is that what u meant?(or how idiot i am!)

[kreagan]

int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;

I add:
int x^32=x^16*x^16
int x^64=x^32*x^32
int x^62=x^64*(1/x*x)


there're 8 asterisks (*) so it should be 8 multiplications . Is that what u meant?(or how idiot i am!)

Wow! Is this a different person with the same homework problem?

[sicarie]

Wow! Is this a different person with the same homework problem?

The wonders of Google.

[JosAH]

int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;

I add:
int x^32=x^16*x^16
int x^64=x^32*x^32
int x^62=x^64*(1/x*x)


there're 8 asterisks (*) so it should be 8 multiplications . Is that what u meant?(or how idiot i am!)

A division is equivalent to a multiplication ... so I count nine multiplications here.

kind regards,

Jos

[tuananh87vn]

A division is equivalent to a multiplication ... so I count nine multiplications here.

kind regards,

Jos

sounds better.. I just intended to put x^2 as the divisor but somehow didn't count the division (then there were only 7 multiplications ) so I changed it to x*x. So finally we get:
int x2= x*x;
int x4= x2*x2;
int x8= x4*x4;
int x16= x8*x8;
int x^32=x^16*x^16
int x^64=x^32*x^32
int x^62=x^64* 1/x^2

(sounds funny cuz we can simply write the last line as x^62=x^64/x^2)

but how can we then put it into C code? use a for loop?

Wow! Is this a different person with the same homework problem?

great problem faces great people :))

[Ganon11]

Actually, I would use recursion.