Contents - Webcourse

Contents 1.

2.

Mathematica.......................................................................................................................................... 2 1.1.

Karatsuba ....................................................................................................................................... 2

1.2.

Integration by Simpson .................................................................................................................. 2

1.4.

Module in Factorial ........................................................................................................................ 3

1.5.

Binary exponentiation ................................................................................................................... 3

Graphs .................................................................................................................................................... 3 2.1.

Topological sort ............................................................................................................................. 3

2.2. Strongly connected components ........................................................................................................ 4

3.

4.

2.3.

K shortest path............................................................................................................................... 5

2.4.

Dijkstra Algorithm .......................................................................................................................... 6

2.5.

Minimum Spanning Tree: Kruskal Algorithm + Union-Find ........................................................... 7

2.6.

Floyd-Warshall Algorithm .............................................................................................................. 8

2.7.

Bellman-Ford algorithm ................................................................................................................. 9

2.8.

Points of articulation ................................................................................................................... 10

2.9.

Maximum flow: Ford-Fulkerson method, Edmonds-Karp algorithm .......................................... 11

Three. Dynamic Programming ............................................................................................................. 12 3.1.

Longest common subsequence ................................................................................................... 12

3.2.

Submatrix of zeros Maxima ......................................................................................................... 12

Geometry ............................................................................................................................................. 13 4.1.

Area of a polygon ......................................................................................................................... 13

4.2.

Mass center of a polygon ............................................................................................................ 13

4.3.

Convex hull: Graham Scan ........................................................................................................... 14

4.4.

Minimum distance between a point and a segment ................................................................... 15

4.5.

Minimum distance between a point and a line ........................................................................... 16

4.6.

Determine whether a polygon is convex ..................................................................................... 16

1

1.

Mathematica

1.1.

Karatsuba

//Mandar como Parametro N el numero de bits import java.math.BigInteger; import java.util.Random; class Karatsuba { private final static BigInteger ZERO = new BigInteger("0"); public static BigInteger karatsuba(BigInteger x, BigInteger y) { int N = Math.max(x.bitLength(), y.bitLength()); if (N = 1; } return res; }

Si quiero aumentar el tama~no de una fila en particular insertar en esa fila.

2.

Graphs

2.1.

Topological sort

vector < vector > g; int n; vector used; list ans;

void dfs(int v) 3

{ used[v] = true; for(vector::itetator i=g[v].begin(); i!=g[v].end(); ++i) if(!used[*i]) dfs(*i); ans.push front(v); } void topological sort(list & result) { used.assign(n, false); for(int i=0; i g, gr; vector used; vector order, component; void dfs1(int v) { used[v] = true; for(size t i=0; i> t.end >> t.weight; e.push back(t); total += t.weight; } sort(e.begin(), e.end()); for (int i=0; i> u; g[v].push back(u); g[u].push back(v); } cameras.clear(); for (graph::iterator i = g.begin(); i != g.end(); ++i){ if (colors[(*i).first] == WHITE){ dfs((*i).first); } } cout