Coursework Details

Coursework Aim

This exercise will allow you to demonstrate writing algorithms in the language of the computer.

Submission details

Submission of coursework will be performed using Turnitin on Canvas.  You need to upload two files: the first file is a Word document that includes the answers to the Q1, Q2 and Q3 below. The second  file is the MIPS programs for the assignment problem. Upload your files to the submission boxes        within the Assignments page of the Canvas module by midnight of the day of the deadline.

Deadline: 23:59 on 3rd April 2023

You are expected to meet all submission deadlines as set. If you are ill or experience problems that prevent you from meeting the deadlines that are outside of your control, then the University            Mitigating Circumstances policy may apply. Please refer to MyKingston > Faculties > ECE for             guidance on the Extensions and Mitigation Circumstances process. Requests for mitigation must be submitted with evidence through OSIS. Please                                                                                                    see https://kingstonuniversity.sharepoint.com/sites/mykingston/myfaculty/ECE/Pages/emc.aspx for details of the policy.

Coursework Brief

The coursework consists of some program code with three questions to answer: Q1, Q2 and Q3. You should compile your answers to Q1, Q2 and Q3 and related discussion in a Word or ODT document   to submit to Canvas. Please add a cover page to the document showing your name, K number,            module title and code, and assignment title. Do NOT use this document as a template.

The C program shown in the Appendix 1 below will add the coursework array marks to the exam array marks and store them in the results array. Assume the number of students is 8. The program  will then sort the marks into the sorted array. Note that Bubble Sort is a function called by the main program. Finally, the program will create counters for the number of students with a result >= 70,   >=60, >=50 and < 50 and output the counter grades.

Q1      Use the MIPS instruction set and the MARS MIPS simulator to:

(i)       Write the equivalent MIPS assembly code unoptimised for the C-code shown above. Remember to add comments to your assembly code.

a.   Test the assembly code program via the MARS MIPS simulator to ensure expected and actual outcome.

b.   Take note of many instructions are executed for your code.

(ii)         Optimise using inline expansions and loop unrolling to use a minimum number

of instructions in to run your assembly code and explain the methods done.

a.   Test the assembly code program via the MARS MIPS simulator.

b.   How many instructions are executed for your code with the new optimisations.

(iii)       Within the report show the following:

a.   all test results of running the assembly code, highlight the expected and actual outcome.

b.   Show the instruction counts including a breakdown R, I and J types for both (i) unoptimised and (ii) optimised code.

c.    Describe the optimisation methods used, highlight changes within you code that have been made to achieve this. (50 marks)

Q2    Consider the basic MIPS 5-stage pipeline (IF, ID, EX, MEM, WB).  Assume that there is

full forwarding and branch not taken.

(i)      Show the pipeline execution table of your unoptimised code for the Bubble Sort function (note: you only to show a single iteration of each of the loops).

(ii)      Describe each of the possible pipelining hazards.

(iii)     Highlight any hazards found within your pipeline execution table and explain

how these hazard(s) can be resolved. (20 marks)

Q3    Algorithms

(i)          Using a copy of the table below, write down the state of the int[] results array before and after the first iteration of the outer (i loop) of the              bubble_sort function fromAppendix 1 – Code for Q1 & Q2.

(ii) Bubble sort is a classic O(n2) algorithm, for some variety consider something

that is naively O(2n) – the so-called Fibonacci sequence numbers, which are possibly an attempt to model animal breeding (supposedly rabbits), due to      Leonardo of Pisa [1] (who was nicknamed Fibonacci, although maths history   suggests the sequence itself pre-dates him and was written about earlier by    Arabic mathematicians, as well as having been employed in India, ancient

Greece etc. [2]), and like the factorial function the numbers get large quickly [3] even though they have a very simple formula:

Fn  = Fn − 1 + Fn − 2,         F0  = 0, F1  = 1

(the values of Fn  are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)  The formula is easy to translate into an “algorithm” and code, for example some straightforward recursive Java syntax could be:

public long Fibonacci(int n) {

if (n <= 0) return 0;

if (n == 1) return 1;

return Fibonacci(n - 1) + Fibonacci(n - 2); }

Illustrate the exponential complexity of the function Fibonacci by           explaining how the function computes Fibonacci(5) = 13. You could do this with a “tree”, a diagram, a table or list of numbers.

(iii)        The recursion in the Fibonacci function can be “unrolled” to make an iterative

algorithm with O(N) complexity and O(1) additional storage, or a dynamic  one with O(N) additional storage. Choose one (iterative or dynamic),            reproduce it in your answer using one of Java, Python, JavaScript, or C/C++ syntax (as appropriate to your course), and explain briefly how the “big O” expression relates to the code.

NB: If you ask ChatGPT for help with this it will probably include an example utilising “memoisation” – obviously if you decide to use it, you need to         explain it adequately too, and should always reference the source(s) used. (30 marks)

Appendix 1 – Code for Q1, Q2 & Q3(i)

// MAIN PROGRAM

void main() {

// Coursework is an array, each mark ranges from 0 to 50

int[] coursework = new int[]{12,28,48,36,32,41,25,09};

// Exam is an array, each mark ranges from 0 to 50

int[] exam = new int[]{33,15,39,42,36,21,23,22};

// Results is an array

int[] results; // init as zeros to start

// Sorted is an array

int[] sorted; // init as zeros to start

// result = coursework + exam. // It goes from 0 to 100.

for (i = 0; i < y; i++) {

results [i] = coursework [i] + exam [i];

}

// use the bubble sort function to populate the sorted array. sorted = bubble_sort(results, y);

// Finally, the program will create counters for the number of // students with a result >=70, >=60, >=50 and < 50

for (i = 0; i < y; i++) {

if (results[i] >= 70)

a = a + 1;

else if(results[i] >= 60)

b = b + 1;

else if(results[i] >= 50)

c = c + 1;

else

f = f + 1;

}

Console.WriteLine($"No. students with A: {a}");    Console.WriteLine($"No. students with B: {b}");    Console.WriteLine($"No. students with C: {c}");    Console.WriteLine($"No. students that Failed {f}"); // Main program code ends here

}

// BUBBLE SORT function code

int[] bubble_sort(int[] arr, int n) {

int i, j;

int temp;

for (i = 0; i < n - 1; i++) {

for (j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

return arr;

}

Appendix 2 – References/further reading for Q3

[1] Boldt, A. and Wikipedia, 2023. Fibonacci number. Available at:

https://en.wikipedia.org/wiki/Fibonacci_number(Accessed: 21/02/2023).

[2] Scott, T.C. and Marketos, P., 2014. On the origin of the Fibonacci Sequence. MacTutor History of

Mathematics, 23.

[3] The On-line Encyclopedia of Integer Sequences ®, 2023, Available at:https://oeis.org/A000045 (Accessed: 22/02/2023).

Academic Misconduct

Plagiarism is presenting somebody else’s work as your own. It is an offence to copy                materials (even if it is a phrase or a sentence) from the Internet or other work and                  publications. You must write everything in your own words. Also, using tools such as code     convertors / generators to complete the practical elements of this assignment is an offence. Collusion is also an offence i.e., allowing another student to use your work even if it is just as a template! There is a heavy penalty for plagiarism and collusion which could see you             receiving a ZERO mark and your subsequent academic record may be affected. Further          details about plagiarism and referencing can be found at:

http://www.kingston.ac.uk/aboutkingstonuniversity/howtheuniversityworks/policiesandregula

tions/documents/Plagiarism_%20Student.pdf