COMPUTER ORGANIZATION                     October 1, 2002

WC3824-001 (CSEE) HOMEWORK #3
PROF. TONY JEBARA

 

 

DUE

THURSDAY, OCTOBER 10th, 2002 AT BEGINNING OF CLASS

 

 

Please use the class newsgroup (bulletin board) for questions, updates, clarifications, and corrections related to the homework. It is linked off of the class home page: http://www.cs.columbia.edu/~jebara/3824. As a second resort, you can also email a TA directly: kdunn@cs.columbia.edu or am2104@columbia.edu.

 

 

1. (10 points): Patterson and Hennessy Exercise 4.10.

 

2. (15 points): Patterson and Hennessy Exercise 4.14.

 

3. (5 points): Patterson and Hennessy Exercise 4.21.

 

4. (15 points): Patterson and Hennessy Exercise 4.23.

 

5. (10 points): Patterson and Hennessy Exercise 4.31.

 

6. (20 points): Patterson and Hennessy Exercise 4.42.

 

7. (10 points): Patterson and Hennessy Exercise 4.51. Read p. 332 & 241-249 first.

 

8. (20 points): Patterson and Hennessy Exercise 4.52. Read p. 332 & 241-249 first.

 

9. (30 points): Patterson and Hennessy Exercise 4.53.

 

10. (50 points): Recursive Palindrome Detector (SPIM). In this problem, use SPIM to write a recursive MIPS function, palindrome-r. Pseudo-code for the function palindrome-r is as follows:

 

palindrome-r(str1,str2)

string str1,str2;

{

string res1;

boolean res2;

if (head(str2)==’NULL’) return(str1,TRUE);

else

{

(res1,res2) = palindrome-r(str1,tail(str2));

res2 = (res2 AND (head(res1)==head(str2)));

return(tail(res1),res2);

}

}

 

 

This function takes a null-terminated ASCII-encoded string, “str” and checks if the string is a palindrome, i.e. if the string reads the same backwards and forwards. Examples of palindromes include the strings: “x”, “madam”, and “wow”. Sentences can also be palindromes, for example “avid diva”. Spaces are treated just like any other character. Note that the empty string “” is also a palindrome. See Patterson and Hennessy pages 142-144 for background on strings and characters.

 

The function has the nice property that it checks if the string is a palindrome in-place: no additional buffers or arrays are needed. The function handles both odd-length and even-length strings correctly as well as the empty string.

 

There are a few important observations about this function. First, the function is called with two arguments: “str1” and “str2”. However, for your top-level call to palindrome-r (i.e. from main()) these two arguments are identical. For example, to check if string abcx is a palindrome, you would simply call:

palindrome-r(abcx,abcx);

 

Second, the pseudo-code includes the notation: tail and head. These are simply string operations, used to break up a string into parts. For example, if str=”abc”, then tail(“abc”)=”bc”. So tail is shorthand to indicate the remainder of the string, starting with the second character. Similarly, head(“abc”)=’a’. In other words, head indicates the first character in the string. Note that tail returns a string (which is being shown here in double-quotes) while head returns a single character (which we show written in single quotes). In other words, head does not give a null-terminated string, just a single byte to represent the one single character. Important: do not implement head and tail as separate functions. They are simply notations for basic string operations; translate them directly into the corresponding MIPS assembly instructions.

 

Third, note that the function has 2 return values, so you have to return these in registers $v0 and $v1 respectively. Thus the shorthand:

(res1,res2) = palindrome-r(str1,str2)

simply means that the function palindrome-r returns 2 values, the 1st return value is res1 and the 2nd return value is res2. Note that the 1st result is a string; the second result is TRUE or FALSE, indicating if the original string is an palindrome. You should encode TRUE by the integer 1 and FALSE by the integer 0 (i.e. as 32-bit words).

 

As in some of the HW#2 problems, assume that “str1” and “str2” are valid ASCII-encoded null-terminated strings and that they are given as pointers to the memory location at the start of each string. Write a MIPS assembly version of the palindrome-r function as a procedure. You should also write a main routine which calls palindrome-r. Your main routine should call it at least 4 times with different test cases by using the $a0-$a3 registers (it should work for any string, in principle). Be sure to use the caller-callee conventions as outlined previously and in class. Put comments in your program to make it easy to read and understand.

 

Use the SPIM simulator to test our your code and to make it output results on the console. Use syscalls as in the example code on the class web page and the SPIM documentation to output results on the console. SPIM is available and documentation can be downloaded from: http://www.cs.columbia.edu/~jebara/3824. Only hand in your assembly code for this question, either hand-written or as a print-out (do not print out the console or SPIM status windows).