MIPS Recursive Programming, Help please!

[gomickle]

I have been working on this assignment for couple weks (aling with my other classwork) and I couldn't get it anywhere, can any one help me doing it. Or can you at least tell me hints and tips toward resolving the program: the question is:

The element selection problem is defined here as follows. Given a sequence S = {s1, s2, s3, ..., sn} of integers and an integer k, where 1 ≤ k ≤ n, find the k-th smallest integer in S. The outline of a recursive algorithm that can solve the selection problem follows (adapted from: S. Akl, The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989). The parameter Q in procedure SELECT is a small integer constant.procedure SELECT(S,k)

if | S | < Q  then sort S          and return the k-th elementelse subdivide S into | S |          / Q subsequences of Q elements eachend if.
Sort each subsequence and determine its median.
Call SELECT recursively to find m,          the median of the | S | / Q  medians found in 2.
Create three subsequences S1, S2,          and S3 to contain elements of S          smaller than, equal to, and larger than m, respectively.
if  | S1| ≥ k              then call SELECT recursively to find the              k-th element of S1else if  | S1| + | S2| ≥              k   then return melse call SELECT recursively to              find the (k - | S1| - | S2|)-th              element of S3end if
end if.

The running time of SELECT is O(n) for any value of Q ≥ 5 (under this condition, recursive calls are carried out for sequences ever-decreasing in size).
Notice the similarities between SELECT and the popular QUICKSORT algorithm. The latter algorithm is for sorting, and has worst case and expected running times O(n2) and O(n lgn), respectively.

I used bubble sort in my code. and my code is the following:* I Also Uploaded the code in a text file *
CODE

.data
se:    .word    14,23,17
.text
sa:    .space    50
sb:    .space    50
sc:    .space    50
.globl main


main:
la     $a0, se                #a0 refers to se


addi    $s0, $zero,5            #Q
addi    $s1, $zero,2            #K
add    $s2, $zero,$zero            #set s2 to zero


#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    count


ct:    lw    $a1, 0($a0)            #store the first word from a0 to a1
add    $s2, $s2, 1            #add one to s5 (this is the counter)
addi    $a0, $a0, 4            #go to the next word (shift index by 4bytes)
bne    $a1, $zero, ct            #if a1 is not at the end, go back to ct (count)
la    $a0, se                #make a0 refers back to beginning of se


#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    compare and branch


bgt    $s0,$s2,bbss            #if Q > |S| then bubble sort and give K
j    subs                #otherwise, go to subs
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    finish the program
li     $v0,10                           # exit
syscall


#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    bubble sort
bbss:    addi    $sp,$sp,-4            #adjust this MF for one element
sw    $ra,0($sp)
bbs:    addi     $t0,$s2,0
addi     $t0,$t0,-1                         #$t0 = na - 1
la     $t1,se                                # pointer pa, $t1 = address of a
li     $t2,0                                # exchange flag, $t2 = 0


loop:
beq     $t0,$zero,done
lw     $t6,0($t1)                           # $t6 = *(pa)
lw     $t7,4($t1)                           # $t7 = *(pa+1)
slt     $t3,$t6,$t7                         # if ($t6 < $t7)
beq     $t3,$zero,next                      #   goto next
sw     $t6,4($t1)                           #
sw     $t7,0($t1)                           # *pa <-> *(pa+1)
li     $t2,1                                # set exchange flag
next:   addi     $t1,$t1,4                      # pa++
addi     $t0,$t0,-1                         # $t0 = $t0 -1
j     loop
done:
bne     $t2,$zero,fin                      # if (exchange) goto main


fin:    la    $a0,se
sll    $s1,$s1,2
add    $s1,$a0,$s1
lw    $s3,0($s1)
lw    $ra,0($sp)
addi    $sp,$sp,4
jr    $ra
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    subs
#                    make em
addi    $t0,$s0,0                    #copy Q to t0
addi    $t1,$s2,0                    #copy counter to t1


div    $t1,$t0                    #to find how many time we have to split
sll    $t2,$t0,2                    #t2 now contains a shift amount = size of elements


la    $t3,se                    #address of se into a0


again:    addi    $sp,$sp,-4                #adjust this pointer for 1 element
sw    $t3,0($Sp)                #store one element on it
add    $t3,$t3,$t2                #add size of Q elements
subi    $t1,$t1,1                    #we did that once, so we subtract
bne    $t1,$zero,again
addi    $sp,$sp,-4                #adjust this pointer for 1 element
sw    $t3,0($Sp)                #store one bitch on it


#                    sort em
sort:    addi    $t0,$s0,0                    #copy Q to t0
addi     $t0,$t0,-1                         #$t0 = na - 1
lw    $t1,0($sp)                    #load the address of first section
addi    $sp,$sp,4                #so we go to next section at next time
li     $t2,0                                    # exchange flag, $t2 = 0
lop:
beq     $t0,$zero,pull
lw     $t6,0($t1)                               # $t6 = *(pa)
lw     $t7,4($t1)                               # $t7 = *(pa+1)
slt     $t3,$t6,$t7                             # if ($t6 < $t7)
beq     $t3,$zero,next                          #   goto next
sw     $t6,4($t1)                               #
sw     $t7,0($t1)                               # *pa <-> *(pa+1)
li     $t2,1                                    # set exchange flag
next:   addi     $t1,$t1,4                          # pa++
addi     $t0,$t0,-1                             # $t0 = $t0 -1
j     lop



#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#                    Pull K
pull:

• I Also Uploaded the code in a text file *

I would appreciate it
regards

[MacGyver Orca]

I would like to help you, but I don't know if I can for two reasons: I am no good at recursion, and I'm not entirely sure what your problem is asking. So I have two questions for you before I can determine if I can help. Do you have to use recursion, and if so, do you have to use the method you described in your post? Are you searching through an array, or are you trying to find the smallest integer in an integer?

[gomickle]

Alright, the question is asking to subdevide an array of integers into a smaller ones; each sub array size is equal to a number (Q). Hence, if the original array size is less than Q, we don't need to subdevide it. Otherwise, we should devide the array into smaller ones as i said whith eatch has Q elements in it.

after that, we will sort each array and determine its median.
if you can do this part for me (devide, sort ten get each median), that would be great! don't worry about recursion cause i don't have to do it with recursion.

[MacGyver Orca]

after that, we will sort each array and determine its median.
if you can do this part for me (devide, sort ten get each median), that would be great! don't worry about recursion cause i don't have to do it with recursion.

If you don't have to do it with recursion, why do we need to divide the array into smaller arrays? Aside from that, lets say you have knowledge of all the array sizes, and that they are all the same size, then you would use the following code fragment to figure out the median, assuming also it is an array of words:

add   $t4, $zero, $zero 
addi  $s0, $s0, 2    # will be useful later 
la      $t0, size       # size of the array, I just called it size 
lw     $t1, 0($t0)    # get the size 
div    $t1, $s0       # divide the size by 2 
mfhi  $t2              # puts the remainder from the previous divide in $t2 
mflo  $t3              # puts the quotient in $t3  
la   $t5, numbers  # numbers is the name of your array 
loopStart: 
slt $t6, $t4, $t3 
beq $t6, $zero, loopDone 
addi $t5, $t5, 4 
j loopStart 
loopDone: 
lw $t7, 0($t5)  
# Print the median size 
add $a0, $t7, $zero   
li  $v0, 1 
syscall

That should work to find the median of an odd array, not an even one, that will require a check of the mfhi instruction and then doing additional calculations to figure out where you need to go in the array, if you really need that part explained you'll have to wait till tomorrow, also, the above code might be off by one, but it should be right. if you need anymore explanation just ask

[assembler]

Hi ,
Your code for finding out the median was really helpful. I am trying to figure out how to use the same code for a list of integers, even or odd does not matter. Also I am trying to set up a bootloader program in MIPS. I have three option that should show on the MENU whe I start the program -
Division
Mean
Median

I have got division and mean to work and I am working on Median. But can you help me out with how to write the bootloader program. Please let me now if you need any clarifications. You r help will be gratly appreciated

If you don't have to do it with recursion, why do we need to divide the array into smaller arrays? Aside from that, lets say you have knowledge of all the array sizes, and that they are all the same size, then you would use the following code fragment to figure out the median, assuming also it is an array of words:

add   $t4, $zero, $zero 
addi  $s0, $s0, 2    # will be useful later 
la      $t0, size       # size of the array, I just called it size 
lw     $t1, 0($t0)    # get the size 
div    $t1, $s0       # divide the size by 2 
mfhi  $t2              # puts the remainder from the previous divide in $t2 
mflo  $t3              # puts the quotient in $t3  
la   $t5, numbers  # numbers is the name of your array 
loopStart: 
slt $t6, $t4, $t3 
beq $t6, $zero, loopDone 
addi $t5, $t5, 4 
j loopStart 
loopDone: 
lw $t7, 0($t5)  
# Print the median size 
add $a0, $t7, $zero   
li  $v0, 1 
syscall

That should work to find the median of an odd array, not an even one, that will require a check of the mfhi instruction and then doing additional calculations to figure out where you need to go in the array, if you really need that part explained you'll have to wait till tomorrow, also, the above code might be off by one, but it should be right. if you need anymore explanation just ask

[MacGyver Orca]

Hi ,
Your code for finding out the median was really helpful. I am trying to figure out how to use the same code for a list of integers, even or odd does not matter. Also I am trying to set up a bootloader program in MIPS. I have three option that should show on the MENU whe I start the program -
Division
Mean
Median

I have got division and mean to work and I am working on Median. But can you help me out with how to write the bootloader program. Please let me now if you need any clarifications. You r help will be gratly appreciated

Unfortunately I can't help you, we never had to write a bootloader in our class so I have no experience with it, my book doesn't even make any mention of it. Sorry.