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.

## 2 comments:

Jason Harrison has pointed out that the following improvements can be made:

"

- the solution for atoi can be compressed by using the known ordering of digits in ASCII:

int digit;

if( *string >= '0' && *string <= '9')

{

digit = *string - '0'

value = value *10 + digit;

}

else

{

return value;

}

- the solution for swaping nibbles can be made faster by using left and right shift operators, event integer multiplications and divisions can be slower than shifts:

return (byte & 0xf0) >> 4 | (byte & 0xof) << 4

"

Thanks Jason!

nibbleswap can be faster by realising that in C++, right shift is implemented with logical right shift for unsigned types: hence, suffice to use

inline char nibbleSwap(unsigned char byte){

return byte>>4 | byte<<4;

}

Or in Java, we can use

return byte>>>4 | byte<<4.

Post a Comment