Strumenti Utente
magistraleinformatica:alg2:algo2_13:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisione Revisione precedente Prossima revisione | Revisione precedente Ultima revisione Entrambe le parti successive la revisione | ||
|
magistraleinformatica:alg2:algo2_13:start [13/12/2013 alle 08:09 (10 anni fa)] Roberto Grossi [Topics] |
magistraleinformatica:alg2:algo2_13:start [08/02/2014 alle 13:57 (10 anni fa)] Roberto Grossi [Announcements] |
||
|---|---|---|---|
| Linea 4: | Linea 4: | ||
| ==== Announcements ==== | ==== Announcements ==== | ||
| - | * The {{: | + | |
| + | | ||
| * The class lectures will be (mainly) given in English. | * The class lectures will be (mainly) given in English. | ||
| * Office hours: Thu 11-14 (Dipartimento di Informatica) | * Office hours: Thu 11-14 (Dipartimento di Informatica) | ||
| Linea 30: | Linea 31: | ||
| === Enumeration, | === Enumeration, | ||
| - | NP-hard problems are important but difficult to solve and no deterministic polynomial algorithms are currently known for them. Even basic problems, such as finding a simple path of vertices in a graph, are NP-hard. We discuss how to attack these problems (a) by counting and listing their solutions where the cost is proportional to the output (it can be exponential in the worst case but we only pay for what we get) and (b) by approximating their solutions when the problem requires to minimize a cost or maximize a benefit. Most of the addressed problems are on graphs, which are popular representations for modern networked data. | + | NP-hard problems are important but difficult to solve and no deterministic polynomial algorithms are currently known for them. Even basic problems, such as finding a simple path of vertices in a graph, are NP-hard. We discuss how to attack these problems (a) by counting and listing their solutions where the cost is proportional to the output (it can be exponential in the worst case but we only pay for what we get) and (b) by approximating their solutions |
| ^ Date ^ Topics ^ References and notes ^ | ^ Date ^ Topics ^ References and notes ^ | ||
| Linea 75: | Linea 76: | ||
| | Dec. 10| Cache-oblivious (CO) model. Ideal cache. Motivations and simple examples: multiple scanning, inverting an array. van Emde Boas (vEB) layout of complete binary (search) trees. | [[http:// | | Dec. 10| Cache-oblivious (CO) model. Ideal cache. Motivations and simple examples: multiple scanning, inverting an array. van Emde Boas (vEB) layout of complete binary (search) trees. | [[http:// | ||
| | Dec. 11| Problem solving. Filling the details of the DC3 suffix sorting. Suffix array searching. Implicit van Emde Boas layout of binary complete search trees. | {{: | | Dec. 11| Problem solving. Filling the details of the DC3 suffix sorting. Suffix array searching. Implicit van Emde Boas layout of binary complete search trees. | {{: | ||
| - | | Dec. 12| Text indexing and searching: suffix trees and inverted lists. | [[http:// | + | | Dec. 12| Text indexing and searching: suffix trees and inverted lists. | [[http:// |
| - | | Dec. 17| Text compression: | + | | Dec. 17| Text compression: |
| Linea 82: | Linea 83: | ||
| == Excercises discussed in class == | == Excercises discussed in class == | ||
| - | This is a {{: | + | This is the {{: |
| == Official class docs (registro) == | == Official class docs (registro) == | ||
| Linea 89: | Linea 90: | ||
| * Access to the [[https:// | * Access to the [[https:// | ||
| - | == Examination outcomes == | + | == Examination outcomes |
| - | After Dec.19... | + | Risultati del 19.12.2013 |
| + | |||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | |||
| + | Risultati del 20.01.2014 | ||
| + | |||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | |||
| + | Risultati del 07.02.2014 | ||
| + | |||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
magistraleinformatica/alg2/algo2_13/start.txt · Ultima modifica: 04/10/2015 alle 10:06 (9 anni fa) da Roberto Grossi
Strumenti Pagina
