Homework < Infogen

Tags: view all tags

%TOC%

---+++ <font color=990000 size="+3">Homework A.A. 2013/2014</font> <br><br>

---+++ <font color=black size="+1">Informazioni</font>

Quest pagina contiene le informazioni relative agli Homework assegnati agli studenti. <br>

Gli Homework consegnati saranno verificati automaticamente. In particolare si verificherà:
   * che la compilazione non generi errori
   * che l'esecuzione sia corretta su diversi input
   * che non ci sia eccessiva somiglianza con altri Homework consegnati

La verifica di similarità sarà anch'essa effettuata in modo automatico. In caso di copiatura, si riterranno nulli sia gli elaborati del copiante che del copiato.

Gli Homework dovranno essere consegnati entro la relativa scadenza che sarà comunicata in classe e che sarà ben visibile nella  [[http://twiki.di.uniroma1.it/~infogen/consegna-homework-canale2.html][pagina delle consegne]]. Non si accetteranno proroghe. 

La consegna si effettua online alla pagina [[http://twiki.di.uniroma1.it/~infogen/consegna-homework-canale2.html][Consegna Homework]]. Per consegnare è necessario registrarsi su Twiki a questa <a href="http://twiki.di.uniroma1.it/twiki/view/TWiki/TWikiRegistration">pagina</a>.

Il superamento degli Homework permetterà di non sostenere la prova di laboratorio ed, eventualmente, di disporre anche di un bonus di incremento di 1 o due punti punto sul voto finale come descritto in [[Modalità d'esame]].

In caso vi siano domande o problemi, potete rivolgetevi a Simone Silvestri (silvestris@di.uniroma1.it)


---+++ <font color=black size="+1">Regole generali</font>

1) Seguire esattamente le specifiche dell'input e dell'output.

2) Non includere getchar(), scanf(), System("pause") o qualunque altra chiamata che blocchi l'esecuzione del programma alla fine del codice dell'esercizio (utilizzatele se volete per provare il funzionamento ma non includete le istruzioni di attesa alla fine del file nella versione inviata).

3) Leggere l'input con scanf semplici. Es: scanf("%d",&n) per leggere un intero n, non inserire stampe del tipo printf("Inserisci il valore\n");

4) Inviare un unico file .zip contenente *tutti* i sorgenti (.c) degli esercizi dell'Homework. <font color=red >ATTENZIONE: non si deve fare una cartella contenente i file sorgenti e poi fare il .zip della cartella, ma si deve creare un file .zip contenente *solo i file* .c</font>. Controllare bene l'estensione dei file inseriti nel file .zip, essa deve essere (.c) e non (.cc o altro). 

5) Vanno inviati SOLO i sorgenti di codice e NON i file compilati (.out, .exe).

6) Il nome da dare ai file contenenti i sorgenti c è: _NomeCognome.NumEsercizio.c_ . Per Paolino Paperino: _PaolinoPaperino.1.c_ per il primo esercizio, _PaolinoPaperino.2.c_ per il secondo, _PaolinoPaperino.3.c_ per il terzo e così via. Il nome da dare al file zip è: _NomeCognome.zip_. Sulle macchine del laboratorio di calcolo ciò si ottiene col seguente comando di shell (relativamente ai sorgenti dell'esempio):<P>
<center><font color=black size="+1"><B>$ zip _PaolinoPaperino.zip_ _PaolinoPaperino.1.c_ _PaolinoPaperino.2.c_ _PaolinoPaperino.3.c_ </B></font></center><P>
Per verifica si può impartire il comando:<P>
<center><font color=black size="+1"><B>$ unzip _PaolinoPaperino.zip_ </B></font></center><P>
che estrae i file contenuti nel file zip e li ricrea nello stesso direttorio.

7) *Per inviare i sorgenti C*:

7.1) E' necessario essere iscritti al sito twiki.di.uniroma1.it (si può fare dal link: TWiki.TWikiRegistration) .

7.2) Creare un file .zip contenente tutti i sorgenti degli esercizi dell'Homework

7.3) Collegarsi alla pagina [[http://twiki.di.uniroma1.it/~infogen/consegna-homework-canale2.html][Consegna Homework]] 

7.4) Inserire i propri dati (wikiname e password sono i dati di accesso a twiki)

7.5) Cliccare su "Browse" (o "Sfoglia", a seconda della lingua del vostro browser internet) e selezionare il file .zip contentente le vostre soluzioni  

7.3) Cliccare su "spedisci la tua soluzione!" per effettuare la consegna

7.4) Riceverete una e-mail di conferma a cui non bisogna inviare reply

8) Se le soluzioni vengono inviate più di una volta, ogni nuovo invio sovrascrive i precedenti. Verrà quindi considerato l'ultima versione da voi inviata. 


---+++ <font color=black size="+1">Risultati</font>


   * I risultati del terzo Homework si possono trovare [[%ATTACHURL%/risultati_hw_3_2014.html][qui]]
   * I risultati del secondo Homework si possono trovare [[%ATTACHURL%/risultati_hw_2_2014.html][qui]]
   * I risultati del primo Homework si possono trovare [[%ATTACHURL%/risultati_hw_1_2014.html][qui]]
   * I risultati dell'Homework di prova si possono trovare [[%ATTACHURL%/risultati_hw_prova_2014.html][qui]]
   


---+++ <font color=black size="+1">Homework da consegnare</font>

   * *<b>Homework 3</b> - Consegna entro: <font color="red"> 20 Giugno 2014 ore 24:00</font>*

<b><u>Esercizio 1</u></b><br>
Un albero binario e' definito attraverso la seguente struttura:

<verbatim>
typedef struct int_bin_tree{

	int key;
	struct int_bin_tree *left;
	struct int_bin_tree *right;

}int_bin_tree;
</verbatim>

L'esercizio prevede lo sviluppo di una libreria per l'utilizzo di alberi binari che implementi le seguenti funzionalita':<br>
- calcolo del numero di elementi contenuti nell'albero,<br>
- verifica della presenza di un elemento con una certa chiave,<br>
- calcolo del numero di occorrenze di una certa chiave,<br>
- recupero del puntatore a un elemento con chiave massima,<br>
- recupero del puntatore a un elemento con chiave minima,<br>
- stampa ordinata delle chiavi degli elementi dell'albero,<br>
- cancellazione di un elemento che ha una certa chiave.<br>

In particolare, si devono implementare le seguenti funzioni:<br>

<verbatim>
	int num_nodes(int_bin_tree *tree)
</verbatim>
	
La funzione ritorna il numero di nodi presenti nell'albero tree. Un albero vuoto ha zero nodi.


<verbatim>
	int contains(int_bin_tree *tree, int x)

</verbatim>
	
La funzione ritorna 1 se nell'albero tree e' presente almeno un nodo con chiave x.


<verbatim>
	int occurrences(int_bin_tree *tree, int x)
</verbatim>

La funzione ritorna il numero di elementi dell'albero tree aventi chiave x. La funzione ritorna 0 se l'albero e' vuoto.
	

<verbatim>	
	int_bin_tree* min_key(int_bin_tree *tree)
</verbatim>

La funzione ritorna il puntatore al nodo dell'albero avente chiave minima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave minima si puo' ritornare il puntatore ad uno qualsiasi di questi.

<verbatim>
	int_bin_tree* max_key(int_bin_tree *tree)
</verbatim>
	
La funzione ritorna il puntatore al nodo dell'albero avente chiave massima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave massima si puo' ritornare il puntatore ad uno qualsiasi di questi.	
	

<verbatim>	
	int * get_ordered_array(int_bin_tree *tree)
</verbatim>	

La funzione alloca un vettore di interi di dimensione pari al numero di elementi dell'albero. Il vettore deve contere le chiavi presenti nell'albero ordinate in modo crescente. Se l'albero e' vuoto la funzione ritorna NULL senza allocare nulla. 	
	

<verbatim>	
	int_bin_tree * delete(int_bin_tree *tree, int x)
</verbatim>
La funzione elimina un nodo con chiave x dall'albero, se presente. Se sono presenti piu' elementi con chiave x si puo' eliminare uno qualsiasi di questi. La funzione ritorna il puntatore alla radice dell'albero.
	
Si deve modificare    [[%ATTACHURL%/NomeCognome_hw_3_2014.1.c][QUESTO]] file riempendo il corpo delle funzioni sopra elencate. Si possono tuttavia utilizzare funzioni ausiliarie. Il main prende in input un intero a ed una sequenza di interi positivi, terminata da un numero negativo. L'intero a serve a testare diverse funzioni, come spiegato in seguito, gli altri interi letti sono invece inseriti nell'albero. La funzione di inserimento insert() e' gia' implementata e non deve essere modificata.

L'homework e' suddiviso in tre parti. Nella prima parte (a = 1) si testeranno solamente le funzioni num_nodes(), contains() e occurencies(). Nella seconda parte (a = 2) si testeranno invece le funzioni min_key(), max_key(). Nella terza parte (a = 3) si testeranno infine le funzioni get_ordered_array() e delete(). Si deve comunque consegnare un unico file con estensione .1.c. La correzione verra' poi effettuata come se si trattasse di esercizi distinti. 

*Esempio 1 (a = 1)* <br>
Si inseriscono i valori<br>
1<br>
1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
-1<br>


Il programma deve stampare:<br>
Num nodes 13<br>
contains(0) = 0 occurences(0) = 0<br>
contains(1) = 1 occurences(1) = 1<br>
contains(2) = 1 occurences(2) = 1<br>
contains(3) = 1 occurences(3) = 1<br>
contains(4) = 1 occurences(4) = 1<br>
contains(5) = 1 occurences(5) = 1<br>
contains(6) = 1 occurences(6) = 1<br>
contains(7) = 1 occurences(7) = 1<br>
contains(8) = 1 occurences(8) = 1<br>
contains(9) = 1 occurences(9) = 1<br>
contains(10) = 1 occurences(10) = 1<br>
contains(11) = 1 occurences(11) = 1<br>
contains(12) = 1 occurences(12) = 1<br>
contains(13) = 1 occurences(13) = 1<br>
contains(14) = 0 occurences(14) = 0<br>
...<br>
contains(99) = 0 occurences(99) = 0<br>


*Esempio 2 (a = 2)* <br>
Si inseriscono i valori<br>
2<br>
1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
-1<br>

Il programma deve stampare<br>
1<br>
13<br>


*Esempio 3 (a = 3)* <br>
Si inseriscono i valori<br>
3<br>
5<br>
5<br>
5<br>
5<br>
3<br>
3<br>
3<br>
5<br>
5<br>
5<br>
1<br>
1<br>
1<br>
3<br>
3<br>
5<br>
5<br>
-1<br>
	
Il programma deve stampare<br>
1 1 1 3 3 3 3 3 5 5 5 5 5 5 5 5 5 <br>
Deleting 1<br>
Num nodes 16<br>
Deleting 1<br>
Num nodes 15<br>
Deleting 1<br>
Num nodes 14<br>
Deleting 3<br>
Num nodes 13<br>
Deleting 3<br>
Num nodes 12<br>
Deleting 3<br>
Num nodes 11<br>
Deleting 3<br>
Num nodes 10<br>
Deleting 3<br>
Num nodes 9<br>
Deleting 5<br>
Num nodes 8<br>
Deleting 5<br>
Num nodes 7<br>
Deleting 5<br>
Num nodes 6<br>
Deleting 5<br>
Num nodes 5<br>
Deleting 5<br>
Num nodes 4<br>
Deleting 5<br>
Num nodes 3<br>
Deleting 5<br>
Num nodes 2<br>
Deleting 5<br>
Num nodes 1<br>
Deleting 5<br>
Num nodes 0<br>



	

---+++ <font color=black size="+1">Errori comuni</font>
<ul>
<li><b>Aggiunta di stampe</b>: non si devono aggiungere stampe ulteriori a quelle previste dall'homework. Ad esempio, se l'output previsto per un esercizio e' <verbatim>5</verbatim> ed il programma stampa <verbatim>il risultato e' 5</verbatim> l'esercizio e' considerato errato. Le funzioni di stampa sono in genere fornite con il testo dell'homework e non vanno modificate.
<li><b>Compilazione</b>: I programmi devono compilare correttamente (senza nessun messaggio di errore e senza nessun warning) sotto Linux con il compilatore gcc. <br> *Attenzione* i programmi C sono in genere compilabili in C++, ma il viceversa non è vero. Quindi *NON* utilizzare compilatori quali g++.
<li><b>Sintassi for</b>: Il C non permette la dichiarazioni di variabili all'interno dell'istruzione del ciclo for. Un istruzione del tipo: <verbatim>for(int i = 0; i < 5; i++)</verbatim> genera un errore di compilazione.
<li><b>Estensioni</b>: Nel sistema Windows le estensioni dei file sono di default nascoste. Se ad esempio si crea un file pippo.1.c, il file verrà visualizzato come pippo.1 (senza estensione .c). Se lo si rinomina come pippo.1.c, il risultato sara' un file pippo.1.c.c che non e' confonrme alle specifiche richieste. Si deve abilitare nelle opzioni cartella la visualizzazione delle estensioni di tutti i file.
</ul>

---+++ <font color=black size="+1">Homework precedenti</font>
<!--
   * [[%ATTACHURL%/hw_1_2013.txt][Homework 1]]
   * [[%ATTACHURL%/hw_2_2013.txt][Homework 2]]
-->


---+++ [[Homework anni accademici precedenti]]

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who
c	NomeCognomeHwProva2014.1.c	r1	manage	0.5 K	2014-04-01 - 18:16	SimoneSilvestri
c	NomeCognomeHwProva2014.2.c	r1	manage	0.7 K	2014-04-01 - 18:18	SimoneSilvestri
c	NomeCognomeHwProva2014.3.c	r1	manage	0.8 K	2014-04-01 - 18:19	SimoneSilvestri
c	NomeCognome_hw1_2014.1.c	r1	manage	0.3 K	2014-04-01 - 18:20	SimoneSilvestri
c	NomeCognome_hw1_2014.2.c	r1	manage	0.5 K	2014-04-01 - 18:21	SimoneSilvestri
c	NomeCognome_hw1_2014.3.c	r1	manage	1.7 K	2014-04-01 - 18:23	SimoneSilvestri
c	NomeCognome_hw_2_2014.1.c	r1	manage	0.5 K	2014-05-06 - 11:50	SimoneSilvestri
c	NomeCognome_hw_2_2014.2.c	r1	manage	0.9 K	2014-05-06 - 11:50	SimoneSilvestri
c	NomeCognome_hw_2_2014.3.c	r1	manage	1.0 K	2014-05-06 - 11:50	SimoneSilvestri
c	NomeCognome_hw_3_2014.1.c	r1	manage	2.6 K	2014-05-29 - 16:32	SimoneSilvestri
html	risultati_hw_1_2014.html	r1	manage	140.8 K	2014-05-06 - 11:21	SimoneSilvestri
html	risultati_hw_2_2014.html	r1	manage	133.1 K	2014-06-04 - 14:42	SimoneSilvestri
html	risultati_hw_3_2014.html	r1	manage	107.2 K	2014-06-23 - 15:21	SimoneSilvestri
html	risultati_hw_prova_2014.html	r1	manage	122.8 K	2014-03-28 - 19:53	SimoneSilvestri