1. (20 points) Write an assembly program that implements the function below to compute n choose k, which is sometimes written as either n k or C n k . This is the number of different ways to pick a subset of size k from n things. I suggest that you take the main function that I gave you in fib.asm from lab and adapt it to call this function.

int choose(int n, int k) { if(n < k) return 0; if((n == 0) || (k == 0)) return 1; int val1 = choose(n-1, k-1); int val2 = choose(n-1, k); return val1 + val2; }

main function in lab

.text addi $v0, $zero, 5 #read integer syscall

add $a0, $v0, $zero #call fib function jal fib

add $a0, $v0, $zero #print result addi $v0, $zero, 1 syscall

addi $a0, $zero, 10 #print newline addi $v0, $zero, 11 syscall

addi $v0, $zero, 10 #exit program syscall