Strumenti Utente

Strumenti Sito


magistraleinformatica:ad:ad_17: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 revisioneRevisione precedente
Prossima revisione
Revisione precedente
magistraleinformatica:ad:ad_17:start [27/12/2017 alle 16:16 (7 anni fa)] Roberto Grossimagistraleinformatica: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://www.di.unipi.it/en/education/mcs/timetable-wif/myschedule-wif?courses%5B%5D=58926_u&cds=WIF-LM&dip=Informatica&test=10&sem=1&anno=2017#|weekly timetable]] with changes: (Oct.5 -> Oct.4, 14-16, I-Lab); (Oct.9 -> Oct.2, 14-16, room A1); (Oct.10 -> Oct.23, 14-16, room A1).   * Timetable: [[https://www.di.unipi.it/en/education/mcs/timetable-wif/myschedule-wif?courses%5B%5D=58926_u&cds=WIF-LM&dip=Informatica&test=10&sem=1&anno=2017#|weekly timetable]] with changes: (Oct.5 -> Oct.4, 14-16, I-Lab); (Oct.9 -> Oct.2, 14-16, room A1); (Oct.10 -> Oct.23, 14-16, room A1).
   * 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://www.ittc.ku.edu/~jsv/Papers/Vitwritingnotes.pdf|some useful tips for scientific writing in English]] (first two sections) by J.S. Vitter. Suggested reading: [[http://www.ittc.ku.edu/~jsv/Papers/Vitwritingnotes.pdf|some useful tips for scientific writing in English]] (first two sections) by J.S. Vitter.
 +
 +Example of interaction: [[.interaction:|student and instructor]] discussing the report's content and structure.
  
  
-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).  2-approximation algorithm . | [CLRS 35.2] | |23.11.2017| General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithm . | [CLRS 35.2] |
 |27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https://www.dropbox.com/s/mvomtclqs97vx26/27-11.pdf?dl=0|slides]] [[https://www.dropbox.com/s/aeowxkt6p8iximx/chapter2.pdf?dl=0|notes]] | |27.11.2017| Case study on approximation for metric k-center: Clustering and video summarization. | [[https://www.dropbox.com/s/mvomtclqs97vx26/27-11.pdf?dl=0|slides]] [[https://www.dropbox.com/s/aeowxkt6p8iximx/chapter2.pdf?dl=0|notes]] |
-|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. | {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} 
-|30.11.2017| Randomized approximation. Derandomization: universal hash functions; conditional expectations. Case study: max-cut for graphs. | TBD |+|30.11.2017| Randomized approximation. Derandomization: universal hash functions; conditional expectations. Case study: max-cut for graphs. | [[http://pages.cs.wisc.edu/~jyc/02-810notes/lecture19.pdf|sect. 3-4]] [[http://web.cs.iastate.edu/~pavan/633/lec14.pdf|sect. 1.1]] |
 |04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https://tinyurl.com/yak7p2w7|paper]] | |04.12.2017| Case study on approximation for graphs (max cut): single individual haplotypes reconstruction problem (hapcut) |[[https://tinyurl.com/yak7p2w7|paper]] |
-|05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. TBD +|05.12.2017| Fixed-parameter tractable (FPT) algorithms. Kernelization. Bounded search tree. Case study: min-vertex cover in graphs. [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 2.2.1, 3.1]] 
-|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://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 5.2, 5.3]] |
 |11.12.2017| Class canceled for weather alert. | - |  |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. | TBD |+|12.12.2017| Fine-grained algorithms. SETH conjecture and conditional lower bounds. Guaranteed heuristics. Case study: diameter in undirected unweighted graphs. | [[https://www.dropbox.com/s/zq0dklabkjyd302/20171212.pdf?dl=0|notes]] [[https://people.csail.mit.edu/virgi/ipec-survey.pdf|sect. 2.3, 2.4, 3, 4]]|
 |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:diameterapprox.pdf | notes }} [[https://www.nature.com/articles/nature03607.pdf|paper]] [[https://images.nature.com/original/nature-assets/nature/journal/v435/n7043/extref/nature03607-s1.pdf|supplement]] | |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:diameterapprox.pdf | notes }} [[https://www.nature.com/articles/nature03607.pdf|paper]] [[https://images.nature.com/original/nature-assets/nature/journal/v435/n7043/extref/nature03607-s1.pdf|supplement]] |
  
magistraleinformatica/ad/ad_17/start.1514391401.txt.gz · Ultima modifica: 27/12/2017 alle 16:16 (7 anni fa) da Roberto Grossi

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki