DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Master (Laurea Magistrale) in Computer Science and Networking » Algorithm Engineering » Algorithm Engineering A.A. 2021-2022
magistraleinformaticanetworking:ae:ae2021:start

Differenze

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

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione Entrambe le parti successive la revisione
magistraleinformaticanetworking:ae:ae2021:start [23/11/2021 alle 19:20 (2 anni fa)]
Paolo Ferragina [Lectures] 		magistraleinformaticanetworking:ae:ae2021:start [24/11/2021 alle 09:06 (2 anni fa)]
Paolo Ferragina [Lectures]
Linea 91: Linea 91:
 | 23/11/2021 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n. Suffix Array construction via qsort and its asymptotic analysis. Text mining use of suffix arrays. Compressor bzip: MTF, RLE, Burrows-Wheeler Transform. | Chap. 10 of the notes: 10.1, 10.2.1 (but no page 10-4 and 10-5 and thus no Lemma 10.2), 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"), 10.4.3 and 14.1-14.3.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?web=1|Video]] and [[https://www.dropbox.com/s/m4yogpojydotw97/Lect%20SA-ST%20and%20Bwt.pptx?dl=0|slides]] | | 23/11/2021 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n. Suffix Array construction via qsort and its asymptotic analysis. Text mining use of suffix arrays. Compressor bzip: MTF, RLE, Burrows-Wheeler Transform. | Chap. 10 of the notes: 10.1, 10.2.1 (but no page 10-4 and 10-5 and thus no Lemma 10.2), 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"), 10.4.3 and 14.1-14.3.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?web=1|Video]] and [[https://www.dropbox.com/s/m4yogpojydotw97/Lect%20SA-ST%20and%20Bwt.pptx?dl=0|slides]] |
 | 23/11/2021 | Exercises | Video and notes | | 23/11/2021 | Exercises | Video and notes |
 +| 24/11/2021 | How to construct the BWT via qsort. How to invert the BWT. Exercises. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_090354-Meeting%20Recording.mp4?web=1|part 1]] and part 2.|
  
-| 00/00/2021 | How to construct the BWT via qsort. How to invert the BWT. | | 
 | 00/00/2021 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries or Patricia Trees. Analysis of space, I/Os and time of all described solutions.  | Chap. 9 of the notes: 9.1, 9.4, 9.5. No Locality Preserving front coding (9.3). | | 00/00/2021 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries or Patricia Trees. Analysis of space, I/Os and time of all described solutions.  | Chap. 9 of the notes: 9.1, 9.4, 9.5. No Locality Preserving front coding (9.3). |
    
magistraleinformaticanetworking/ae/ae2021/start.txt · Ultima modifica: 27/04/2023 alle 15:32 (12 mesi fa) da Paolo Ferragina

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki