473,320 Members | 2,088 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Analysis Questions...

kim6987
12
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?
Sep 10 '07 #1
26 3660
Ganon11
3,652 Expert 2GB
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)
Sep 10 '07 #2
kim6987
12
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 :)
Sep 10 '07 #3
JosAH
11,448 Expert 8TB
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:

Expand|Select|Wrap|Line Numbers
  1. int x2= x*x;
  2. int x4= x2*x2;
  3. int x8= x4*x4;
  4. int x16= x8*x8;
  5. // etc. etc.
  6.  
kind regards,

Jos
Sep 10 '07 #4
kim6987
12
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=150*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,
Sep 11 '07 #5
kim6987
12
I'll give you a hint w.r.t. the first question:

Expand|Select|Wrap|Line Numbers
  1. int x2= x*x;
  2. int x4= x2*x2;
  3. int x8= x4*x4;
  4. int x16= x8*x8;
  5. // etc. etc.
  6.  
kind regards,

Jos
thankssssss . I am finguring out your hint .
Sep 11 '07 #6
kim6987
12
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 ;)
Sep 11 '07 #7
kreagan
153 100+
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=150*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.
Sep 11 '07 #8
kreagan
153 100+
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. :)
Sep 11 '07 #9
I'll give you a hint w.r.t. the first question:

Expand|Select|Wrap|Line Numbers
  1. int x2= x*x;
  2. int x4= x2*x2;
  3. int x8= x4*x4;
  4. int x16= x8*x8;
  5. // etc. etc.
  6.  
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!)
Sep 11 '07 #10
kreagan
153 100+
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?
Sep 11 '07 #11
sicarie
4,677 Expert Mod 4TB
Wow! Is this a different person with the same homework problem?
The wonders of Google.
Sep 11 '07 #12
JosAH
11,448 Expert 8TB
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
Sep 11 '07 #13
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 :))
Sep 12 '07 #14
Ganon11
3,652 Expert 2GB
Actually, I would use recursion.
Sep 12 '07 #15
kim6987
12
I’m not good at math at all. So don’t laugh at me if I think simply like this :

1. int x^2= x*x;
2. int x^4= x^2*x^2;
3. int x^8= x^4*x^4;
4. int x^16= x^8*x^8;
5. int x^62;
6. x^62 = x^2 * x^2 * x^2 * x^4 * x^4 * x^8 * x^8 * x^16 *x^16
Sep 13 '07 #16
kim6987
12
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. :)
I definitely might have heard of and even witness the miracle of GOOGLE.
But rather than wandering tens or thoundsands of pages be4 stopping at what i need, some experiences of yours may help me speeding up my learning.
Recommendations and advices are always valuable to me .
I’m a little bit upset when asking someone and receive an answer : “Google it ”
Of course i dare not bother you( or waste my question ) if I can find it in GOOGLE

[quote]great problem faces great people :))[quote]

tuananh87vn :sounds great that you have the same problem with me. can we make friend ?
Sep 13 '07 #17
[quote=kim6987]I definitely might have heard of and even witness the miracle of GOOGLE.
But rather than wandering tens or thoundsands of pages be4 stopping at what i need, some experiences of yours may help me speeding up my learning.
Recommendations and advices are always valuable to me .
I’m a little bit upset when asking someone and receive an answer : “Google it ”
Of course i dare not bother you( or waste my question ) if I can find it in GOOGLE

[quote]great problem faces great people :))

tuananh87vn :sounds great that you have the same problem with me. can we make friend ?
Hi Kim6987! I also have to face the same problem with you. I think that your solution for the 1st exercise quite easy to understand. I also solve it like you.
Sep 13 '07 #18
kreagan
153 100+
I definitely might have heard of and even witness the miracle of GOOGLE.
But rather than wandering tens or thoundsands of pages be4 stopping at what i need, some experiences of yours may help me speeding up my learning.
Recommendations and advices are always valuable to me .
Well, the tone was facetious. Nonetheless, my comment is still a recommendation. The internet has A LOT of data on algorithms which are more complete than what we can tell you, and probably more understandable than most text books out there.

As for "good" text books, I haven't come accross a good algorithms book. (My Algorithm text book wasn't great) The reference texts that I used were for understanding the math behind the algorithm.

Great for Graph Theory Problems. Its a cheap fun book! But if this for a low level algorithm class, this book will be more complex. (It was a grad level math class text)
Applied Combinatorics

This is also a great Math book I refered to for Algorithms.
Discrete Math
Sep 13 '07 #19
JosAH
11,448 Expert 8TB
Actually, I would use recursion.
But f(x)= f(x/2)*f(x-x/2) including memoization yields 9 multiplications ;-)

kind regards,

Jos
Sep 13 '07 #20
Ganon11
3,652 Expert 2GB
True, but the question did not say, "Write a program to compute X^62 in 8 multiplications." It just said, "Show how to compute X^62 in 8 multiplications."
Sep 13 '07 #21
actually we shouldn't put it into program, cuz no integer variable's able to contain the value of x^62. it'd be be algorithm only and below is my finality:
x2=x*x;
x4=x2*x2;
x8=x4*x4;
x12=x8*x4;
x24=x12*x12;
x48=x24*x24;
x60=x48*x12;
x62=x60*x2;
Sep 14 '07 #22
kim6987
12
great problem faces great people :))

Hi Kim6987! I also have to face the same problem with you. I think that your solution for the 1st exercise quite easy to understand. I also solve it like you.
the "wonder of google" told me that you are taking the same course with me . I knew who you are :) .

well , I guess that many others who " google" this excercise may come across to this forum :)))

I also found the key for the excerisce 2 in some corners of the net and I will post it here . have a look :
::Posting answers is like spoonfeeding code, so it was snipped::
they didn't explain

I can understand a,b,c but the answer d ? I'm still confused
Sep 14 '07 #23
JosAH
11,448 Expert 8TB
True, but the question did not say, "Write a program to compute X^62 in 8 multiplications." It just said, "Show how to compute X^62 in 8 multiplications."
Also true but recursion that chops the exponents in half, finally uses 9 multiplications
and it's not the way to go here; see a previous reply for the correct solution.

kind regards,

Jos
Sep 14 '07 #24
JosAH
11,448 Expert 8TB
x2=x*x;
x4=x2*x2;
x8=x4*x4;
x12=x8*x4;
x24=x12*x12;
x48=x24*x24;
x60=x48*x12;
x62=x60*x2;
Yep, that's the one. Finding the optimal value for these type of problems is NP,
they're nasty little problems.

kind regards,

Jos
Sep 14 '07 #25
hey , my friends, ^^
I have another solution :
x*x=x^2
x^2*x=x^3
x^3*x^3=x^6
x^6*x^6=x^12
x^12*x^3=x^15
x^15*x=x^16
x^16*x^15=x^31
x^31*x^31=x^62
hope we get good marks in hw 2:d
Sep 14 '07 #26
JosAH
11,448 Expert 8TB
x*x=x^2
x^2*x=x^3
x^3*x^3=x^6
x^6*x^6=x^12
x^12*x^3=x^15
x^15*x=x^16
x^16*x^15=x^31
x^31*x^31=x^62
Yep, that's another one; well done. A nice (and dfficult) asignment would be:
given an exponent, list the minimal number of multiplications to construct a
certain number raised to that exponent.

kind regards,

Jos
Sep 14 '07 #27

Sign in to post your reply or Sign up for a free account.

Similar topics

3
by: Ste | last post by:
Hello, my goal would be implementing some keystroke analysis using php. I'm a novice in php, so i ask your advice: according to you, is it possible to log each keystroke client-side even if php is...
1
by: Jens Nordahl | last post by:
On a large scale C++ project we are considering to make a static code analysis tool capable of giving answers to high level questions like (examples): - Which entry points on this layer in the...
3
by: phil789 | last post by:
Hi, My questions are about run-time analysis tools like purify. Do you think that such a tool is usefull when developping? Is there some others tools like purify? What tool do you recommend when...
0
by: exits funnel | last post by:
Hello, I apologize if this question is a bit vague and slightly off topic but I couldn't find an Analysis Services and/or ODBO specific newsgroup. In any event, I'm trying to address an issue...
1
by: joeyp | last post by:
hello! i'm looking for resources on database analysis. my main questions are: how does one determine the primary key of a table, and, how does one determine the relationships between the...
0
by: Larry Lard | last post by:
Recently we've been on a code quality drive and have eliminated all compilation warnings from our code. To preserve this state, we've turned 'Treat warnings as errors' to 'All' in all our projects...
1
by: ray pulbrook | last post by:
My questions are can you use access to query correlation and regression analysis or should i link an excel spreadsheet to the database that has those functions specific to the analysis. if you can do...
4
by: yogi_bear_79 | last post by:
I am stuck on a few open-book multiple choice questions for this class. I have answers, but I can not back them up. Any insight would be helpful, a link to read, or just hey dummy you are wrong. ...
4
by: yogi_bear_79 | last post by:
Distant learning course. This is a self-taught open-book test. I have read the book over & over, I even found a PDF version and searched it. I've combed the net and found some good resources...
2
jwwicks
by: jwwicks | last post by:
A Guide for the Beginning CIS Student Introduction It's that time again. A new semester is starting and CIS students all over the country are beginning to program. It can be an overwhelming...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.