I am trying to work through some problems I found from Stanfords "Design & Analysis of Algorithms" course from 2013. In particular, problem 3 from problem set 1 here.
In summary it states:
The problem requests you design an algorithm that uses Θ(n)W total power.
Being a 5pt question from problem set 1, I presume this is easier than I am finding it.
...what is this algorithm?....or how can I change my thinking to find one?
The question states that the strategy "just increase power by 1 watt each time" will result in an Θ(n^2)W total power. Indeed, this is true, as the total power used by any n is n * (n+1) / 2.
However, I can't think of any strategy that isn't:
Also, if I ignore the discreteness of the radio for a minute and analyse the problem as a continuous linear function, the total power should be generalisable to a function g(n) of the form g(n) = Kn + B (where K and B are constants). This linear function would represent the integral of the function we need to use for controlling the radio.
Then, if I take the derivative of this function, dg(n)/dn, I'm left with K. I.e. If I want to have linear total power, I should just drive the radio at a constant power for n times...but this would only result in a rescue if I happened to guess K correctly the first time.
Yes, I had already thought of doubling etc....but the answers here pointed out the error in my thinking. I had been trying to solve the question "design an algorithm that has linear cumulative power consumption"...which I think is impossible. As pointed out by the answers, I should have thought about it as "for a given n, design an algorithm that will consume Kn"...i.e. what the question posed.
I've read the assignment...
It states that the radio is capable of transmitting in integers, but it doesn't mean you should try it one by one and go over all the integers until n.
Well, I could give you the answer but I'll try just to lead you to think about it on your own:
Please notice that you need to transmit a signal equal or greater than n, so there is no way you are "going to far". Now, with the concepts of complexity, if you go over all the signals you'll get a series of (1+2+3+...+n) which equals to Θ(n^2), try to think of a pattern which you can skip some of those and getting a series that results a sum of Θ(n).
This task is similar to searching algorithms which naively goes for Θ(n^2), but there are algorithms reduced to less than that - you should go and explore how they work :)
If you want an approach for an answer:
You can start with 1W and each step double it for the next transmit. That way you will do
log(n)attempts, and each attempt costsiwhichiis the power of that attempt. So the cumulative power will be something like that:(1+2+4+8+16+...+n)which equals to2n-1and fits the requirement ofΘ(n)