Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Notice Board

[AVVISO] Testo dell'Homework 1 - scadenza domenica 8 aprile

andrea.sterbini (207920 points)
749 1267 2373
in Homework 1 by (208k points)
reopened by

Homework 1 - sequenza a finestra scorrevole

Data una sequenza S di N numeri interi, da questa si può ottenere una sequenza derivata Y di N-K interi sommando, per ogni indice i nell'intervallo [0 .. N-k-1], i k elementi di S agli indici j in [i .. i+k-1].

Esempio (in cui evidenzio in grassetto un valore di Y ed i k elementi che sommati lo producono):

  • k = 4
  • S =   97, 77, 51, -96,   63, 45, -23, 26, -13,   -42,    -30,   -95,    47,    -91, -12, -44, -10, 53, -31, -71
  • Y = 129, 95, 63, -11, 111, 35, -52, -59, -180, -120, -169, -151, -100, -157, -13, -32, -59

Non conoscendo a priori la lunghezza della sequenza S, non è possibile pre-allocare staticamente lo spazio di memoria necessario a memorizzarla completamente prima di calcolare la sequenza Y.

Se però si sa che k è limitato è possibile produrre la stampa della sequenza Y ricordando solo gli ultimi k elementi letti.

Scrivete il programma assembly MIPS che:

  • legge il numero intero 0 < k < 21
  • legge la sequenza S di almeno k interi diversi da 0 terminata dal valore 0 (zero, che non fa parte della sequenza)
    • mano a mano che ha informazioni sufficienti, stampa i valori della sequenza Y seguiti da accapo
  • alla fine stampa (in quest'ordine, sempre seguiti da accapo) i valori
    • minimo della sequenza S
    • massimo della sequenza S
    • minimo della sequenza Y
    • massimo della sequenza Y

I valori letti in input sono tutti valori interi seguiti da accapo in modo che li possiate leggere con la syscall 5.

Esempio di input/output:

Input: (commentato, nei test NON ci saranno commenti)

4                     # K
97
77
51
-96
63
45
-23
26
-13
-42
-30
-95
47
-91
-12
-44
-10
53
-31
-71
0                 # indica fine della sequenza S, non fa parte della sequenza

 Output atteso: (commentato, nei test NON ci saranno commenti)

129
95
63
-11
111
35
-52
-59
-180
-120
-169
-151
-100
-157
-13
-32
-59
-96             # minimo della sequenza S
97              # massimo della sequenza S
-180           # minimo della sequenza Y
129            # massimo della sequenza Y

Consegna

Il file da consegnare è il file sorgente exercise01.asm del vostro programma (meglio se commentato):

  • NON DEVE contenere stampe/prompt diverse da quelle indicate
  • DEVE iniziare la propria esecuzione dalla etichetta main
    • ricordatevi quindi di inserire la direttiva .globl main
  • DEVE terminare la sua esecuzione con la syscall 10
  • NON DEVE memorizzare nè tutta S nè tutta Y in memoria, nè con allocazione statica, nè con quella dinamica nè con la stack.
  • DEVE: stampare Y mano a mano che legge S.
  • NOTA: i compiti copiati vengono annullati

Per consegnare il file programma.asm sviluppato in Mars usate la pagina di consegna

Scadenza della consegna:  domenica 8 aprile ore 24

Per eseguire i test in locale

  • aprite una finestra di comando/console e posizionatevi nella directory in cui avete messo i file:
    • il programma exercise01.asm da voi sviluppato
    • il simulatore Mars4_5.jar
    • un file di esempio di input input.txt
    • il corrispondente file di output atteso expected.txt

eseguite in console il comando

  • java -jar Mars4_5.jar me nc sm ic exercise01.asm < input.txt > output.txt
  • in questo modo produrrete nel file output.txt le stampe del vostro programma

  • confrontate il file output.txt con il file expected.txt, se sono uguali il test è superato

File di test

K N range di valori
1 1 -1000 .. 1000
1 18 -1000 .. 1000
2 26 -1000 .. 1000
7 100 -1000 .. 1000
8 57 -1000 .. 1000
14 69 -1000 .. 1000
17 62 -1000 .. 1000
20 68 -1000 .. 1000

NOTA: ho messo pochi dati piccoli per permettervi di debuggare il codice ma farò dei test anche con N >> 1000 e con valori grandi

Premi e cotillon

Il voto di ciascun homework dà 0.5 o 1 punto (a seconda della difficoltà) da aggiungere ai voti delle prove scritte/ASM ed è composto da due parti:

  • correttezza = % di test passati * 0.5                 (da 0 a 0.5 per questo HW)
  • efficienza = +0.1 punti se siete nel primo 1/4 della classifica di efficienza di chi ha superato tutti i test

Per calcolare la classifica dell'efficienza uso il numero di istruzioni totali eseguite dal vostro programma sui test, in ordine crescente (lower = better).

PS. se qualcosa non è chiaro chiedete sotto

3.2k views

8 Answers

t
trianni.andrea (930 points)
3 8 15
by (930 points)
Prof, scusi il disturbo, non mi è chiaro quale sia il carattere di andata a capo, (uso windows)

io stampo '\n' e sulla console funziona, sui file invece non ha effetto, le chiedevo quindi quale sia il carattere giusto, anche perché penso poi i compiti verranno corretti su Linux?.
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
Usa '\n', in windows apri il file risultante con Wordpad o Word oppure con un editor di puro testo (NON con Notepad)
Sì, i test saranno fatti girare su Linux
o
orlandoalessio1998 (7730 points)
7 24 36
by (7.7k points)
edited by
prof, ho problemi con il caricamento del file.
Durante la fase di consegna mi viene rilevato l'errore di codifica UTF-8 sia che chiami il file "programma.asm" o "program.asm" sia che lo chiami "exercise01.asm", come posso risolvere?
t
trianni.andrea (930 points)
3 8 15
by (930 points)
Pure a me ha dato questo problema,
dopo qualche prova ho visto che mars mi codificava in ansi, allora con notepad ho cambiato formato in utf-8 e, dopo aver sostituito qualche carattere buggato, ho sovrascritto il file, e, prima di consegnare, ho riassemblato il tutto con mars.

(PS: Il file alla fine l' ho chiamato programma.asm)
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
Credo che dobbiate evitare di usare qualsiasi tipo di lettere accentate o caratteri strani
o
orlandoalessio1998 (7730 points)
7 24 36
by (7.7k points)
caratteri accentati, come consuetudine, non ne ho usati, i caratteri più strani che ho usato sono l'apostrofo e i trattinibassi che non penso diano fastidio
edit. Non so per quale motivo, provando a creare un nuovo file e copiando le istruzioni ho risolto il problema.
s
simone (25820 points)
47 97 209
by (25.8k points)
Per la consegna le lettere accentate non danno nessun problema. La pagina accetta tutti i contenuti codificati in UTF8.
by (9.9k points)

Salve professore, avrei alcune domande:

  1. Il range di valori per ogni elemento della sequenza S è garantito che si trovi nell'intervallo [-1000;1000] o può variare arbitrariamente entro i 32 bit?
  2. Il range di valori che può assumere k è garantito che si trovi nell'intervallo (0, 21)?
  3. Il calcolo del numero delle istruzioni viene fatto dopo che l'asseblatore sostituisca le pseudo-istruzioni in istruzioni native o prima ?
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
1) il range di valori in S è quello degli interi rappresentabili con una word
2) sì, ovvero i valori da 1 a 20 (nota che potete assumere che la sequenza S contenga almeno K elementi, e quindi Y almeno 1)
3) dopo, conta le istruzioni effettivamente eseguite (l'opzione 'ic' stampa su stderr anche il numero di istruzioni base eseguite)
4) metterò un timeout sensato su ciascun test (che ne so, 1000000 istruzioni)
by (9.9k points)
Ah ok, quindi usando l'opzione ic dobbiamo ricordarci che l'ultima linea sono le istruzioni eseguire e non fa parte del testo dell'output.
L
Lorenzo (230 points)
0 0 3
by (230 points)

quando dice 

  • mano a mano che ha informazioni sufficienti, stampa i valori della sequenza Y seguiti da accapo

intende durante la fase di inserimento?
personalmente avevo pensato di raccogliere prima l'intero input e poi di creare l'output, per ottenere un risultato più ordinato

by (9.9k points)
Devi stampare la sequenza Y mentre scansioni la sequenza S, perchè, come ha scritto il professore, userà sequenze così grandi che sicuramente manderà in crash il programma. Ovviamente tale cosa è voluta D:
by (9.9k points)
Professore, quando sarà accessibile la pagina dei risultati personali nella sezione homework? Così per vedere se i nostri programmi passano i vari test.
o
odiamadis (860 points)
1 5 13
by (860 points)
Come ci dobbiamo comportare se la lunghezza di S è minore di k? Facciamo ricominciare l'input del vettore da zero oppure lo facciamo continuare (ignorando quindi l'inserimento dello 0 che ha interrotto l'input)? Oppure (tanto improbabile quanto drastico) facciamo terminare il programma?
by (9.9k points)
È garantito che la sequenza S contenga almeno k elementi.
L
Lorenzo (230 points)
0 0 3
by (230 points)

ho completato il codice, ma ho due domande:

  1. una volta calcolati i valori di Y non è più importante conservare i valori dati in input?
  2. i test saranno tali da poter potenzialmente "riempire" lo stack?

Lo chiedo perché in tal caso mi vedrei costretto a rifinire il codice

andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
NON salvate nè S nè Y in memoria (neanche su stack).
Stampate Y MANO A MANO che leggete S.
L
LucaStravato (1360 points)
10 31 38
by (1.4k points)

Salve prof, mi chiedevo se con questo "mano a mano" intende che dobbiamo stampare appena abbiamo letto K elementi in input o in generale quando vogliamo? Nel caso del mio algoritmo stampo solo dopo avere letto K+1 interi da input memorizzando K interi in memoria(memoria pre-allocata per memorizzare al massimo k interi), un piccolo esempio sotto (max e min non ancora implementati)

in questo caso k=4
**** user input : 4

**** user input : 97
**** user input : 77
**** user input : 51
**** user input : -96
**** user input : 63
129
**** user input : 45
95
**** user input : -23
63
**** user input : 26
-11
**** user input : ...e cosi via

andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
La prima che hai detto.
gianpcr (4620 points)
5 16 34
by (4.6k points)
Salve prof, le ho inviato qualche giorno fa un messaggio privato su q2a riguardo l'homework e mi chiedevo se fosse riuscito a leggerlo poichè non ho ricevuto una risposta. Grazie in anticipo .
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)
Visto, ti ho risposto