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?
26 3660
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)
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 :)
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: -
int x2= x*x;
-
int x4= x2*x2;
-
int x8= x4*x4;
-
int x16= x8*x8;
-
// etc. etc.
-
kind regards,
Jos
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,
I'll give you a hint w.r.t. the first question: -
int x2= x*x;
-
int x4= x2*x2;
-
int x8= x4*x4;
-
int x16= x8*x8;
-
// etc. etc.
-
kind regards,
Jos
thankssssss . I am finguring out your hint .
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 ;)
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.
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. :)
I'll give you a hint w.r.t. the first question: -
int x2= x*x;
-
int x4= x2*x2;
-
int x8= x4*x4;
-
int x16= x8*x8;
-
// etc. etc.
-
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!)
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?
Wow! Is this a different person with the same homework problem?
The wonders of Google.
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
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 :))
Actually, I would use recursion.
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
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 ?
[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.
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
Actually, I would use recursion.
But f(x)= f(x/2)*f(x-x/2) including memoization yields 9 multiplications ;-)
kind regards,
Jos
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."
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;
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
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
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
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
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
Sign in to post your reply or Sign up for a free account.
Similar topics
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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. ...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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....
|
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
|
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...
|
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...
| |