For problems 4 and 6, they say something like log n, can we assume that it is in base 2 or should we do base 10. In the solved exercise 1 than state log2(n)???
I don't believe this will affect the correct answer.
It may help to remember (or learn) how to convert between logs in different bases. log_A (x) = log_B (x) * log_A (B) (To check this, raise A to the right-hand side, and simplify using laws of exponents and logs.)
I did the brute force way picking different n's for some of #2, but that seems not very efficient but it worked.
Also, I had a question on 6b...I am confused on how to "reduce" the program to C*f(n), it seems easy to prove the upper bound but getting the lower bound is :O.
For example,
i = 1: N+1 j = i+1:N+1 the upper bound would be n*(n-1) = n^2 - n = O(n^2), but how would I find the lower bound...any small hints would be much appreciative! :)
With the EHarmony Problem, the upper bound is that all man have to ask all women to get the final Stable matching which is n*n = n^2 and the lower bound is if the input mensPref has every man wanting a different woman such that every man asks exactly one woman therefore the lower bound is n*(1) == omega(n);
This means that it is not tight bounded by n or n^2 because the upper != lower...but I could be wrong on this as well!
If I go thru the loops at every step i, and add up the j interations that would that be the bare minimum or lower bound? It seems the j loop has a sequence of n-1 + ... 1 (had to review sequences been awaile) then that would be the lower bound because it would always do this many interations???
Yes, Krista, that was I was wondering last night. Here was my question to the Professor:
I think I am done with the rest of the homework, but I am stuck with the b part of #2.6. I calculated the number of iterations of the inner loop, but I am not sure how to calculate the number of addition operations. Would you mind to give me a hint? *****************************
Here is his answer to me:
You don't have to compute the exact number of addition operations, just get approximate answers that are correct up to a constant factor. I suggest you convert the pseudocode into actual (Java) code -- that will make it much more clear how many addition operations are done in the line of pseudocode talking about the "sum of entries".
By the way, Krista, you might want to recalculate your O(.). The upper bound would be all iterations of outer loop * all iterations of inner loop * summations of the array elements.
Hey Lucia, Thanks for posting the response for everyone, I was just doing an example of just the double loop because did not want to get too in depth so I pretended that I just had i and j loops and nothing else.
I was also thinking of doing an average of the additions but do I take the i = 1: n/2 or i = n/2+1 to n because when I use a small example of say n = 4 it seems that the additions are much higher for lower i's and go to zero at i = n, should I take the larger avg or the lower???
If I want to prove that it is lower bounded than I would expect to take the i = 1: n/2 because it will be closer to f(n) of part a.
I'd say you take the larger avg, because the algorithm does calculate everything and the lower avg will give you the lower number, which will be unrealistic.
for i = n-2 to n, you make 3 additions, which will run in O(1). Which is bogus, because you still have to calculate i = 1 to n and it will take more than O(1). Right?
When I answered Lucia's question before, I was confusing problems 2 and 4---sorry if this caused any confusion.
Advice on problem 2d: one answer---easy with a calculator---use binary search, with a "guess and check" approach. Start with values of n for which n*log(n) is too big, and too small, and then try their average as your next value. Keep going until you pin down the correct n within 1.
answer #2. Use math software. For free, on the internet, go to http://www.wolframalpha.com/ Type "solve(n log(2,n) = 100)" in the box, and hit enter. It will give you the answer, 22.32 (always make sure it has parsed your request properly in its "input interpretation") Of course, 100 should be replaced with the appropriate number for the problem. Matlab is another good choice, free on the CS machines, as are Maple and Mathematica, for instance, if you happen to own one.
Note that wolframalpha also shows you a graph of the function. Often, graphing the function is more helpful than just computing the answer.
Hope this helps!
Reminder: my office hours are at 2:00 today, Farris 149.
@Krista, a hint for finding the lower bound in problem 2.6:
The number of additions being done depends on i and j. When i and j are far apart, there are more additions. Can you find a lot of i, j values that are far apart? How many? How far apart? (these answers should be functions of n) Can you describe most of these---Theta(this many)---in a very succinct way? How?
For problems 4 and 6, they say something like log n, can we assume that it is in base 2 or should we do base 10. In the solved exercise 1 than state log2(n)???
ReplyDeleteI don't believe this will affect the correct answer.
ReplyDeleteIt may help to remember (or learn) how to convert between logs in different bases. log_A (x) = log_B (x) * log_A (B) (To check this, raise A to the right-hand side, and simplify using laws of exponents and logs.)
For #2d, n log n = c, I used Matlab's lambertw() function. Is there an easier way to solve it?
ReplyDeleteThanks.
I did the brute force way picking different n's for some of #2, but that seems not very efficient but it worked.
ReplyDeleteAlso, I had a question on 6b...I am confused on how to "reduce" the program to C*f(n), it seems easy to prove the upper bound but getting the lower bound is :O.
For example,
i = 1: N+1
j = i+1:N+1
the upper bound would be
n*(n-1) = n^2 - n = O(n^2),
but how would I find the lower bound...any small hints would be much appreciative! :)
With the EHarmony Problem, the upper bound is that all man have to ask all women to get the final Stable matching which is n*n = n^2 and the lower bound is if the input mensPref has every man wanting a different woman such that every man asks exactly one woman therefore the lower bound is n*(1) == omega(n);
This means that it is not tight bounded by n or n^2 because the upper != lower...but I could be wrong on this as well!
If I go thru the loops at every step i, and add up the j interations that would that be the bare minimum or lower bound? It seems the j loop has a sequence of n-1 + ... 1 (had to review sequences been awaile) then that would be the lower bound because it would always do this many interations???
ReplyDeleteAgain, could be way out field on this one!
Yes, Krista, that was I was wondering last night. Here was my question to the Professor:
ReplyDeleteI think I am done with the rest of the homework, but I am stuck with
the b part of #2.6. I calculated the number of iterations of the inner
loop, but I am not sure how to calculate the number of addition
operations. Would you mind to give me a hint?
*****************************
Here is his answer to me:
You don't have to compute the exact number of addition operations,
just get approximate answers that are correct up to a constant factor.
I suggest you convert the pseudocode into actual (Java) code -- that
will make it much more clear how many addition operations are done
in the line of pseudocode talking about the "sum of entries".
By the way, Krista, you might want to recalculate your O(.). The upper bound would be all iterations of outer loop * all iterations of inner loop * summations of the array elements.
ReplyDeleteHey Lucia,
ReplyDeleteThanks for posting the response for everyone,
I was just doing an example of just the double loop because did not want to get too in depth so I pretended that I just had i and j loops and nothing else.
I was also thinking of doing an average of the additions but do I take the i = 1: n/2 or i = n/2+1 to n because when I use a small example of say n = 4 it seems that the additions are much higher for lower i's and go to zero at i = n, should I take the larger avg or the lower???
If I want to prove that it is lower bounded than I would expect to take the i = 1: n/2 because it will be closer to f(n) of part a.
This is a tough one (part b), huh!?!
I'd say you take the larger avg, because the algorithm does calculate everything and the lower avg will give you the lower number, which will be unrealistic.
ReplyDeletefor i = n-2 to n, you make 3 additions, which will run in O(1). Which is bogus, because you still have to calculate i = 1 to n and it will take more than O(1). Right?
ReplyDeleteWhen I answered Lucia's question before, I was confusing problems 2 and 4---sorry if this caused any confusion.
ReplyDeleteAdvice on problem 2d:
one answer---easy with a calculator---use binary search, with a "guess and check" approach. Start with values of n for which n*log(n) is too big, and too small, and then try their average as your next value. Keep going until you pin down the correct n within 1.
answer #2. Use math software. For free, on the internet, go to http://www.wolframalpha.com/
Type "solve(n log(2,n) = 100)" in the box, and hit enter. It will give you the answer, 22.32 (always make sure it has parsed your request properly in its "input interpretation")
Of course, 100 should be replaced with the appropriate number for the problem.
Matlab is another good choice, free on the CS machines, as are Maple and Mathematica, for instance, if you happen to own one.
Note that wolframalpha also shows you a graph of the function. Often, graphing the function is more helpful than just computing the answer.
Hope this helps!
Reminder: my office hours are at 2:00 today, Farris 149.
@Krista, a hint for finding the lower bound in problem 2.6:
ReplyDeleteThe number of additions being done depends on i and j.
When i and j are far apart, there are more additions.
Can you find a lot of i, j values that are far apart? How many?
How far apart? (these answers should be functions of n)
Can you describe most of these---Theta(this many)---in a very succinct way? How?
Matlab is free for UNM students. http://it.unm.edu/download/
ReplyDeleteI got it now, thank you to all that posted! :)
ReplyDeletefor i = 1 to n/2 have a lot more add operations therefore I will take the first half of averages as opposed to the bottom half which occurs n/2 times!
Is there anyone who looked into Problem 2.7 yet? There is some language/culture barrier for me. What is it talking about the Christmas song?
ReplyDeleteOllie, look here
ReplyDeletehttp://en.wikipedia.org/wiki/The_Twelve_Days_of_Christmas_%28song%29