FIT2085 Week 3 Laboratory Exercises

A.J.Hurst

Version 0.0

Table of Contents

1 Introduction
1.1 Some Global Code Fragments
1.2 Reuseable Python Fragments
1.3 Reuseable MIPS Fragments
2 Task 1: Compute Average with no additional space
2.1 Task 1 a
2.2 Task 1 b
2.3 Task 1 c
3 Task 2: Print even elements of list
3.1 Task 2 a
3.2 Task 2 b
3.3 Task 2 c
3.4 Reusable Python Fragments, task 2 ff
4 Task 3: Print temperatures above reference point
4.1 Task 3 a
4.2 Task 3 b
4.3 Task 3 c
5 Task 4: Print random element of list
5.1 Task 4 a
5.2 Task 4 b
5.3 Task 4 c
6 Task 5: Perform Fisher-Yates shuffle
6.1 Task 5 a
6.2 Task 5 b
7 Task 6: Print unique temperatures
7.1 Task 6 a
7.2 Task 6 b
8 Task 7: Print median value
8.1 Task 7 a
8.2 Task 7 b
9 Test Data
10 The Makefile
11 Document History
12 Indices
12.1 Files
12.2 Chunks
12.3 Identifiers


1. Introduction

This file defines the code for the solutions to week 3 laboratory in FIT2085 as a literate program.

1.1 Some Global Code Fragments

<edit warning 1.1> =
## ********************************************************** ## * DO NOT EDIT THIS FILE! * ## * Use $HOME/Desktop/FIT2085/week03/week03.xlp instead * ## **********************************************************
Chunk referenced in 2.1 2.3 2.5

1.2 Reuseable Python Fragments

<Python header 1.2> =
## T A S K taskNum ## ## A.J.Hurst ##
Chunk referenced in 2.1 2.3 3.1 3.2 4.1 4.2 5.1 5.2 6.1 7.1 8.1
<Python footer 1.3> =
## ## The End ##
Chunk referenced in 2.1 2.3 3.1 3.2 4.1 4.2 5.1 5.2 6.1 7.1 8.1
<get number of elements 1.4> =
numdays=int(input("Enter the number of days: ")) if numdays<=0: print("Must have at least 1 day") sys.exit(1)
Chunk referenced in 2.1 2.3 3.1 3.2 4.1 4.2 5.1 5.2 6.1 7.1 8.1
<allocate array space 1.5> =
# this expresses a dynamic space allocation in MIPS, with values on the stack values=[0 for i in range(numdays)]
Chunk referenced in 3.1 3.2 4.1 4.2 5.1 5.2 6.1 7.1 8.1
<enter values 1.6> =
for i in range(numdays): dayval=int(input("Enter the next day: ")) values[i]=dayval
Chunk referenced in 3.1 4.1

1.3 Reuseable MIPS Fragments

<MIPS print integer 1.7> =
li $v0,1 # print integer syscall lw $a0,ValueToPrint syscall
Chunk referenced in 2.5
<MIPS print string 1.8> =
li $v0,4 # print string syscall la $a0,StringToPrint syscall
Chunk referenced in 2.5 2.6
<MIPS read integer 1.9> =
li $v0,5 # input integer syscall syscall sw $v0,ValueRead
Chunk referenced in 2.6
<MIPS get number of elements 1.10> =
ori $v0,$0,5 # set syscall readint syscall sw $v0,numdays # save number of entries
Chunk referenced in 2.5
<MIPS set variable to zero 1.11> = sw $0,variable
Chunk referenced in 2.5
<MIPS condition less than 1.12> =
lw $t1,var1 lw $t2,var2 slt $t0,$t1,$t2
Chunk referenced in 2.6
<MIPS while 1.13> =
beq $t0,$0,loopend whilebody j whiletest loopend:
Chunk referenced in 2.6

2. Task 1: Compute Average with no additional space

2.1 Task 1 a

Write a Python program task1_a.py that performs the following steps:

"task1_a.py" 2.1 =
<Python header 1.2>(taskNum='1 A') <edit warning 1.1> import sys from builtins import input <get number of elements 1.4> sum=0 <python task1 for loop 2.2> avg=sum//numdays print("The average temperature is: ") print(avg) <Python footer 1.3>
<python task1 for loop 2.2> =
for i in range(numdays): dayval=int(input("Enter the next day: ")) sum+=dayval
Chunk referenced in 2.1

2.2 Task 1 b

Write a Python program task1_b.py which implements task1_a.py in preparation for the following MIPS translation.

"task1_b.py" 2.3 =
<Python header 1.2>(taskNum='1 B') <edit warning 1.1> import sys from builtins import input <get number of elements 1.4> sum=0 count=0 <python task1 while loop 2.4> avg=sum//numdays print("The average temperature is: ") print(avg) <Python footer 1.3>
<python task1 while loop 2.4> =
while count<numdays: dayval=int(input("Enter the next day: ")) sum+=dayval count+=1
Chunk referenced in 2.3

2.3 Task 1 c

Write a MIPS program task1_c.asm which implements task1_b.py faithfully.

"task1_c.asm" 2.5 =
## T A S K 1 C ## ## A.J.Hurst ## <edit warning 1.1> .text MAIN: <MIPS print string 1.8>(StringToPrint='EnterNum') <MIPS get number of elements 1.10>{Note 2.5.1} <MIPS set variable to zero 1.11>(variable='sum') <MIPS set variable to zero 1.11>(variable='count') <MIPS task1 loop 2.6>{Note 2.5.2} <MIPS task1 compute average 2.7> <MIPS print string 1.8>(StringToPrint='AvgTemp') <MIPS print integer 1.7>(ValueToPrint='avg') li $v0,10 # exit syscall syscall .data numdays: .word 0 sum: .word 0 count: .word 0 dayval: .word 0 avg: .word 0 EnterNum: .asciiz "Enter the number of days: " NextDay: .asciiz "Enter the next day: " AvgTemp: .asciiz "The average temperature is: "
{Note 2.5.1}
saves result in both $a0, numdays
{Note 2.5.2}
this loop performs the equivalent to the Python fragments <python task1 for loop 2.2> and <python task1 while loop 2.4>
<MIPS task1 loop 2.6> =
loops1: <MIPS condition less than 1.12>(var1='count', var2='numdays') <MIPS while 1.13>(loopend='loope1', whilebody=' <MIPS print string 1.8>(StringToPrint='NextDay') <MIPS read integer 1.9>(ValueRead='dayval') lw $v1,sum add $v0,$v0,$v1 sw $v0,sum lw $v0,count addi $v0,$v0,1 sw $v0,count ', whiletest='loops1')
Chunk referenced in 2.5
<MIPS task1 compute average 2.7> =
lw $v0,sum lw $v1,numdays div $v0,$v1 mflo $v0 sw $v0,avg
Chunk referenced in 2.5

3. Task 2: Print even elements of list

3.1 Task 2 a

Write a Python program task2_a.py that performs the following steps:

An example run of the program is:

          Enter the number of days:
          > 30
          Enter the next day:
          > 26
          ...
          Enter the next day:
          > 18
          The even elements of the lists are:
          26
          22
          ...
          18
          18
        

"task2_a.py" 3.1 =
<Python header 1.2>(taskNum='2 A') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <enter values 1.6> print("The even elements of the list are:") for i in range(numdays): dayval=values[i] if dayval%2==0: print(dayval) <Python footer 1.3>

3.2 Task 2 b

Write a simple Python program task2_b.py which implements task2_a.py.

"task2_b.py" 3.2 =
<Python header 1.2>(taskNum='2 B') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> print("The even elements of the list are:") i=0 while i<numdays: dayval=values[i] if dayval%2==0: print(dayval) i+=1 <Python footer 1.3>

3.3 Task 2 c

Write a MIPS program task2_c.asm which implements task2_b.py faithfully.

"task2_c.asm" 3.3 =

3.4 Reusable Python Fragments, task 2 ff

<Python while loop to read temperature inputs 3.4> =
i=0 while i<numdays: dayval=int(input("Enter the next day: ")) values[i]=dayval i+=1
Chunk referenced in 3.2 4.2 5.2 6.1 7.1 8.1

4. Task 3: Print temperatures above reference point

4.1 Task 3 a

Write a Python program task3_a.py that performs the following steps:

An example run of the program is:

          Enter the number of days:
          > 30
          Enter the next day:
          > 26
          ...
          Enter the next day:
          > 18
          Enter the reference temperature:
          > 23
          The number of temperatures equal or higher than the reference temperature is:
          12
        

"task3_a.py" 4.1 =
<Python header 1.2>(taskNum='3 B') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <enter values 1.6> reftemp=int(input("Enter the reference temperature: ")) hottercount=0 for i in range(numdays): dayval=values[i] if dayval>=reftemp: hottercount+=1 print("The number of temperatures equal or higher than the reference temperature is") print(hottercount) <Python footer 1.3>

4.2 Task 3 b

Write a Python program task3_b.py which implements task3_a.py.

"task3_b.py" 4.2 =
<Python header 1.2>(taskNum='3 B') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> reftemp=int(input("Enter the reference temperature: ")) hottercount=0 i=0 while i<numdays: dayval=values[i] if dayval>=reftemp: hottercount+=1 i+=1 print("The number of temperatures equal or higher than the reference temperature is") print(hottercount) <Python footer 1.3>

4.3 Task 3 c

Write a MIPS program task3_c.asm which implements task3_b.py faithfully.

"task3_c.asm" 4.3 =

5. Task 4: Print random element of list

5.1 Task 4 a

Write a Python program task4_a.py that performs the following steps:

Suggestion: You might want to write the Python and MIPS programs first without functions and, once they work, add the functions in. Exceptionally, we recommend you use syscall with code 42 (see the Missouri State documentation ) to draw a random number. In python we recommend you use the package random. Please ensure that the index (and value) printed out by your program for a given list is not fixed across runs.

"task4_a.py" 5.1 =
<Python header 1.2>(taskNum='4 A') import sys from builtins import input from random import seed,uniform seed() # start the random number generator def random(l): r=int(uniform(0,l)) return r <get number of elements 1.4> <allocate array space 1.5> for i in range(numdays): dayval=int(input("Enter the next day: ")) values[i]=dayval randindex=random(numdays) print("The index randomly drawn is:") print(randindex) print("The value at that index is:") print(values[randindex]) <Python footer 1.3>

5.2 Task 4 b

"task4_b.py" 5.2 =
<Python header 1.2>(taskNum='4 B') import sys from builtins import input from random import seed,uniform seed() # start the random number generator def random(l): r=int(uniform(0,l)) return r <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> randindex=random(numdays) print("The index randomly drawn is:") print(randindex) print("The value at that index is:") print(values[randindex]) <Python footer 1.3>

5.3 Task 4 c

Write a MIPS program task4_b.asm that implements task4_a.py faithfully. Here we expect you to define and use a function.

"task4_c.asm" 5.3 =

6. Task 5: Perform Fisher-Yates shuffle

In this task we ask you to write a function that shuffles the input list “in place”, i.e. without additional memory (or only constant memory, independent of the size of the list).

6.1 Task 5 a

Write a Python program task5_a.py that performs the following steps:

"task5_a.py" 6.1 =
<Python header 1.2>(taskNum='5 A') import sys from builtins import input from random import seed,uniform seed() # start the random number generator def random(l): r=int(uniform(0,l)) return r <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> l=0 while l<numdays: i=random(l) if i<=(l-1): temp=values[i] values[i]=values[l-1] values[l-1]=temp l+=1 print("The shuffled list is:") i=0 while i<numdays: print(values[i]) i+=1 <Python footer 1.3>
Chunk defined in 6.1,6.2

6.2 Task 5 b

Write a MIPS program task5_b.asm that implements task5_a.py faithfully.

An example run of the program is:

        Enter the number of days:
        > 30
        Enter the next day:
        > 26
        ...
        Enter the next day:
        > 18
        The shuffled list is:
        22
        18
        ...
        27
        

Here we use an algorithm called the Fisher-Yates shuffle.

Suggestion: we recommend you use syscall with code 42 to draw a random number.

"task5_a.py" 6.2 =
Chunk defined in 6.1,6.2
"task5_b.asm" 6.3 =

7. Task 6: Print unique temperatures

7.1 Task 6 a

Write a Python program task6_a.py that performs the following steps:

"task6_a.py" 7.1 =
<Python header 1.2>(taskNum='6 A') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> # allocate marking space seen=[0 for i in range(0,31)] print("Excluding the repeated numbers, the list is:") i=0 while i<numdays: temp=values[i] if not seen[temp]: print(temp) seen[temp]=1 i+=1 <Python footer 1.3>

7.2 Task 6 b

Write a MIPS program task6_b.asm that implements task6_a.py faithfully. An example run of the program is:

          Enter the number of days:
          > 30
          Enter the next day:
          > 26
          ...
          Enter the next day:
          > 18
          Excluding the repeated numbers, the list is:
          26
          19
          ...
          17
        

"task6_b.asm" 7.2 =

8. Task 7: Print median value

8.1 Task 7 a

Write a Python program task7_a.py that performs the following steps:

To do this, we revise task 6 by making the variable seen count the number of occurences. Then we scan through the seen list for all possible temperatures, accumulating the occurences for each temperature we go, until we reach the halfway point of the total number of occurences.

"task7_a.py" 8.1 =
<Python header 1.2>(taskNum='6 A') import sys from builtins import input <get number of elements 1.4> <allocate array space 1.5> <Python while loop to read temperature inputs 3.4> # allocate marking space seen=[0 for i in range(0,31)] i=0 while i<numdays: temp=values[i] seen[temp]+=1 i+=1 i=0 count=0 halfway=numdays//2 while i<31: count+=seen[i] if count>=halfway: break i+=1 print("The median value of the list is:") print(i) <Python footer 1.3>

8.2 Task 7 b

Write a MIPS program ( task7_b.asm ) which implements task7_a.py faithfully.

An example run of the program is:

          Enter the number of days:
          > 30
          Enter the next day:
          > 26
          ...
          Enter the next day:
          > 18
          The median value of the list is:
          22
        
Note that for this task you may need to do some research and implement code more complicated that may at first seem necessary.

"task7_b.asm" 8.2 =

9. Test Data

The first value in what follows is a count of the number of subsequent values. The last value in the list is the reference temperature, only used in task 3.

"testString1" 9.1 =
30 26 19 22 21 13 22 18 22 20 27 18 24 15 28 26 27 20 20 23 24 27 26 15 23 22 20 23 17 18 18 23

10. The Makefile

Define your Makefile here.

"Makefile" 10.1 =
default=program GenFiles = .program install-program include ${HOME}/etc/MakeXLP install-program: program.tangle cp .program ${HOME} touch install-program install: install-program all: install program.dvi clean: litclean -rm $(GenFiles)

11. Document History

20170807:163647 ajh 0.2 completed to week 3 checkpoint
20170807:124316 ajh 0.1 first working MIPS (task1_c)
20170804:131714 ajh 0.0 first draft, constructed from code fragments

12. Indices

12.1 Files

File Name Defined in
Makefile 10.1
task1_a.py 2.1
task1_b.py 2.3
task1_c.asm 2.5
task2_a.py 3.1
task2_b.py 3.2
task2_c.asm 3.3
task3_a.py 4.1
task3_b.py 4.2
task3_c.asm 4.3
task4_a.py 5.1
task4_b.py 5.2
task4_c.asm 5.3
task5_a.py 6.1, 6.2
task5_b.asm 6.3
task6_a.py 7.1
task6_b.asm 7.2
task7_a.py 8.1
task7_b.asm 8.2
testString1 9.1

12.2 Chunks

Chunk Name Defined in Used in
MIPS condition less than 1.12 2.6
MIPS get number of elements 1.10 2.5
MIPS print integer 1.7 2.5
MIPS print string 1.8 2.5, 2.5
MIPS read integer 1.9
MIPS set variable to zero 1.11 2.5, 2.5
MIPS task1 compute average 2.7 2.5
MIPS task1 loop 2.6 2.5
MIPS while 1.13 2.6
Python footer 1.3 2.1, 2.3, 3.1, 3.2, 4.1, 4.2, 5.1, 5.2, 6.1, 7.1, 8.1
Python header 1.2 2.1, 2.3, 3.1, 3.2, 4.1, 4.2, 5.1, 5.2, 6.1, 7.1, 8.1
Python while loop to read temperature inputs 3.4 3.2, 4.2, 5.2, 6.1, 7.1, 8.1
allocate array space 1.5 3.1, 3.2, 4.1, 4.2, 5.1, 5.2, 6.1, 7.1, 8.1
enter values 1.6 3.1, 4.1
get number of elements 1.4 2.1, 2.3, 3.1, 3.2, 4.1, 4.2, 5.1, 5.2, 6.1, 7.1, 8.1
python task1 for loop 2.2 2.1
python task1 while loop 2.4 2.3

12.3 Identifiers

Identifier Defined in Used in

8 accesses since 07 Aug 2017, HTML cache rendered at 20170807:0242