Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- biss2010:start [21/02/2010 alle 12:19 (16 anni fa)] – Paolo Ferragina
+++ biss2010:start [10/03/2010 alle 18:22 (16 anni fa)] (versione attuale) – Paolo Ferragina
@@ Linea 10: / Linea 10: @@
 Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces basic and sophisticated algorithmic solutions aimed at minimizing the use of computational resources like time, space, communication, I/O, energy consumption, etc.. The theoretical investigation will go hand-in-hand with some algorithm-engineering considerations.
 ===== Lectures: topics and material =====
-**Lecture 1.** Introduction to (Modern) Computational Models. Sorting vs Permuting. [slides, {{:biss2010:lect1-sorting.zip|material}}]
+**Lecture 1.** Introduction to (Modern) Computational Models. Sorting vs Permuting. [{{:biss2010:ferragina-biss-day1.zip|slides}}, {{:biss2010:lect1-sorting.zip|material}}]
-**Lecture 2.** Hashing: Uniform, Universal, Perfect, Cuckoo, Bloom Filters. [slides, {{:biss2010:lect2-hash.zip|material}}]
+**Lecture 2.** Hashing: Uniform, Universal, Perfect, Cuckoo. [{{:biss2010:ferragina-biss-day2a.zip|slides}}, {{:biss2010:lect2-hash.zip|material}}]
-**Lecture 3.** Dictionaries: From arrays to (Patricia) tries, from plain storage to (Locality Preserving) Front Coding. [slides, {{:biss2010:lect3-trie.zip|material}}]
+**Lecture 3.** Dictionaries: From arrays to (Patricia) tries and Bloom Filters, from plain storage to (Locality Preserving) Front Coding. [{{:biss2010:ferragina-biss-day3.zip|slides}}, {{:biss2010:lect3-trie.zip|material}}]
-**Lecture 4.** Text indexing and mining: suffix trees and arrays. Some mining queries, and the issue "LCA=RMQ". [slides, {{:biss2010:lect4-suffixtreesuffixarray.zip|material}}]
+**Lecture 4.** Text indexing and mining: suffix trees and arrays. Some mining queries, and the issue "LCA=RMQ". [{{:biss2010:ferragina-biss-day4.zip|slides}}, {{:biss2010:lect4-suffixtreesuffixarray.zip|material}}]
+**Lecture 5.** Data compression: basics, Huffman, Arithmetic, bzip2 and beyond. [{{:biss2010:ferragina-biss-day5.zip|slides}}, {{:biss2010:lect5-compression.zip|material}}]
-**Lecture 5.** Data compression: basics, Huffman, Arithmetic, bzip2 and beyond. [slides, {{:biss2010:lect5-compression.zip|material}}]
 ===== Exam =====
@@ Linea 32: / Linea 32: @@
   * Problem posed by Chakrabharti [inspiring papers? {{:biss2010:chakrabhartisearch1.pdf|one}}, {{:biss2010:chakrabhartisearch2.pdf|two}}]
   * Permuting Web pages to improve compression ratio [inspiring papers? {{:biss2010:wsdm022-ferragina.pdf|one}}, {{:biss2010:clusteringtext.pdf|two}}, {{:biss2010:suelwww2010reorder.pdf|three}}, {{:biss2010:ferraginawebcompression.tgz|software}}, [[http://brie.di.unipi.it/_UKOriginal1Gb.warc.bz2|UK-crawl]], [[http://brie.di.unipi.it/_UKURLsorted1Gb.warc.bz2|UK-URLsort]]]
-  * Generalised BWT [inspiring papers? {{:biss2010:generalisedbwt.pdf|one}}]
+  * Generalised BWT [inspiring papers? {{:biss2010:generalisedbwt.pdf|one}}, [[http://people.unipmn.it/manzini/bwtdisk/|sparring partner]], [[http://brie.di.unipi.it/_UKOriginal1Gb.warc.bz2|UK-crawl]],]
   * Temporal data mining on a DB of cars [ [[http://brie.di.unipi.it/autoscout24.tgz|dataset]] ]
-  * Smart compression:
-      * Variable-block size depending on the number of phrases ({{:biss2010:lect3-lpfc.pdf|paper}}, [[http://www.zlib.net/|gzip]])
-      * Fix a bound on Compression-ratio, minimize the number of phrases (hence decompression time).
-      * Fix a bound on Decompression-time, minimize the compression ratio.
-  * Energy-aware algorithms: examples of inefficient algorithms which use less battery!
-===== List of Students =====
-These are the students who attended the course:
-  - aa
-  - aa
-  -