attn computer science students

M

Mortez

Banned
Having probs with this assignment...
Code: 
MODULE exp(n) RETURNS 2^n
    IF n = 0 THEN
         RETURN 1
    ELSE
         RETURN 2 * exp(n-1)
    ENDIF
ENDMODULE

Prove using induction exp(n) is determitive, n >= 0.
Incase my vocabulary fails: Prove that module exp(n) stops(is right) with all n >= 0.

This is what I've got so far:

(i) exp(0) = 1
(ii) Assume exp(k) = true , k >= 0

exp(k+1) = true, k >= 0

Prove: If parameter n = 0 module returns 1, part (i), ending recursive calls. If n > 0 module calls itself recursively with parameter n-1. In recursive loop Lim n-1 = 0 so with every n >= 0 module exp(n) will stop.

(iii) exp(n) is true, n >= 0.


How ever I'm not very happy with the prove part. Can it be done more elegantly?
 
But computers are the wave of the future! Thats where all the high paying jobs are! The radio told me so!
 
there's mixed reviews on the future of comp jobs.
maybe 50% of the predictions say they're gonna come back, soon, bigtime.
however, most current trends are still slashing, cutting, continuing the exporting.
there's a great article on it in the recent ACM mailing for you comp ppl.
 
Its mathmatical induction on n, so:
Basis: n=0. exp(0)=1 2^0=1 Therefore, exp(0) is correct.
Induction: Assume the inductive hypothesis: exp(n) is correct.
exp(n+1)=2*exp(n). From the inductive hypothesis exp(n)=2^n. Then, exp(n+1)=2*2^n=2^(n+1).
 
thats not even really CS

using induction?

exp(3) = 2 * (exp(3 - 1))
exp(3 - 1) = exp(2) = 2 * (exp(2 - 1))
exp(2 - 1) = exp(1) = 2 * (exp (1 - 1))
exp(1 - 1) = exp(0) = 1

so

exp(3) = 2 * (2 * (2 * (1))) = 8

or something like that
 
Wow, I see a lot of people who can't help with the problem pitching shit.

My thoughts: This sort of thing varies from class to class. In the undergrad classes I've taken, we did very rigorous proofs. Yours is not what I would call rigorous or formal, which is why you are uncomfortable with it. As you advance in CS, the proofs may not be so rigorous, but they will be plenty hard.

With no experience with your class/instructor, I would write it like this:

Basis: Let k = 0. exp(0) = 1, so the hypothesis is true for the basis. (exp(0) is determitive).

Induction: Assume that the hypothesis is true for some k >= 0.
Then for k+1, exp will return: 2 * exp(n-1), which is 2 * exp(k).
Since exp(k) is determitive(?) by the inductive assumption, then exp(k+1) is also determitive.

However, the form of any such proof is dependent on the requirements of the instructor. Be as formal as you need to be.
 
I was offered a paid internship to a big defense company here in San Diego but i would have to major in computer science. I may do it next semester though since they pay well and ill have a job
 
TonyElTigre said:
I was offered a paid internship to a big defense company here in San Diego but i would have to major in computer science. I may do it next semester though since they pay well and ill have a job
Click to expand...

Yeah, I don't know why everyone's so down on CS - I made good money at a research internship this summer.

The effect should be to weed out lazy dumbasses who couldn't excel in the first place, but it seems like those people aren't deterred.

If you get a graduate degree (terminal Master's or PhD.) you should be able to find a job. I'm sure there are some with that education who don't, but everyone I know with a graduate degree is well employed. Of course, my friends are all smart ;).
 
yeah if anything this internship would be a good 5 years (i have to stay 1 year after i graduate so they will pay for school) of quality experience in the field and hopefully i could just stay on longer with them
 
US might be a different story, but in here uni is having a hard time keeping the students in because many are torn to joblife before they get through.
 
You must log in or register to reply here.
Back
Top