Professor Wrong? Program assignment?

[MercenaryFH]

Ok So I have been given a program assignment over the weekend,
http://www.cs.uky.edu/~jurek/cs315/cs315s08/pa/pa1.pdf
doesn't look too bad, just getting running times and such.

he gives us a formula
a(n) = a(n - 2) + a(n - 3))

hmmm sound almost like the fibonnaci number formula, which i happen to have a small program of.

#include <iostream>
using namespace std;
long fib(int n);



int main()

{
int n;
cin >> n;
while(n<20)
{
cout << fib(n);
cout << " ";
n++;
}


return 0;
}


long fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n-1)+fib(n-2);
}
}


now I checked wiki, and this DOES correctly output the first 20 numbers of the fibonnaci numbers.

so I figure hey ill just change the n-1 to n-2, and the n-2 to n-3....right?
should work, i mean their exactly the same.
BUT, when I do that i get WAY different numbers than what he's getting, when you look at the program assignment he's getting like 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22 in his sequence, and when i change it.....well thats not what i get AT all.
so my question is.......is he wrong, or is changing the n-1 to n-2, etc just not gonna be as simple as that.

cuz...the formulas look EXACTLY the same, besides the 2 numbers??

and he said it was recursive....and ^^ that is a recusive function correct?

EDIT: also im supposed to do a memoization....version of this, but Im not sure I understand how to do that, our professor never really....touched on memoization. i mean I understand the concept but..... i wouldnt know how to implement it?

thanks all!

[ovidiucucu]

[ Redirected thread ]

[Graham]

Well, that fib function is wrong (what answer do you get from fib(1)?). Note that the modified fib requires three initial givens, not two like the standard fib. Noting the three initial values that you have been given, I'm not surprised that you get a different answer if all you've done is replace the "-1" and "-2" by "-2" and "-3".

[pm_kirkham]

Your professor isn't wrong - 3, 0, 2, 3, 2, 5, 5, 7, 10, ...
3 + 0 = 3
0 + 2 = 2
2 + 3 = 5
3 + 2 = 5
2 + 5 = 7
5 + 5 = 10
You need to return the values of a(0), a(1), and a(2) as special cases, just like you have 0 and 1 as special cases in your fib function.

[MercenaryFH]

So.....wait, i'll just need to modify the special return case?

so would something like this work(it works for me at least)


long fib(int n)
{
if (n == 0)
{
return 3;
}
if(n==1)
{
return 0;
}
if(n==2)
{
return 2;
}

else
{
return fib(n-2)+fib(n-3);

}

}


sorry for indention, but u get the idea? dunno if thats the best way to do it tho.

neways i checked it and it worked.....but how would you memoization a function like that?
thats the next part of my assignment.....I read up on memoization (he never went over it in class)
and from what I can tell basically....like you memorize numbers that are already used....but how would I impelement that into this equation.
thx for the help so far guys, i was kinda being durpee dur on the special cases ahah

[pm_kirkham]

It's OK, I'd favour switch/case for more than a couple of values, but that's more a matter of taste than anything (until you get many values, it which case everyone uses switch). Also call it something other than fib(), since it's not Fibonacci, but another sequence (Perrin) .

Have you done dynamic arrays at all, such as the C++ stl vector, or have you done structures like maps? If not, use a fixed size array. Either will let you store a mapping of an integer to a long which you can use to store the memo.

[MercenaryFH]

I've done some arrays although it's been awhile(and i've never use vectors),
but so anyways for the memoization I could make some kind of array and store the value....but how would you check if the value is stored each time? and how would you call upon it.

this class is actually more of an algorithm class and only my second c++ class (our university isn't very good with it's CS classes)
sorry

also: for the memoization and Recusive function and then this:
iterative with a constant number of extra variables (four or five should
be enough)(dunno what that even means)

i need to set up some kind of "counter" to see how many times the function was used?
but.....how would you do that without changing the function?
or would you set up some kind of counter within the else statement?
that parts got my super confused

[angelorohit]

MercenaryFH, what you are attempting to do is hack at a piece of code that you already have. That's not a very wise thing to do. You should not try to force the problem so that it fits the bill. You need an elegant way to solve the problem. Yes, I agree that the problem that your professor has given you appears similar to a fibonacci series. However, if you truly understand recursive functionality then you certainly must attempt writing this program from scratch without any bias.

[MercenaryFH]

I see what you mean, but he specifically states to use that function, then do it recusivly and then with memoization.

i have no problem with the recursive as it works, I just dont see how you would implement a counter

long fib(int n)
{
static int counter;
cout << counter << " ";
counter ++;

if (n == 0)
{
return 3;
}
if(n==1)
{
return 0;
}
if(n==2) {
return 2;
}


else
{

return fib(n-2)+fib(n-3);
}

}


in my mind that should work, since each time the function is called the counter will go up 1? but then again i could be way off. I mean the counter is going up, but to compute a number like 9 it's saying 13 times......and I dunno how right that is lol?
of course this is without memoization so....i suppose that could be right

[pm_kirkham]

Maybe look at the example code for memoization for the fib function your prof gives at http://www.cs.uky.edu/~jurek/cs315/cs315s08/pa/pa1-utilities.sphp ?

[MercenaryFH]

well i guess actually now that i read it he wants to see how many times the function is added

here is his ""
"count (number) of + operations (used to
compute a(n) and not operations to control loops or to increase counters)"

so....that'd be how many times the function was added.....im assuming?

not sure I get his wording

[angelorohit]

From what I can understand, you have already done the recursive method. The memorization method is the one that uses std::vector and the iterative method is the way you would do it with a simple loop. Now for this:
For each value of n, tabulate the count (number) of + operations (used to compute a(n) and not operations to control loops or to increase counters)...For the recursive method, this should be:


unsigned long int calls=0;
unsigned long int noOfAdditions = 0;

unsigned long int Series(size_t n)
{
calls++;
switch(n)
{
case 0: return 3;
case 1: return 0;
case 2: return 2;
}

noOfAdditions++;
return Series( n-2 ) + Series( n-3 );
}

[MercenaryFH]

yea the switch function looks nicer,

i got this for memo function


int memfib(int n)
{

int memo[500]={0};

if (n == 0)
return 3;
if (n == 1)
return 0;
if (n == 2)
return 2;
if (memo[n] != 0)
return memo[n];
memo[n] = memfib(n-2) + memfib(n-3);
return memo[n];
}


it's giving me the same values as the recursive function so im assuming it works right?

i've tried the iterative one, by looking at iterative fib solutions, but I havn't got a clue as to how you would do that......i understand it's a loop sort of thing.....but, I dont see how it really works tho?

here's what i had with it....but it's not working but I didn't know if maybe I had the right idea or not?


{
unsigned f, f1, f2;

if (n==0)
f = 3;
else if (n==1)
f = 0;
else {
f2 = 2;
f1 = 0;
for(unsigned i=1; i< n; i++) {
f = f1 + f2;
f2 = f1;
f1 = f;
}
}
return f;
}

[angelorohit]

Memorization method:-

unsigned long int Series(size_t n)
{
static std::vector<unsigned int> seriesStore;
calls++;
switch(n)
{
case 0: return 3;
case 1: return 0;
case 2: return 2;
}

if(seriesStore.size() < n + 1)
seriesStore.resize(n + 1);

if(seriesStore[n] <= 0)
{
noOfAdditions++;
seriesStore[n] = Series( n-2 ) + Series( n-3 );
}

return seriesStore[n];
}
Use an std::vector for "remembering" computed sequence numbers, not a simple array. The problem with the array is that you need to know its maximum size beforehand. With an STL vector, you can resize it as and when needed.

Iterative method:-

unsigned long int Series(size_t n)
{
calls++;

int first = 3, second = 0, third = 2, next;

switch(n)
{
case 0: return 3;
case 1: return 0;
case 2: return 2;
}

for(int i = 3; i <= n; i++)
{
noOfAdditions++;

next = second + first;
first = second;
second = third;
third = next;
}

return third;
}

[MercenaryFH]

im guessing the noadditions is ur counter? amirite?
where would u define noof additions, just in teh function somewhere at the top I assume?

thx man

edit: hmmm this is weird, I tried using that code, just declared the noadditions and calls within the function but it gives me warnings that their "unitialized local variables?"

[angelorohit]

Yes, noOfAdditions is a counter for counting the number of additions that were made solely for the purpose of calculating f(n). You can see where noOfAdditions is declared in Post #12.

[MercenaryFH]

Hmmm i see, Well lets say i wanted to call noOfAdditions. Like to see what the number is, since it's within the function and it's not returning. is there some way to 'easily' display the counter?(since each function has the same counter variable of "noofadditions"

and thx for all your help man
btw whats the the "unsigned" usage......we've never gone over that in class.....does that just mean it doesn't need a prototype or something?

[angelorohit]

noOfAdditions is a global variable. So, it can be accessed from any function, including main(). An "unsigned" variable means that the variable cannot hold a negative (no sign allowed) value. There cannot be a negative number of additions... so it makes sense to declare the variable as an unsigned integer. The keyword unsigned has its roots in C. Read this (http://www.cplusplus.com/doc/tutorial/variables.html) for more info.

[Lindley]

Personally, I think of memoization as a simple addition to a recursive program which should be used only when it isn't convenient to refactor to a dynamic programming approach.

The reason for doing either memoization or dynamic programming is to keep computation time from blowing up exponentially due to a large number of repeated calculations. Once you understand that the reason you store computation results is so that if you ever get precisely the same inputs you'll have the output immediately, the concept should become clear.

[MercenaryFH]

true, but i have to do all three for the assignment.

last questions guys i swear: for the assignment I have to measure like the "time" it took to do each of these equations. is there like a good time /stopwatch program to implement in these functions, to see how long it took to run each.
he has a stopwatch program on his unix server we can use, but I figured if I could find something within c++ or something easier I could use that, i also tried to use his "stopwatch" code, but it says it cant find <sys/times> nor the other include either

EDIT: nm i used a class stopwatch thing looks like this


#include <ctime>
class stopwatch
{
public:
stopwatch() : start(std::clock()){} //start counting time
~stopwatch();
private:
std::clock_t start;
};


#include <iostream>
using namespace std;
stopwatch::~stopwatch()
{
clock_t total = clock()-start; //get elapsed time
cout<<"total of ticks for this activity: "<<total<<endl;
cout<<"in seconds: "<<double(total)/CLOCKS_PER_SEC<<endl;
}

that should work ok for my code I guess?

the times will be slightly different each time im assuming?

[pm_kirkham]

You are supplied the stopwatch class in the course materials I posted a link to earlier.

[MercenaryFH]

ya I ended up using the clock program above ^^ because for some reason my computer wouldn't load sys/times.

it ended up working out in the end tho.
thx guys!