DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algorithm Design » Year 2019-2020
magistraleinformatica:ad:ad_19: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 revisione Revisione precedente
Prossima revisione 		Revisione precedente
magistraleinformatica:ad:ad_19:start [12/05/2020 alle 06:45 (4 anni fa)]
Roberto Grossi 		magistraleinformatica:ad:ad_19:start [07/07/2020 alle 07:59 (4 anni fa)] (versione attuale)
Roberto Grossi
Linea 11: Linea 11:
 You student, what can you do next for getting a lecture?  You student, what can you do next for getting a lecture? 
  
-  - Join the class on **Google Classroom** (use Android/iOS or connect to the [[https://classroom.google.com/u/1/c/NjI0NjI4NjExNzRa|Algorithm Design link]]), and use the code below: {{:magistraleinformatica:ad:ad_19:code.jpg?400|}}\\ \\  +  - Join the class on Google Classroom (use Android/iOS or connect to the [[https://classroom.google.com/u/1/c/NjI0NjI4NjExNzRa|Algorithm Design link]]).  
   - Click on the link for streaming on [[https://meet.google.com/rco-fojo-cqn|Google Meet]] for attending the classes. Please note that we //keep our schedule for time//, the only difference is that you have connect to the link instead of physically coming to the room.   - Click on the link for streaming on [[https://meet.google.com/rco-fojo-cqn|Google Meet]] for attending the classes. Please note that we //keep our schedule for time//, the only difference is that you have connect to the link instead of physically coming to the room.
  
Linea 83: Linea 83:
 |24.04.2020| NP-hard problems: download file manager and the knapsack problem. Reduction from Partition to Knapsack (restriction). Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples. | {{ :magistraleinformatica:ad:ad_17:partition-knapsack.pdf | PDF}}  [[https://repl.it/@grossiroberto/knapsack|code]] | |24.04.2020| NP-hard problems: download file manager and the knapsack problem. Reduction from Partition to Knapsack (restriction). Dynamic programming algorithms for Knapsack: Case 1: integer weights, complexity O(nW). Case 2: integer values, complexity O(n<sup>2</sup>vmax). Examples. | {{ :magistraleinformatica:ad:ad_17:partition-knapsack.pdf | PDF}}  [[https://repl.it/@grossiroberto/knapsack|code]] |
 |28.04.2019| NP-hard problems: heuristics based on dynamic programming; approximation algorithms. Case study: knapsack problem. | [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| chapt.2: par. 2.1.1]] [[https://repl.it/@grossiroberto/knapsack|code]]  | |28.04.2019| NP-hard problems: heuristics based on dynamic programming; approximation algorithms. Case study: knapsack problem. | [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/book/chapter02.pdf| chapt.2: par. 2.1.1]] [[https://repl.it/@grossiroberto/knapsack|code]]  |
- +|30.04.2019| Clique-based social network analysis (seminar by F.Geraci) | classroom drive |
-30 +
 |05.05.2020| NP-hard problems: counting version (#P) based on dynamic programming, uniform random sampling of the feasible solutions. Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |05.05.2020| NP-hard problems: counting version (#P) based on dynamic programming, uniform random sampling of the feasible solutions. Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] |
 |07.05.2020| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] | |07.05.2020| NP-hard problems: fully polynomial-time randomized approximation schemes (FPRASs). Case study: #knapsack problem. | {{ :magistraleinformatica:ad:ad_17:notesknapsack2.pdf |notes}} [[https://repl.it/@grossiroberto/ApproxKnapsack|code]] |
 |12.05.2020| General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithms for metric TSP, Local search. Greedy. Case study: max cut for graphs. Non-existence of PTAS. | [CLRS 35.2] {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} | |12.05.2020| General inapproximability results. Case study: travel salesman problem (TSP).  2-approximation algorithms for metric TSP, Local search. Greedy. Case study: max cut for graphs. Non-existence of PTAS. | [CLRS 35.2] {{:magistraleinformatica:alg2:algo2_14:lec02.pdf|Notes}} |
 |14.05.2020| Randomized approximation and 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]] | |14.05.2020| Randomized approximation and 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]] |
-|15.05.2020| Case study on bottom-k sketches: approximate similarity searching | {{ :magistraleinformatica:ad:ad_18:06691730.pdf |}} {{ :magistraleinformatica:ad:ad_18:p371-thorup.pdf | only Sect.1}} {{ :magistraleinformatica:ad:ad_18:bio.pdf |}}| +|15.05.2020| 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]] | 
-|19.05.2020| 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]] | +|19.05.2020| 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]] |
-|21.05.2020| 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]] |+
  
  
magistraleinformatica/ad/ad_19/start.1589265948.txt.gz · Ultima modifica: 12/05/2020 alle 06:45 (4 anni fa) da Roberto Grossi

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki