Portail nationalFormationRechercher par discipline

Algorithm Engineering and Data Structures

Code UE : USEEU5

  • Cours
  • 6 crédits

Responsable(s)

Stefano SECCI

Public, conditions d’accès et prérequis

Basic algorithms and data structures, Programming, Basic algebra and probability.

Objectifs pédagogiques

The goal of the course is to teach students how to design and analyze advanced algorithms and data structures for the efficient solution of combinatorial problems involving high volumes of basic data types, such as integers, strings, trees, and graphs. 

Contenu

The design and analysis of advanced algorithms and data structures will involve basic data types (such as integers, strings, trees, and graphs) and several models of computation - such as RAM, 2-level memory, cache-oblivious, streaming - in order to take into account the architectural features and the memory hierarchy of modern PCs and the availability of Big Data upon which those algorithms could work on. Engineering considerations spurring from the implementation of the proposed algorithms and from experiments published in the literature will be also discussed.
 
Topics:
  • Sorting and Permuting atomic items in a disk-based setting: Multi-way mergesort, multi-way quicksort
  • Sorting strings: Multi-key quicksort, LSD-radix sort, MSD-radix sort
  • Randomised sampling in a streaming scenario
  • Hashing: universal, perfect, minimal ordered and perfect, Bloom filters
  • Randomized data structures: Treaps and skip lists
  • String data structures: Tries, Ternary search trees, Patricia Tries, Suffix arrays and suffix trees
  • Prefix- and substring-based searches over textual collections
  • Data compression: Integer codes, Elias-Fano coding, Canonical Huffman coding, Arithmetic coding, Lempel-Ziv parsing (gzip), Burrows-Wheeler Transform (bzip)

Modalité d'évaluation

Written exam

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master ROC en alternance - Mulhouse
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x)
Lieu(x)
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

EPN05 - Informatique
2 rue Conté accès 33.1.11B
75003 Paris
Tel :01 40 27 27 02
secretariat.mastersibi@cnam.fr

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé