magistraleinformatica:ad:ad_17: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:ad:ad_17:start [27/12/2017 alle 16:04 (7 anni fa)] – [Topics] Roberto Grossi | magistraleinformatica:ad:ad_17:start [03/09/2018 alle 22:02 (7 anni fa)] (versione attuale) – [Schedule] Roberto Grossi | ||
---|---|---|---|
Linea 11: | Linea 11: | ||
==== Schedule ==== | ==== Schedule ==== | ||
+ | * Regarding your exam planning: I'll be on leave during 19.09.18-15.10.18 and 01.11.2018-28.02.19. | ||
* Timetable: [[https:// | * Timetable: [[https:// | ||
* Office hours: Thu. 14-17 or by appointment. | * Office hours: Thu. 14-17 or by appointment. | ||
- | |||
==== Overview ==== | ==== Overview ==== | ||
Linea 20: | Linea 20: | ||
==== Exams ==== | ==== Exams ==== | ||
- | Written exam: | + | //Written exam:// |
- choose one of the topics discussed in class | - choose one of the topics discussed in class | ||
- write a very short to-do list and ask the instructor for approval | - write a very short to-do list and ask the instructor for approval | ||
Linea 30: | Linea 30: | ||
Suggested reading: [[http:// | Suggested reading: [[http:// | ||
+ | |||
+ | Example of interaction: | ||
- | Oral examination: topics discussed in class, please read the references in the notes. | + | //Oral exam:// topics discussed in class, please read the references in the notes. |
==== Topics ==== | ==== Topics ==== | ||
Linea 82: | Linea 84: | ||
|23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). | |23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP). | ||
|27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https:// | |27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https:// | ||
- | |28.11.2017| Non-existence of PTAS. Local search. Greedy. Case study: max-cut for graphs. | TBD | | + | |28.11.2017| Non-existence of PTAS. Local search. Greedy. Case study: max cut for graphs. | {{: |
- | |30.11.2017| Randomized approximation. Derandomization: | + | |30.11.2017| Randomized approximation. Derandomization: |
|04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https:// | |04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https:// | ||
- | |05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. | + | |05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. |
- | |07.12.2017| Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | TBD | | + | |07.12.2017| Randomized FPT algorithms: color coding and randomized separation. Case study: longest path in graphs and subgraph isomorphism. | [[https:// |
- | |12.12.2017| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | TBD | | + | |11.12.2017| Class canceled for weather alert. | - | |
+ | |12.12.2017| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | [[https:// | ||
|14.12.2017| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. Case study: communities detection in large graphs.| {{ : | |14.12.2017| Approximation in fine-grained algorithms and limitations. Case study: diameter in undirected unweighted graphs. Case study: communities detection in large graphs.| {{ : | ||
magistraleinformatica/ad/ad_17/start.1514390664.txt.gz · Ultima modifica: 27/12/2017 alle 16:04 (7 anni fa) da Roberto Grossi