Compito A del 01-09-05 - Programmazione

================================================================
Esercizio Assembler MIPS ================================================================
E’ data una rappresentazione lineare (mediante array) di un albero binario di ricerca contenente interi positivi.  In tale rappresentazione:
 (i) la posizione di indice zero dell’array contiene la dimensione in byte dell’array stesso,
 (ii) uno zero in una posizione dell’array indica l’assenza nell’albero del nodo corrispondente,
(iii) i nodi esterni (che non contengono informazione) sono rappresentati con uno zero nella corrispondente posizione dell’array oppure non sono esplicitamente rappresentati. Vedi anche Figura b di seguito riportata.

Come esercizio si chiede di fornire il codice MIPS della procedura insert per l’inserimento di un elemento nell’albero binario di ricerca.  La procedura:
(i) ritorna zero quando l’array non ha spazio sufficiente a contenere l’elemento da inserire (overflow),
(ii) ritorna l’offset della posizione in cui è stato inserito l’elemento quando nell’array vi è ha spazio sufficiente.
N.B. La procedura ha complessità  O(log n).

Fornire il codice della procedura richiesta utilizzando il file risultato1.s a tale scopo predisposto.
N.B. Non modificare né i dati specificati nella direttiva .data né il codice del  main presenti nel file risultato.s, pena la non presa in considerazione della soluzione.

Traccia di soluzione

================================================================
Esercizio JAVA
================================================================
La classe Graph contenuta nel file risultato1.zip realizza un grafo non orientato rappresentato mediante matrice delle adiacenze. In tale rappresentazione i vertici del grafo sono identificati dagli interi 1..N.

Come esercizio si chiede di fornire il codice JAVA del metodo public int[] prim(int s) che calcola con l’algoritmo di Prim (a partire dal vertice s) un Minimum Spanning Tree dell’oggetto grafo a cui viene applicato e che ritorna un array contente l’albero calcolato rappresentato come vettore dei predecessori.

Al fine di facilitare la codifica dell’algoritmo richiesto viene fornita la classe MyVertexPQ che implementa il tipo di dato Coda con Priorità definito dall’interfaccia VertexPQ.

Si noti la presenza in tale interfaccia dei metodi particolari:
    a)  public boolean isIn(int v) che ritorna “true” se il vertice “v” è nella coda;
    b)  public int dis(int v)  che ritorna la priorità (“distanza”) associata al vertice “v”
         anche quando “v” è stato estratto dalla coda.

La classe Main nel file risultato.java contiene il codice per la verifica del corretto funzionamento del metodo richiesto. Tale codice è completo e non deve essere modificato in alcun modo, pena la non presa in considerazione della soluzione fornita.

Traccia di soluzione

Compito B del 01-09-05 - Programmazione

================================================================
Esercizio Assembler MIPS ================================================================
E’ data una rappresentazione lineare (mediante array) di un albero binario di ricerca contenente interi positivi.  In tale rappresentazione:
 (i) la posizione di indice zero dell’array contiene la dimensione in byte dell’array stesso,
 (ii) uno zero in una posizione dell’array indica l’assenza nell’albero del nodo corrispondente,
(iii) i nodi esterni (che non contengono informazione) sono rappresentati con uno zero nella corrispondente posizione dell’array oppure non sono esplicitamente rappresentati. Vedi anche Figura b di seguito riportata.

Come esercizio si chiede di fornire il codice MIPS della procedura find per la ricerca di un elemento nell’albero binario di ricerca.  La procedura:
 (i) ritorna zero quando l’albero non contiene l’elemento cercato,
 (ii) ritorna l’offset della posizione in cui è stato trovato l’elemento quando nell’array contiene l’elemento cercato.
 N.B. La procedura ha complessità  O(log n).

Fornire il codice della procedura richiesta utilizzando il file risultato2.s a tale scopo predisposto.  N.B. Non modificare né i dati specificati nella direttiva .data né il codice del  main presenti nel file risultato.s, pena la non presa in considerazione della soluzione.

 Traccia di soluzione

================================================================
Esercizio JAVA
================================================================
La classe Graph contenuta nel file risultato2.zip realizza un grafo non orientato rappresentato mediante matrice delle adiacenze. In tale rappresentazione i vertici del grafo sono identificati dagli interi 1..N.

Come esercizio si chiede di fornire il codice JAVA del metodo public int[] dijkstra(int s) che calcola con l’algoritmo di Dijkstra l’albero dei cammini minimi (con origine in s) dell’oggetto grafo a cui viene applicato e che ritorna un array contente l’albero calcolato rappresentato come vettore dei predecessori.

Al fine di facilitare la codifica dell’algoritmo richiesto viene fornita la classe MyVertexPQ che implementa il tipo di dato Coda con Priorità definito dall’interfaccia VertexPQ.

Si noti la presenza in tale interfaccia dei metodi particolari:
    a)  public boolean isIn(int v) che ritorna “true” se il vertice “v” è nella coda;
    b)  public int dis(int v)  che ritorna la priorità (“distanza”) associata al vertice “v”
         anche quando “v” è stato estratto dalla coda.

La classe Main nel file risultato.java contiene il codice per la verifica del corretto funzionamento del metodo richiesto. Tale codice è completo e non deve essere modificato in alcun modo, pena la non presa in considerazione della soluzione fornita.

Traccia di soluzione