Assignment 3 Dynamic Memory Allocation and Linked Lists

COMP 273
Assignment 3

1 Dynamic Memory Allocation and Linked Lists
For this question, your job is to implement a SINGLY Linked list. This linked list will be built by
taking SINGLE CHARACTER inputs from the user, one input at a time, and placing the input in
respective nodes. Every node will have a character specified by user input AND an address. The
address will be pointing toward the next node in the linked list. You will then develop a procedure
to print the linked list you have made, along with a procedure to reverse said linked list. Use
whichever subroutines you like. Follow convention.
(a) Write a procedure called "build" that will continually ask the user for another input UNTIL
the user has input the character "*". "*" Will act as the token that signifies that the list
is complete. The final "*" will not be considered a part of the linked list. For EACH user
input until "*", you will put that character into a single node in the linked list. $v1 will be
used to return the address of the first node in the linked list.
(b) Write a procedure called "print" which will use $a0 to take the address of the first node of
a linked list. "print" will print the contents of each node as it goes through the linked list.
(c) Write a procedure called "reverse" which will reverse a singly linked list. Reverse will take
the first node of a linked list as an argument. Pass the address of the first node of a linked list
through $a1. Reverse will then reverse every element in the linked list. Return the reversed
linked list in $v1. Use whichever subroutines you like. Follow convention.
2 Dr. Ackermann or: How I Learned to Stop Worrying and
Love Recursion
There was some confusion on the last assignment about what recursion really entailed. In particular, because Dijstrka’s algorithm was “tail-recursive,” one could implement it using a single
stack frame using a loop, without the need to make a recursive call at all. Functions that can be
computed in such a way are called “primitive recursive.”
One may ask if all computable functions are primitive recursive. In 1928, German mathematician William Ackermann answered the question in the negative by providing an example of a
recursive function which was not primitive recursive (actually, David Hilbert provided the example,
but Ackermann formally proved the result). In a sense, the recursion cannot be "taken out" of the
computation of the function. In particular, the function cannot be computed using a loop whose
bound is known at runtime, so that we cannot get away with using a single stack frame.
1
The Ackermann function A(m, n) for natural numbers m, n is defined by
A(m, n) =
8
<
:
n + 1 if m = 0
A(m  1, 1) if m 0 and n = 0
A(m  1, A(m, n  1)) if m 0 and n 0.
(1)
Your task is to write a MIPS program that computes the Ackermann function. It should take
input from the console and print the answer. You should write a helper procedure that checks the
type and range of the inputs, printing an appropriate error message if necessary. You should use
the table of values found at https://en.wikipedia.org/wiki/Ackermann_function#Table_of_
values to test your program. Be careful: A(m, n) grows very rapidly. Thus, you should limit your
tests to values of m < 4 and n < 5.
The history of Ackermann’s discovery is a fascinating read. If you are fascinated by the relevant concepts, you should consider taking COMP 330 (Theory of Computation) and COMP 302
(Programming Languages and Paradigms) to learn more.
3 Numerical Integration with the Floating Point Coprocessor
MIPS has two coprocessors dedicated to floating-point arithmetic. We will make use of them by
implementing a numerical method for integration.
Recall (or learn) that the integral R b
a f(x) dx of a real-valued function f(x) of one real-variable
gives the signed area under the graph of f over the interval [a, b]. Most integrals do not have closedform expressions as solutions and one must resort to numerical methods for their computation.
To this end, let us partition the interval [a, b] into N subintervals [x0, x1],..., [xN1, xN ] with
xi = a + i ⇤ x, where x = (b  a)/N, and let x⇤
i be the midpoint of the ith interval. Then the
“midpoint method” approximates the integral according to the formula
Z b
a
f(x) dx ⇡ X
N
i=1
f(x⇤
i )x (2)
with the approximation becoming exact as N ! 1.
Your task is to write a procedure that computes the definite integral of a real-valued function
of one variable using the midpoint method. Your procedure should accept as input the address of
the function to be integrated and the endpoints of the interval of integration (specified in the data
section). The value of N should be hard-coded into the body of your method. You should have a
helper procedure that checks that a<b, printing an appropriate error message if necessary. Since
a, b and the result of integration will be floating point values, you will need to use the appropriate
registers of the floating point coprocessor to manipulate them. Refer to the assignment template
for additional details.
4 Assignment Submission Instructions
1. Submit your solution to MyCourses before the due date.
2. Highlight the Three template files, and zip them. The zipped file will be named <studentID.zip. If my student ID is 123456789, then the zip file to submit will be named
"123456789.zip".
3. If you have special comments about your code in any questions, feel free to include a "confessions.txt" file in your zip containing your specific comments. Otherwise, simply comment
your code as you normally would.
4. Your code must run and assemble, even if the final solution is not quite working. Part marks
will be awarded for correct high-level control flow and use of conventions. If something is
not working, comment-out the broken parts of code and write a comment or two about what
you expect to happen, what is happening, and what the problem may be. If your code does
not assemble you will receive very few points
2