1) Write a function which converts a string to a positive integer. Ignore the '+' and '-' characters, return 0 if the string is empty, and return any interpreted digits if a non-numerical character is encountered. Here was my solution:
int atoi (char * string)
{
if (*string=='\0') return 0;
int value = 0;
while (*string!='\0')
{
if (*string=='0') value+=0;
else if (*string=='1') value++;
else if (*string=='2') value+=2;
else if (*string=='3') value+=3;
else if (*string=='4') value+=4;
else if (*string=='5') value+=5;
else if (*string=='6') value+=6;
else if (*string=='7') value+=7;
else if (*string=='8') value+=8;
else if (*string=='9') value+=9;
else if (*string=='+') value/=10;
else if (*string=='-') value/=10;
else return value/10;
value*=10;
string++;
}
return value/=10;
}
2) Swap positions of the nibbles in a byte:
char nibbleSwap (char byte)
{
char nibble1 = byte&0xF0;
char nibble2 = byte&0x0F;
return ((nibble1/16)|(nibble2*16));
}
3) Write a function which computes x to the power of n using O(log n) multiplications.
int power (int base, int n)
{
if (n == 0) return 1;
if (n == 1) return base;
int half = n/2;
int value = power(base, half);
if (n%2==0) return (value*value);
else return (value*value*base);
}
This has a recurrence relation of T(n) = T(⌊n/2⌋) + Θ(1) for n>=2 and T(n) = Θ(1) for n<2. T(n) is ∈ Θ(log n).
4) Implement a function which draws a line, given coordinates for a start point, coordinates for an end point, and a two dimensional array representing grayscale pixels (8 bits per pixel). I didn't get around to attempting this question since I ran out of time.
