ECS 50: Program #3
Prof. Joël Porquet
UC Davis, Fall Quarter 2019
•1 Changelog
•2 General information
•3 Program
•4 Submission
•5 Academic integrity
1 Changelog
Note that the specifications for this project are subject to change at anytime for additional clarification. Make sure to always refer to the latest version.
•v2: Fixed couple of typos
•v1: First publication
2 General information
•Due before 11:59 PM, Tuesday, November 26, 2019
•You are to work alone for this programming assignment
•The reference work environment is the CSIF, and the MIPS simulator spim
2.1 Objectives of the assignment
The objectives of this programming assignment are:
•Writing a complex high-quality assembly program.
•Using functions with arguments, and return values.
•Programming a recursive function.
•Implementing two popular algorithms, for sorting and searching.
2.2 Assessment
Your grade for this assignment will be broken down in several scores:
•Auto-grading: ~75% of grade
Running an auto-grading script that tests your program and checks the output against various inputs
•Manual review: ~25% of grade
The manual review is itself broken down into different rubrics:
◦Quality of implementation: ~20%
◦Coding style: ~5%
3 Program
3.1 Sorting and searching
3.1.1 Introduction
Two of the most important algorithms, used in almost all significant programs, are sorting, that is organizing a collection of data items in a defined order, and searching, that is finding a certain data item in a collection.
3.1.1.1 Sorting
There exist plenty of sorting algorithm (including some with very intriguing names, such as “cocktail shaker sort”!) but one of the simplest, and yet quite efficient for small collections, is the insertion sort.
Below is the pseudo-code corresponding to the insertion sort algorithm on an array A.
i := 1
while i < length(A)j := iwhile j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j := j – 1
end while
i := i + 1
end while
3.1.1.2 Searching
The most naive searching algorithm consists in looking at all the data items in the collection to find the requested one. However, if the collection is already sorted, then a binary search can leverage this characteristic by recursively dividing the search interval in half until it finds the requested item.
Below is the pseudo-code corresponding to the binary search algorithm on an array A with a key key.
position := BinarySearch(A, 0, length(A) – 1, key)
function BinarySearch(A, low, high, key):
if high < lowreturn not_foundmid := (low + high) / 2if A[mid] > key
return BinarySearch(A, low, mid – 1, key)
else if A[mid] < keyreturn BinarySearch(A, mid + 1, high, key)elsereturn mid3.1.2 ProgramWrite program sort_search.s, which reads in a variable-size collection of positive 32-bit integers from the user, then sorts them in ascending order, and finally provides the user with the ability to search certain integers within this sorted collection.The following trace shows an example of the interaction between the user and this program. The special value -1 is used to indicate the end of the variable-size of input integers, and the end of the search requests.$ spim -f sort_search.sLoaded: /usr/share/spim/exceptions.s758437154741287682-141Found at index 30Not found82Found at index 742Not found15Found at index 0-1$A compiled C reference runnable on Linux is available on CSIF at /home/cs50jp/public/p3/sort_search. It should show what the expected output is for different inputs, so that you can compare with your assembly implementations.The program must be composed of 5 functions, as defined in the following subsections.3.1.2.1 Function loadFunction load has the equivalent C prototype: int load(int arr[], int max_len);.It reads integers from the user, one at a time, and stores them in the argument array arr. The function stops reading and returns when the user inputs a negative integer (which should not be part of the array) or when the maximum amount of integers, specified by argument max_len, has been read. The function returns the number of integers that have been actually read in the array.3.1.2.2 Function sortFunction sort has the equivalent C prototype: void sort(int arr[], int len);.It sorts the argument array arr of length len in ascending order, using the insertion sort algorithm.3.1.2.3 Function bsearchFunction bsearch has the equivalent C prototype: int bsearch(int arr[], int low, int high, int key);.It recursively finds the integer specified in argument key into the argument array arr using the binary search algorithm. It returns a negative integer if the search was unsuccessful, or the index of the key in the array.3.1.2.4 Function findFunction find has the equivalent C prototype: void find(int arr[], int len);.It reads integers from the user, one at a time, and launches a search into the argument array arr of length len using function bsearch() and displays the result of the search. The function stops reading integers from the user once the user inputs a negative number.3.1.2.5 Function mainThe main function calls the other functions in the following order:1.load to read the integer array from the user2.sort to sort the array3.find to find different keys in the array3.1.3 Additional information and constraints•Although the array itself should be declared in the data section as a global variable, only the main function is allowed to access it directly. All the other functions should receive the array via their first function argument.•The maximum number of integers that the array can contain is 10.•The MIPS calling conventions, as seen in class, must be strictly respected. All of your functions should have one prologue, one body, and one epilogue.•When writing a function, you should not assume that you know how registers are used in order functions; this means that:◦If you use a temporary register, you should not assume that it should retain its value across function calls.◦If you use a saved register, you need to save its value in the stack before using it.•When writing a function that necessitates a local variable (if you were to imagine the equivalent C code), you have a couple options:◦If the local variable doesn’t need to be persistent across function calls, you can probably optimize it away with a temporary register.◦If the local variable needs to be persistent across function calls, you can either allocate a saved register for it (if there aren’t too many local variables in the function) or you can allocate the space for an actual local variable in the stack.•Apart from all the floating-point instructions, and the multiply and divide instructions (mul*, div*) , you can use all the other MIPS instructions and pseudo-instructions.•Your code should be properly commented, and the different blocks of code should be well-organized and spaced, in order to improve its readability.3.1.4 TestingWhen debugging your code, the easiest is to simply interact with the program manually, by inputting the numbers directly.Once your code starts working and you want to be able to quickly test it, it can be useful to automate the testing. For example, you can build a input file that can be fed directly to the program upon execution:$ cat input_test.txt758437154741287682-1410824215-1$ cat input_test.txt | spim -f sort_search.sLoaded: /usr/share/spim/exceptions.sFound at index 3Not foundFound at index 7Not foundFound at index 0$4 SubmissionGradescope will be opened for submission on Monday, November 25 at 0:00. At that time, you will be able to submit your programs and have them be autograded.5 Academic integrityYou are expected to write this project from scratch. Therefore, you cannot use any existing source code available on the Internet.You are also expected to write this project yourself. Asking anyone someone else to write your code (e.g., a friend, or a “tutor” on a website such as Chegg.com) is not acceptable and will result in severe sanctions.You must specify any sources that you have viewed to help you complete this assignment (e.g., at the end of your source code). All of the submissions will be compared with MOSS to determine if students have excessively collaborated, or have used the work of past students.Any failure to respect the class rules, as explained above or in the syllabus, or the UC Davis Code of Conduct will automatically result in the matter being transferred to Student Judicial Affairs.Copyright © 2019 Joël Porquet
Reviews
There are no reviews yet.