Corso di Algoritmica A.A. 2019/20 - Laboratorio

Questa repository contiene materiale utile per (principalmente la parte di laboratorio del) corso di Algoritmica dell'Università di Pisa.

(!) Tutti i file qui presenti possono essere portati stampati all'esame di laboratorio.

Sono presenti alcuni esercizi interessanti svolti più altre risorse utili per apprendere e padroneggiare al meglio gli algoritmi e la loro implementazione C.
Le cartelle Lezione* contengono alcuni esercizi significativi svolti dal portale degli esercizi di laboratorio.

Tutti i codici sono compilabili con il solo gcc senza bisogno di altri tool o IDE.

Temi d'Esame ed Esercizi Svolti

Nella cartella principale del repository ci sono alcuni file in formato PDF che contengono circa 40 esercizi svolti e commentati del modulo di teoria (suddivisi in prima parte, che comprende tutti gli algoritmi di ordinamento, e seconda parte, dall'hashing fino alla fine del corso). Inoltre sono presenti le soluzioni in pseudocodice di alcuni esami di laboratorio, volti a favorire una migliore comprensione della loro implementazione che a sua volta si trova nella cartella Esami Svolti.

Algoritmi Base

La cartella Algoritmi Base contiene la trascrizione C di molti degli pseudocodici visti a lezione. Si consiglia di leggere tutti i commenti presenti nel codice per una migliore comprensione di tutti i dettagli e scelte implementative.

Sorting

Per gli algoritmi di Sorting sono forniti anche tre file .txt per testarli su esempi grandi e provare le diverse complessità in tempo al caso medio, ottimo e pessimo (quando queste sono diverse tra loro). Questi file contengono

• Una permutazione casuale degli interi in [1, 100000] (file input_shuffled.txt)
• Gli interi in [1, 100000] già ordinati (file input_sorted.txt)
• Gli interi in [1, 100000] ordinati al contrario (file input_reversed.txt)

Per eseguirli con gli input da file, utilizzate ./programma < nome_del_file. Per cronometrarne l'esecuzione usate time ./programma < nome_del_file.

Liste ed Hashing

Per le Tabelle Hash forniamo due librerie che contengono le implementazioni sia della variante con liste di trabocco (chained_hash) sia della variante ad indirizzamento aperto (open_hash).

Per le Liste forniamo una libreria che contiene l'implementazione delle operazioni di base su liste monodirezionali.

Per poter utilizzare queste librerie nei vostri esercizi:

1. Includere il file .h desiderato nel file del proprio esercizio con #include "nome_file.h"
2. Compilare il proprio esercizio con gcc -Wall -pedantic vostro_esercizio.c file_di_libreria.c -o vostro_esercizio.

Contatti:

• [email protected]
• [email protected]
• andrealisi.12lj [chiocciola] gmail [punto] com: Profilo Github, 🦆 Pagina personale
• [email protected]

A cura di Chiara B., Andrea L., Nicolas M., Davide R.