Materiale di studio per il corso di Algortimi Avanzati del Corso di Laurea Magistrale in Informatica presso l'Università di Modena e Reggio Emilia, A.A. 2016/17.

1. T.H. Cormen, C.E. Leoserson, R.L. Rivest, C. Stein, Introduction to Algorithms , Mc-Graw Hill, II o III Edizione
2. S. DAsgupta, C.H. Papadimitriu, U.V. Vazirani, Algorithms, Science Engineering & Math, 2011.
3. J. Kleinberg and E. Tardos, Algorithm Design, PEARSON Addison-Wesley, 2006
4. Nancy A. Lynch, Distributed Systems Morgan Kaufmann Publishers, Inc.

• Fondamenti di Algoritmi :
  • "Introduction to Algorithms": Cap 1 + Cap 3
• Teoria della Complessità :
  • "Introduction to Algorithms" Cap 34: Intorduzione + Sezioni: 34.1, 34.2, 34.3 (fino a "Circuit satisfability" ESCLUSO), 34.4 (fino a "Teorema 34.9" ESCLUSO).
  • Nozioni introduttive di complessità computazionale (lucidi in formato pdf, 414K).
  • "Riassunto" e Riduzione di Karp in pdf (*) ATTENZIONE rimosso dal sito - per informazioni contattare il docente
• Riduzioni (del materiale indicato interessa SOLO la parte relativa alla riduzione):
  • 3SAT, Independent Set, Vertex Cover:
    • "Algorithms" in sezione 8.3 ("The reductions" nel capitolo "NP-Complete problems")
    • Alternativa in pdf (rimosso dal sito - è il file (*))
  • Ciclo Hamiltoniano, Commesso Viaggiatore, Subset-sum: "Introduction to Algorithms" Sezioni: 34.5.3 - 34.5.4 - 34.5.5
  • Integer Kanpsack in pdf
  • Partitioning in pdf
  • Bin Packing in pdf (**) ATTENZIONE rimosso dal sito - per informazioni contattare il docente
  • Integer Linear Programming in pdf (rimosso dal sito - è il file (*))
• Algoritmi di Approssimazione:
  • Vertex Cover: note lezione Prof. Chakrabarti, Dartmouth College ( pdf ).
  • Set Cover: Cap 11.3 in "Algorithm Design".
  • Vertex Cover e Set Cover: note lezione Prof. Suri, Università della California ( txt )
  • Problema del Commesso Viaggiatore (TSP):
    • note lezione Prof. Chekuri, Università dell'Illinois ( pdf ): SEZIONE 1.1.
    • Cap 2 in "Plotkin, Optimization Paradigms" ( pdf ).
  • Problema dello zaino (Knapsack problem): note lezione Prof. Lap Chi Lau della Chinese University ad Hong Kong ( pdf ).
  • Bin Packing:
    • note lezione Prof. Albers e Dr. Souza della Humboldt Univesitat a Berlino ( pdf ) - SEZIONE 10.3 esclusa.
    (rimosso dal sito - è il file (**))
    • note lezione Prof. Subhash Suri dell'Università di California ( txt ): SEZIONE 11 SOLO per studenti di INFORMATCA che hanno seguito il corso di "Algortimi di Approssimazione" come libera scelta durtante la triennale.
  • Load Balancing e Bin Packing: note lezione Prof. Chekuri Università dell'Illinois ( pdf ): SEZIONI 1.1 - 1.2 - 2.1 - 2.1
• Algoritmi di approssimazione utilizzando la tecnica del rilassamento della formulazione ILP (Integer Linear Programming) del problema:
  • Vertex Cover Pesato e Load Balancing con vincoli sull'assegnamento dei job alle macchine: SEZIONI 11.6 e 11.7 di "Algorithm Design".
  • Vertex Cover Pesato (alternativa) e Set Cover deterministico e randomizzato in Cap 8 di pdf.
• Local search :
  • Introduzione alla tecnica, Vertex Cover e Max-Cut : SEZIONI 12.1 e 12.4 di "Algorithm Design".
  • 2-opt per TSP: in pdf SEZIONE 4.2, oppure in pdf SEZIONE 5.
• Branch and Bound (B&B):
  • Tecnica B&B ed esempio di applicazione a TSP (con calcolo del Lower Bound utilizzando 1-tree): in pdf SEZIONI 1 e 2.
• Algortimi Randomizzati:
  • Semplici esempi di algortimi di tipo Monte Carlo (Majoiry Element, Verifying polynomial identities) e Las Vegas (Trovare il numero ripetuto n/2 volte, 8 Queens)
  • Algortimo per Contention Resolution (symmetry breaking): SEZIONE 13.1 di "Algorithm Design".
  • Calcolo della mediana: in SEZIONE 13.5 di "Algorithm Design".
  • Randomized Quicksort in pdf SEZIONE 1.1
  • MAX-SAT:
    • Approssimazione con assegnamento random in pdf in SEZIONE 5.2
    • Approssimazione via rilassamento ILP + composizione dei due algortimi di approssimazione in pdf in SEZIONE 6.1.3 e SOLO ALGORITMO 4 E ENUNCIATO TEOREMA 2 IN SEZIONE 6.1.4.
    • Derandomizzazione in pdf SEZIONE 5.1.2
  • Caching Problem (off-line e on-line): LRU, marking algortihms e randomizzazione in pdf (NO Proof of Claim 20.3.2) e in pdf PROVA Theorem 1 pag 5-6 ( ATTENZIONE: la divisione in fasi della sequeza di richieste nell'esempio e' SBAGLIATA).
  • Breve discussione sul problema di generare numeri realemnte casuali
• Interactive Proofs:
  • Graph non Isomorfism in pdf SEZIONE 1
  • Zero-knowledge Proofs e Graph Isomorfism in pdf SEZIONE 2 e in pdf SEZIONE 1.
    Spiegazione informale del concetto di prova zero-knowledge si puo' trovare in pdf .
  • Problema dell'identificazione: schema con firma digitale in pdf; protocollo FIat-Shamir pdf SEZIONE 2.
• Sistemi Distribuiti
  • Introduzione e modelli in "Distributed Systems": Sezioni 1.1 - 1.2 - 2.1 - 2.2 - 2.3 - 2.6.
  • Problema della Leader Election:
    • Algoritmi LCR e HS per ring e impossibiltà di elezione in ring anonimi in pdf , anche in ps , anche in "Distributed Systems" sezioni 3.1 - 3.2 - 3.3 - 3.4 - 3.5 (trascurando la formalizzazione degli algortimi).
    • Itai-Rodeh algoritmo randomizzato per ring in pdf slide 29-32 e ps
    • Leader Election in general network, algortimo FloodMax in "Distributed Systems" sezione 4.1 (trascurando la formalizzazione degli algortimi).