magistraleinformatica:alg2:algo2_16:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
| magistraleinformatica:alg2:algo2_16:start [01/12/2016 alle 16:57 (9 anni fa)] – Roberto Grossi | magistraleinformatica:alg2:algo2_16:start [14/01/2017 alle 23:07 (9 anni fa)] (versione attuale) – [Announcements] Roberto Grossi | ||
|---|---|---|---|
| Linea 4: | Linea 4: | ||
| ==== Announcements ==== | ==== Announcements ==== | ||
| - | * Question time: Fri. Dec. 16, 2016, at 9:00-13:00 in room N1 (aula N1). | + | * Exams -- written part: [[.results_2016: |
| - | * Final test (verifica) on Dec. 20, 2016, at 11:00-13:00 in room C1 (aula C1), please register. | + | * The {{: |
| - | * Office hours: Thu. 14-18 (in my room at the Dipartimento di Informatica) | + | * First meeting for oral exam calendar: Jan. 16, 2016 at 9:00 in office (room 342 DN). |
| + | * Second meeting for oral exam calendar: Feb. 13, 2016 at 9:00 in office (room 342 DN). | ||
| + | * Office hours: Thu. 14-18 (in my room at the Dipartimento di Informatica) | ||
| ==== Overview ==== | ==== Overview ==== | ||
| Linea 20: | Linea 22: | ||
| Please note that several topics are the outcome of recent advancement in algorithms and data structures, and thus most of the course material consists in research papers or book chapters. | Please note that several topics are the outcome of recent advancement in algorithms and data structures, and thus most of the course material consists in research papers or book chapters. | ||
| - | |||
| - | ^ Date ^ Topics ^ References and notes ^ | ||
| - | | Sept. 21| Introduction to the course. Entrance exam. | - | | ||
| === Warming up === | === Warming up === | ||
| Linea 31: | Linea 30: | ||
| ^ Date ^ Topics ^ References and notes ^ | ^ Date ^ Topics ^ References and notes ^ | ||
| + | | Sept. 21| Introduction to the course. Entrance exam. | - | | ||
| | Sept. 22| Graphs representations. BFS. Dijkstra algorithm for SSSP. Problem " | | Sept. 22| Graphs representations. BFS. Dijkstra algorithm for SSSP. Problem " | ||
| | Sept. 27| Problem solving: " | | Sept. 27| Problem solving: " | ||
| Linea 71: | Linea 71: | ||
| | Nov. 23| External memory model (EMM) a.k.a. cache-aware model vs cache-oblivious model: I/O complexity, sequential access versus random access. Searching (part I). | [[http:// | | Nov. 23| External memory model (EMM) a.k.a. cache-aware model vs cache-oblivious model: I/O complexity, sequential access versus random access. Searching (part I). | [[http:// | ||
| | Nov. 24| External memory model and cache-oblivious model: searching (part II) and van EmdeBoas layout. | [[http:// | | Nov. 24| External memory model and cache-oblivious model: searching (part II) and van EmdeBoas layout. | [[http:// | ||
| - | | Nov. 25| Problem solving: search and range queries in implicit search tree and van Embe Boas layout. | {{: | + | | Nov. 29| Problem solving: search and range queries in implicit search tree and van Embe Boas layout. | {{: |
| - | | Nov. 30| External memory k-way merge sort. DC3 suffix sort (part I). | [[http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf|Introduction, | + | | Nov. 30| External memory k-way merge sort. DC3 suffix sort (part I). |[[http://people.cs.aau.dk/~simas/aalg04/esort.pdf|notes]] [[http://www.cs.helsinki.fi/u/tpkarkka/publications/ |
| - | | Dec. 1 | DC3 suffix sort (part II). Review of P and NP classes. || | + | | Dec. 1 | DC3 suffix sort (part II). Review of P and NP classes. | [[http:// |
| | Dec. 6 | Problem solving: external memory k-way merge, permuting and suffix sorting. | {{: | | Dec. 6 | Problem solving: external memory k-way merge, permuting and suffix sorting. | {{: | ||
| + | |||
| === Enumeration, | === Enumeration, | ||
| Linea 81: | Linea 82: | ||
| ^ Date ^ Topics ^ References and notes ^ | ^ Date ^ Topics ^ References and notes ^ | ||
| - | | | | | | + | | Dec. 7 | Approximations algorithms. Inapproximability of general TSP. 2-approximation for metric TSP. | [CLRS preamble, 35.2] | |
| + | | Dec. 13 | 2-approximation for min-vertex cover and max cut. | [CLRS 35.1] {{: | ||
| + | | Dec. 14 | Problem solving: greedy strategy for min vertex cover and weighted max cut. | {{: | ||
| + | | Dec. 15 | Approximation algorithms for bin-packing and knapsack problems. | [[http:// | ||
| + | | Dec. 16 | Question time | - | | ||
| == Activity in class == | == Activity in class == | ||
magistraleinformatica/alg2/algo2_16/start.1480611471.txt.gz · Ultima modifica: 01/12/2016 alle 16:57 (9 anni fa) da Roberto Grossi