Homework 1.
Si scrivano le seguenti funzioni che operano su matrici, le quali prendono in $a0 l'indirizzo del primo elemento in memoria di una matrice quadrata, il cui numero di righe e colonne sia dato in $a1.
1) trovaelementominimo: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento minimo
2) trovaelementomassimo: restituisce in $v0 e $v1 rispettivamente l'indice di riga e di colonna dell'elemento massimo
3) permutarighe: la funzione prende nei registri $a2 e $a3 gli indici k e j rispettivamente, e sostituisce in memoria la matrice A con la matrice A' ottenuta a partire da A permutandone le righe k e j.
Esempio:

Homework 2.
Si scriva una funzione cercasottostringa che prenda in $a0 e $a1 gli indirizzi iniziali delle stringhe s e z rispettivamente.
La funzione restituisca in $v0 il valore 1 se la stringa z è contenuta in s, e 0 altrimenti.
Esempio:
s="La città di Roma è molto calda d'estate". Se z="calda", la funzione restituisce 1. Se z = "fredda" la funzione restituisce 0.

Homework 3.
Scrivere la funzione che restituisca in $v0 il valore del prodotto scalare tra due vettori v e z, i cui indirizzi in memoria siano dati in $a0 e $a1 rispettivamente, e la cui lunghezza sia data in $a2. Si ricorda che il prodotto scalare tra due vettori v e z, con v=<v₁, v₂, ..., v_k> e z=<z₁, z₂, ..., z_k>
vale p= v₁*z₁+ v₂*z₂+ ...+ v_k*z_k.
Esempio:
v=<2,3,4> e z=<1,2,1>. Il valore di p è 2*1+3*2+4*1=12.

1) Appendice A, del seguente libro:
David A. Patterson, John L. Hennessy, "Struttura e Progetto dei Calcolatori", ed. Zanichelli

2) Manuale di istruzioni del simulatore SPIM .


Entrambi questi testi e molti altri, sono disponibili online alla
pagina relativa alla documentazione sul simulatore SPIM .

elem_pari.s

parole_pari.s

3. Si scriva un programma in assembler MIPS che, data una matrice A di interi in memoria, stampi sulla console l'elenco degli elementi A(i,j) per i quali i==j-1. Esempio:

matrice_stamp_el.s

4. Si scriva un programma in assembler MIPS che, data una stringa A di caratteri in memoria, stampi sulla console una stringa B ottenuta dalla precedente sostituendo ogni occorrenza di vocale con il carattere "1" e ogni consonante con il carattere "0". Per semplicità considerare come consonante anche i caratteri numerici o speciali. Esempio:
Stringa A: "Esercizio"
Stringa B: "101001011"

5. Si scriva un programma in assembler MIPS che, data una stringa A di caratteri in memoria, scriva se è palindroma a meno di spazi. Esempio:
Stringa1: "ailatiditalia" è palindroma
Stringa2: "aabbccdc c b b aa" è palindroma
Stringa3: "acetone" non è palindroma

6. Si scriva un programma in assembler MIPS che, data una stringa A, conti il numero di caratteri che la compongono e le occorrenze del carattere "a". Il programma deve inoltre scrivere in memoria una stringa B ottenuta dalla stringa A letta al contrario. Esempio:
Stringa A: "enoteca" contiene 7 caratteri di cui 1 occorrenza del carattere "a"
Stringa B: "acetone"

7. Si scriva un programma in assembler MIPS che, data in memoria una matrice A di 3 righe e 5 colonne, scriva in memoria e sulla console una matrice B corrispondente alla trasposizione di A. Esempio:

8. Si scriva un programma in assembler MIPS che calcoli, attraverso una doppia chiamata ricorsiva, la funzione f(n) così definita:

Soluzione: fibonacci_complessitesponenziale.s

9. Si scriva un programma in assembler MIPS che calcoli, attraverso una sola chiamata ricorsiva, la funzione f(n) a due valori così definita:

Soluzione: Fibonacci_complessitlineare.s

10. Si scriva un programma in assembler MIPS che calcoli, attraverso chiamate mutuamente ricorsive delle funzioni f() e g(), il valore della funzione f(n).

mutuaricorsione.s

11. Scrivere in assembler MIPS un programma che calcoli ricorsivamente il valore di f(10), dove f(x) è definita come segue:

es11.s

12. Scrivere in assembler MIPS un programma che, data una stringa Z di caratteri, ne ordini i caratteri in ordine alfabetico decrescente, utilizzando la funzione ricorsiva bubble(x) che prende in ingresso l'indirizzo (x) del carattere iniziale della stringa da ordinare e restituisce una stringa ordinata, allo stesso indirizzo della stringa di partenza (ovvero la funzione bubble(x) rimpiazza la stringa di partenza con la stringa ordinata).

Soluzione: sort.s

13. Scrivere un programma in assembler MIPS che determini se una stringa Z è palindroma utilizzando una funzione ricorsiva f(x,y) che prende in ingresso l?indirizzo del carattere iniziale (x) e l?indirizzo dell?ultimo carattere utile (y) e restituisce in uscita il valore 1 se la stringa è palindroma e zero altrimenti.

Soluzione: palindrom.s

14. Scrivere un programma in assembler MIPS che calcoli la somma dei primi 5 elementi di un vettore di interi facendo uso di una funzione iterativa somma_primi_cinque che prende in ingresso nel registro $a0 l'indirizzo del vettore, e restituisce in uscita, nel registro $v0, la somma degli elementi letti.

Soluzione: scritto3-6.s

15. Scrivere un programma in assembler MIPS che calcoli la funzione ricorsiva McCarthy91(n) di un qualsiasi numero n letto in ingresso.
Si veda il file: McCharty91.pdf per una definizione formale della funzione McCarthy91.

Soluzione: McCarthy.s

16. Esercizio sul fattoriale in due versioni del caso base, per risolvere il dubbio di qualcuno....
fattoriale_giusto1.s: fattoriale_giusto1.s
fattoriale_giusto2.s: fattoriale_giusto2.s

17. Scrivere un programma che decida se una matrice in ingresso è simmetrica o no. Il programma deve invocare una funzione f che prende in ingresso due parametri: l'indirizzo della matrice in memoria e la sua dimensione (n=numero di righe e di colonne). La funzione f deve restituire il valore 1 se la matrice è simmetrica e 0 altrimenti. La funzione f deve prevedere un confronto tra la prima riga e la prima colonna e poi chiamare sè stessa ricorsivamente sulla sottomatrice ottenuta eliminando la prima riga e la prima colonna.

Soluzione: matrice_simmetrica_ricorsivo1.s

18. Scrivere un programma che data una word in memoria decida se la sua rappresentazione binaria è palindroma. Si prevedano due metodi risolutivi, ovvero: A) si confronti il bit i-esimo con il bit 32-(i-1)-esimo per 1<=i<=16. B) si crei una word ottenuta da quella iniziale rovesciandone la rappresentazione binaria e si confronti tale parola con quella di partenza.

Soluzione:
word_palindroma_metodoA.s
word_palindroma_metodoB.s

19. (Esercizio di sbarramento dell'esame del 25 Giugno 2007)

Si scriva un programma in assembler MIPS che carichi un numero x presente in memoria e calcoli il numero y ottenuto a partire da x prendendo della sua rappresentazione binaria solo la cifra più significativa (la prima cifra non nulla a partire da sinistra). Si stampi la rappresentazione di y in base 10. Non è consentito l’uso di istruzioni aritmetiche (addizione, sottrazione, divisione, moltiplicazione).

Esempio: x=14₁₀=1110₂ ---> y=1000₂=8₁₀
Il programma deve stampare il numero 8.

Soluzione: sbarramento_25_06_2007.s

20. Scrivere un programma che dato un intero in memoria, usi le operazioni logiche per calcolare il suo complemento a due. Stampare il risultato ottenuto con il servizio di sistema operativo per la stampa di numeri interi. Stamparne inoltre la rappresentazione binaria.

Soluzione:
complemento_a_2.s

21. Si scriva un programma che legga due valori in ingresso: i e b, con i compreso tra 1 e 32, e b tra 0 e 1.
Sia data una word W in memoria contenente una stringa di bit. Il programma deve configurare il bit i-esimo di W con il valore di b. Soluzione:
stampabit.s