Compito A del 01-04-03 - Programmazione

La prova e' costituita da due esercizi di programmazione, un esercizio in assembler MIPS e un esercizio in JAVA.

================================================================
Esercizio Assembler MIPS
================================================================
Dato un numero intero positivo “n”, si vuole calcolare la funzione di Fibonacci F(n) del numero.
Scrivere in assembler la funzione ricorsiva "fib" che ritorna il valore della funzione di Fibonacci del numero passato come argomento.
Utilizzare il "main" di prova per verificare il corretto funzionamento della funzione.
Il candidato ha a disposizione il seguente file:
-          "fib.txt" che deve essere rinominato in "risultato.s".
La soluzione deve essere fornita con il file "risultato.s".

Traccia di soluzione

================================================================
Esercizio JAVA
================================================================
La classe ArrayBinTreeDFS implementa un albero binario utilizzando un array (rappresentazione lineare di un albero binario).
I metodi messi a disposizione dalla classe consentono la navigazione nell’albero e la marcatura dei nodi durante un eventuale attraversamento.
Dato che un albero binario può essere considerato anche come un grafo non orientato, connesso e aciclico, ha senso porsi il problema di determinare il cammino che connette due dati vertici (nodi) del grafo (albero).
Come esercizio, realizzare in Java il metodo:
                 public int[] pathDFS(int s, int z)
che ritorna un vettore contenete i vertici del cammino che connette il vertice sorgente s al vertice target z. L’algoritmo per la determinazione del cammino deve essere formulato in modo iterativo (usando uno Stack di interi) e deve basarsi su di una strategia di attraversamento del grafo (albero) di tipo DFS (prima in profondità).
Si noti che in questo caso gli adiacenti di un vertice sono (quando esistono) il padre, il figlio sinistro e il figlio destro.
Si noti inoltre che, ad ogni iterazione dell’algoritmo, lo Stack contiene i vertici del cammino dal nodo corrente al nodo sorgente s.
Il candidato ha a disposizione i seguenti file:
-          “IntStack.java”  e file correlati che realizzano una Stack di interi
-          “ArrayBinTreeDFS.txt” file da rinominare in "risultato.java".
La soluzione deve essere fornita con il file "risultato.java".

Traccia di soluzione

 ================================================================
Al termine della prova il candidato dovra' lasciare nella directory di lavoro i seguenti file:
- risultato.s       soluzione esercizio MIPS
- risultato.java    soluzione esercizio JAVA
N.B. I files “risultato.s” e “risultato.java” vengono corretti solo se contengono come prima riga un commento con l'indicazione del COGNOME, NOME, PROFESSORE, NUMERO POSTAZIONE di lavoro del candidato.

Compito B del 01-04-03 - Programmazione

La prova e' costituita da due esercizi di programmazione, un esercizio in assembler MIPS e un esercizio in JAVA. 

================================================================
Esercizio Assembler MIPS
================================================================
Dati due numeri interi positivi, si vuole determinare il “massimo comune divisore” dei due numeri.
Scrivere in assembler la funzione ricorsiva "mcd" che ritorni il “massimo comune divisore” dei due numeri passati come argomento.
Utilizzare il "main" di prova per verificare il corretto funzionamento della funzione.
Il candidato ha a disposizione il seguente file:
-          "mcd.txt" che deve essere rinominato in "risultato.s".
La soluzione deve essere fornita con il file "risultato.s". 

Traccia di soluzione

================================================================
Esercizio JAVA
================================================================
La classe ArrayBinTreeBFS implementa un albero binario utilizzando un array (rappresentazione lineare di albero binario).
I metodi messi a disposizione della classe consentono la navigazione nell’albero e la marcatura dei nodi durante un eventuale attraversamento.
Dato che un albero binario può essere considerato anche come un grafo non orientato, connesso e aciclico, ha senso porsi il problema di determinare il cammino che connette due dati vertici (nodi) del grafo (albero).
Come esercizio, realizzare in Java il metodo:
                 public int[] pathBFS(int s, int z)
che ritorna un vettore contenete i vertici del cammino che connette il vertice sorgente s al vertice target z. L’algoritmo per la determinazione del cammino deve essere formulato in modo iterativo (usando una Coda di interi) e deve basarsi su di una strategia di attraversamento del grafo (albero) di tipo BFS (prima in ampiezza).
Si noti che in questo caso gli adiacenti di un vertice sono (quando esistono) il padre, il figlio sinistro e il figlio destro.
Si suggerisce di usare il vettore dei predecessori int[] pred, in cui inserire, quando si scopre un nuovo vertice k, il predecessore di k nel cammino dal vertice sorgente s al vertice corrente k.
Il candidato ha a disposizione i seguenti file:
-          “IntQueue.java”  e file correlati che realizzano una Coda di interi
-          “ArrayBinTreeBFS.txt” file da rinominare in "risultato.java".
La soluzione deve essere fornita con il file "risultato.java".

Traccia di soluzione

 ================================================================
Al termine della prova il candidato dovra' lasciare nella directory di lavoro i seguenti file:
- risultato.s       soluzione esercizio MIPS
- risultato.java    soluzione esercizio JAVA
N.B. I files “risultato.s” e “risultato.java” vengono corretti solo se contengono come prima riga un commento con l'indicazione del COGNOME, NOME, PROFESSORE, NUMERO POSTAZIONE di lavoro del candidato.