MIPS Recursive Programming, Help please!
 

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)

1. if | S | < Q then sort S and return the k-th element
   else subdivide S into | S | / Q subsequences of Q elements each
   end if.
2. Sort each subsequence and determine its median.
3. Call SELECT recursively to find m, the median of the | S | / Q medians found in 2.
4. Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.
   1. if | S1| ≥ k then call SELECT recursively to find the k-th element of S1
      else if | S1| + | S2| ≥ k then return m
      else call SELECT recursively to find the (k - | S1| - | S2|)-th element of S3
      end 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
#/////////////////////////#hopefully this shit will work!!!!!!!!!


.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:





/CODE

* I Also Uploaded the code in a text file *

I would appreciate it
regards

Re: MIPS Recursive Programming, Help please!
 

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?

Re: MIPS Recursive Programming, Help please!
 

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.

Re: MIPS Recursive Programming, Help please!
 

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

Re: MIPS Recursive Programming, Help please!
 

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

Re: MIPS Recursive Programming, Help please!
 

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.