CS 1MD3 T2 2003
Assignments

Some assignments will be handed in using WebCT. Your MUSS userid is your userid for WebCT as well, and your password is initially set to be your student ID. Please change it!

1. Brookshear, Chapter 4, Review Problems (at the end of the chapter) #11 and #28. Due: Thu Jan 23th, 2003, 10:30am, using WebCT.
2. A Book on C, Chapter 4, Exercise #17. Due: Mon Feb 3, 2003, 10:30am, using WebCT.
3. Recursion. Due: Tue Feb 25, 2003, 10:30am, using WebCT.
4. Hashing. Due: Wed Mar 12, 2003, midnight, using WebCT.
5. Finite State Machines. Due: Mon Apr 7, 2003, 10:30am, using WebCT.

Bonus Assignments

• Bonus1. Due: Mon Jan 20th, 2003, before class [by email].
• Bonus2. Due: Thu Feb 6th, 2003, before class [by email].
• Bonus4. Due: Tue Apr 8th, 2003, midnight [by email].

Selected solutions

#3

Dot product

Something like this works

double dot_product(double *v1, int l1, double *v2, int l2) {
    if ( (l1==0) || (l2==0) )
        return 0;
    else
        return (*v1)*(*v2) + dot_product(v1+1, l1-1, v2+1, l2-1);
}

I rather like

double dot_product(double *v1, int l1, double *v2, int l2) {
    return ( (l1==0) || (l2==0) ) ? 0 :
        (*v1)*(*v2) + dot_product(v1+1, l1-1, v2+1, l2-1);
}

Binary powering

A good solution would be

double binary_power(double x, int p) {
    if (p<0)
        return 1/binary_power(x,-p);
    else if (p==0)
        return 1;
    else if (p==1)
        return x;
    else { int c;
        c = binary_power(x, p>>1);
        return c*c*( p%2 == 0 ? 1 : x) ;
    }
}

All those special cases *have* to be there to stop the recursion !!!

The above solution can be expanded into simpler components

double binary_power(double x, int p) {
    if (p<0)
        return 1/binary_power(x,-p);
    else if (p==0)
        return 1;
    else if (p==1)
        return x;
    else { int c,p_div_2,sqr;
        p_div_2 = p >> 1;
        c = binary_power(x, p_div_2);
        sqr = c*c;
        if (p%2 == 0) /* p even */
            return sqr;
        else  /* p odd */
            return sqr*x;
    }
}