In this assignment you are to modify and extend the MIPS assembly program you wrote in assignment 3 as follows:

• Add the command: Find x - returns y where y is the number of elements in the list that are less than or equal to x. Note that if x is in the list then the element in position y in the list is equal to x but if x is not in the list then y+1 is the position that x belongs in the sorted list. If you did not do the bonus then you can assume that x is between 0 and 9, and the command Find x is encoded by just x. This command must be implemented using recursive binary search the pseudocode for which appears below.


• Modify your code so that each of the commands results in calling a separate procedure devoted to implementing the command and uses the jump and link command, saving any registers if necessary, passing parameters using the appropriate registers, etc. Note: you may want to introduce other procedures to make the code easier to read such as a procedure that shifts all of the elements of the list up one position and/or down one position from some index on.


• Modify your code so that the procedures for Insert and Delete call Find in order to find the position of x in the list.
  

An example a log of a session with your new program might look like:

Command: 11
Command: 13
Command: 11
Command: 3
3
Command: 2
2
Command: 1
2
Command: 50
Good-bye!

To be handed in: (1) A complete listing of your fully documented code. Almost every line of code should have a comment. (2) The log of one session which fully tests your code. Make sure your session tests all features of your program. (3) Email me your dot s file.

Here is the pseudocode for recursive binary search:

Find(x)
/* n = size of list
 
 if n = 0 return 0 else return BinSearch(x,1,n)

BinSearch(x,a,b)
/* Search for x in sorted list between index a and b
/* list(i) is the element of index i in the list 
/* ceiling(y) is the least integer greater or equal to y

 if b=a and list(a) <= x return a else return a-1
 c = ceiling((a+b)/2)
 if list(c) <= x return BinSearch(x,c,b) else return BinSearch(x,a,c-1)
  

Report problems to dkrizanc at wesleyan dot edu