CS 2734 Computer Organization II

If your SSN is even then write Hanoi below

else if your SSN is odd then write Comb below

• For those doing Hanoi (even SSN), here is that program in C:
  

         /* Tower of Hanoi problem: given n discs of decreasing size
          * on a peg numbered 1, show how to move them all to peg
          * number 2, using peg number 3.  The rules state that you
          * must not place a disc on a smaller disc, though you can
          * place a disc on an empty peg or on a larger disc.
          */
         #include <stdio.h>
  
         void hanoi(int n, int start, int finish, int extra);
  
         void main(void)
         {
            int n;
            scanf("%d", &n);
            hanoi(n, 1, 2, 3);
         }
  
         void hanoi(int n, int start, int finish, int extra)
         {
            if (n != 0) {
               hanoi(n-1, start, extra, finish);
               printf("Move disc %d from %d to %d.\n", n, start, finish);
               hanoi(n-1, extra, finish, start);
            }
         }
  

  Along with sample output:

         4
         Move disc 1 from 1 to 3.
         Move disc 2 from 1 to 2.
         Move disc 1 from 3 to 2.
         Move disc 3 from 1 to 3.
         Move disc 1 from 2 to 1.
         Move disc 2 from 2 to 3.
         Move disc 1 from 1 to 3.
         Move disc 4 from 1 to 2.
         Move disc 1 from 3 to 2.
         Move disc 2 from 3 to 1.
         Move disc 1 from 2 to 1.
         Move disc 3 from 3 to 2.
         Move disc 1 from 1 to 3.
         Move disc 2 from 1 to 2.
         Move disc 1 from 3 to 2.
  

• For those doing Comb (odd SSN), here is that program in C:
  

         /* Number of combinations of n things taken k at a time.
          * Use a recursive algorithm to calculate.
          */
         #include <stdio.h>
  
         void main()
         {  int N, K, C;
            printf("Enter values for N and K>>>");
            scanf("%d %d", &N, &K);
            C = Comb(N, K);
            printf("C = Comb(%d, %d) is %d\n", N, K, C);
            return;
         }
  
         int Comb(int N, int K)
         {
            printf("Call Comb with N and K =  %d %d\n", N, K);
            if (N == K || K == 0)
                return 1;
            else return Comb(N-1, K) + Comb(N-1, K-1);
         }
  

  Along with sample output:

         Enter values for N and K>>>5
         2
         Call Comb with N and K =  5 2
         Call Comb with N and K =  4 2
         Call Comb with N and K =  3 2
         Call Comb with N and K =  2 2
         Call Comb with N and K =  2 1
         Call Comb with N and K =  1 1
         Call Comb with N and K =  1 0
         Call Comb with N and K =  3 1
         Call Comb with N and K =  2 1
         Call Comb with N and K =  1 1
         Call Comb with N and K =  1 0
         Call Comb with N and K =  2 0
         Call Comb with N and K =  4 1
         Call Comb with N and K =  3 1
         Call Comb with N and K =  2 1
         Call Comb with N and K =  1 1
         Call Comb with N and K =  1 0
         Call Comb with N and K =  2 0
         Call Comb with N and K =  3 0
         C = Comb(5, 2) is 10
  

• In implementing each of these programs in MIPS, you must use $a0, $a1 (for Comb) and also $a2, $a3 (for Hanoi) as the input parameters, as well as $v0 for the returned value of Comb. Because these are recursive calls, you must save and store registers on the stack. In particular, after you have made a recursive call, if you have changed some $ai for the call, then you need to load it again from the stack if you want to use it again. One tricky part of Comb is to realize that you cannot use $v0 for both returned values, but only for the second one (in the case where you call Comb twice). The value returned from the first call must be saved somewhere else (where?).

• You can simply select and copy the C code for your program above, and then compile and run it to see what the output should look like.

For checkoff:

• You must demonstrate your program in action using an input provided at the time of checkoff.
• Hand the laboratory TA a copy of your source code when you start the check off procedure.