Algoritmi e Strutture Dati II (A.A. 2014-2015)

Argomenti trattati a lezione:

• Some representative problems
  • Stable Marriage Problem (KT, 1.1)
  • Five Representative Problems (KT, 1.2)
• Algoritmi Greedy
  • Interval Scheduling (KT, 4.1)
  • Sceduling to minimize Lateness (KT, 4.2)
  • Optimal Caching (KT, 4.3)
  • Shortest Paths in a Graph (KT, 4.4)
  • The Minimum Spanning Tree Problem (KT, 4.5)
  • Implementing Kruskal's Algorithm: The Union-Find Data Structure (KT, 4.6)
  • Clustering (KT 4.7)
• Programmazione Dinamica (KT, 6)
  • Weighted Interval Scheduling (KT, 6.1)
  • Principles of Dynamic Programming: Memoization ot Iteration over Subproblems (KT 6.2)
  • Segmented Least Squares: Multi-way Choice (KT, 6.3)
  • Subset Sum and (0/1) Knapsack (KT 6.4)
  • Integer (unbounded) Knapsack
  • RNA Secondary structure (KT 6.5)
  • Sequence Alignment (KT 6.6)
  • Shortest path in a graph (KT 6.8)
• NP and Computational Intractability
  • Polynomial-time reductions (KT 8.1)
  • Reduction via "Gadgets" (KT 6.2)
  • Efficient certification and the Definition of NP (KT 8.3)
  • NP-Complete Problems (KT 6.4)
• Approximation Algorithms
  • Greedy algorithms and bounds on the optimum: A load balancing problem (KT 11.1)
  • The Center Selection Problem (KT 11.2)
  • The Pricing Method: Vertex Cover (KT 11.4)
  • Linear Programming and Rouding: An Application to Vertex Cover (KT 11.6)
• Randomized Algorithms
  • A first approach: Contention resolution (KT 13.1)
  • Finding the Global Minimum Cut (KT 13.2)
  • Random Variables and their Expectations (KT 13.3)
  • A Randomized approximation algorithm for MAX 3-SAT (KT 13.4)
  • Chernoff Bound (KT 13.9)
  • Load Balancing (KT 13.10)

---