Sumários

String Matching

5 junho 2008, 08:00 • Andreas Miroslaus Wichert

String Matching, Rabin-Krap Alg., Finite Automaton, Knuth-Morris-Pratt Alg., Ex 32.3-1, Ex 32.4-1, Ex 32.4-5

String Matching

4 junho 2008, 08:00 • Andreas Miroslaus Wichert

String Matching, Rabin-Krap Alg., Finite Automaton, Knuth-Morris-Pratt Alg., Ex 32.3-1, Ex 32.4-1, Ex 32.4-5

String Matching

3 junho 2008, 08:00 • Andreas Miroslaus Wichert

String Matching, Rabin-Krap Alg., Finite Automaton, Knuth-Morris-Pratt Alg., Ex 32.3-1, Ex 32.4-1, Ex 32.4-5

Approximation Algorithms

2 junho 2008, 10:00 • Andreas Miroslaus Wichert

Approximation ratio, Vertex-cover problem, 2-approximation ratio algorithm - proof, TSP, TSP with triangle inequality is a 2-approximation ratio algorithm - proof with MST, no good approx. tours if cost function does not satisfy triangle inequality

NPC problems

29 maio 2008, 09:30 • Andreas Miroslaus Wichert

3-CNF SAT, CLIQUE, VERTEX COVER, (HAM-CYCLE), TSP, (SUBSET-SUM). Problems in brackets were mentioned without the reduction algorithm, and without the proof of being NP-Hard