Week #06
	Pedro Ribeiro - DCC/FCUP

Main learning outcomes for this class

1. Dynamic Programming (DP) Concepts:
   • I know the minimax principle for games and how to use DP for solving simple game problems.
   • I know the linear partitions problem and how to use DP to obtain optimal partitions.
   • I know the concept of DAGs and how to use DP to solve problems in DAGs.
   • I know the concept of bitmasks and how to use them in DP states; I know the TSP problem and how to solve in O(n^2 2^n) using DP and bitmasks.
   • I know the concept of counting with DP

Study Material

Main references

• Lecture (given by Duarte Nóbrega):
  • Slides
  • Code: bachets.cpp | bakery.cpp | codigos_preguicosos.cpp | counting.cpp | independent_set.cpp | longest_path.cpp | pokemons.cpp | removal.cpp
• Topics:
  • Games and minimax principle
  • Algorithm Games (TopCoder)
  • Game Theory (PG Wiki)
  • Linear Partitions
  • The Partition Problem (Algorithm Design Manual)
  • DP in DAGs
  • DP on Trees and DAGs (IOI Training, Philippines)
  • Bitmasks and DP
  • A bit of fun: fun with bits (TopCoder)
  • Dynamic Programming and Bit Masking (HackerEarth)
  • A little bit of classics: dynamic programming over subsets and paths in graphs (CodeForces)
  • TSP with DP
  • Travelling Salesman Problem (GeeksforGeeks)
  • Held-Karp Algorithm (Wikipedia)

Initiation/Reinforcement Problems

• [UVA 10404] - Bachet's Game (DP with games - minimax principle)
• [UVA 11258] - String Partition (DP partitions)
• [UVA 10285] - Longest Run on a Snowboard (DP in DAGs)
• [SPOJ COURIER] - The Courier (DP with bitmasks, TSP)
• [UVA 10910] - Marks Distribution (DP counting)

Pedro Ribeiro - DCC/FCUP | Last update: