Skip to content

Instantly share code, notes, and snippets.

View miguelAlessandro's full-sized avatar

miguelAlessandro

13 followers · 11 following
View GitHub Profile
@miguelAlessandro
miguelAlessandro / brute-force:partitions
Created August 13, 2019 19:10
#Brute Force: Partitions
usted esta en medio de una competencia, quedan pocos minutos\... y lee el
siguiente problema:
Se le proporciona un grafo con n <= 40 nodos (posiblemente completo).
Debe imprimir el cardinal del [maximo conjunto independiente](https://en.wikipedia.org/wiki/Maximal_independent_set).
![MIS](https://en.wikipedia.org/wiki/Maximal_independent_set#/media/File:Cube-maximal-independence.svg)
@miguelAlessandro
miguelAlessandro / nt.cpp
Created June 11, 2019 18:05
number theory algorithms
//gcd
int gcd(int a, int b) {
return b!=0 : gcd(b, a%b), a;
}
//extended gcd
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1; y = 0;
return a;
@miguelAlessandro
miguelAlessandro / release.md
Last active May 13, 2019 19:01
  • create branch with release: "git checkout -b release/version" (update last release)
  • update develop
  • merge my new branch with develop
  • commit changes
  • (log status with develop)
  • make pull request
  • compare with master
  • update changelog (commit this)
  • create pull request
  • copy links
@miguelAlessandro
miguelAlessandro / trees_questions.md
Created February 26, 2019 05:18

graphs and trees.

conceptos claros

  • Diseñe un algoritmo para verificar si un grafo es un tree.

  • Como usarias lo anterior para probar que un grafo no tenga ciclos.

  • Test bipartito: Supongamos que tengo un grafo bipartito e inicio de un nodo cualesquiera, y voy marcando a los nodos vecinos con colores opuestos (rojo y azul). Cuando

@miguelAlessandro
miguelAlessandro / trees.md
Last active February 26, 2019 05:46

Grafos 1: Trees

Un grafo en matematicas discretas es una estructura discreta compuesta por un conjunto de vertices y un conjunto de aristas, el conjunto de aristas esta incluido en el conjunto de pares de elementos del conjunto de vertices.

ejemplo:

vertices: {1, 2, 3, 4}

@miguelAlessandro
miguelAlessandro / numeros_primos.md
Last active February 21, 2019 05:43

Numeros primos

La mayor cantidad de problemas en teoría de números hablan sobre números primos.

definición:

un número primo es un número mayor a 1 que no se puede expresar como a x b, para a y b enteros mayores a 1.

@miguelAlessandro
miguelAlessandro / backtracking.md
Last active February 14, 2019 06:33

Backtracking

Backtracking es un algoritmo general para resolver problemas de búsqueda completa, el cual usa la estrategia de abandonar soluciones candidatas si no puede ser posible que se vuelva una solución al problema.

Backtracking solo puede ser aplicable si el problema admite un parcial candidato de una solución.

Aun siendo un enfoque de busqueda completa, muchos algoritmos np son solucionables optima y exactamente con este enfoque. Entre ellos se encuentran problemas como sudoku, 8 reinas, covertura exacta, knapsack problem, etc.

C

Estructura del backtracking

@miguelAlessandro
miguelAlessandro / clase_05.md
Last active February 5, 2019 20:38

Uso de stacks

supongamos que queremos realizar las siguientes operaciones:

  1. agregar un elemento

  2. quitar el ultimo elemento

  3. consultar el minimo de todos los elementos actuales

@miguelAlessandro
miguelAlessandro / sqrt_descomposition.md
Last active February 4, 2019 17:45
@miguelAlessandro
miguelAlessandro / complete_search\brute_force.md
Last active February 6, 2019 23:58

complete search \ Brute force

Brute force es un enfoque exhaustivo que trabaja revisando toda posible respuesta mientras la correcta no es encontrada. Esto hace que los algoritmos regidos por este enfoque sean lentos en ejecución. Por ejemplo buscar los factores primos de un número increiblemente grande (> 10^1000) o elegir el mejor movimiento en una partida de ajedrez, tienen tantos estados que hace imposible computacionalmente encontrar una solución bajo este enfoque.

Para hacer un problema de brute force, por tanto, se debe recorrer de la forma más inteligente los estados (tenga en cuenta que el nombre brute force solo se refiere a que no se aplicará ninguna heurística para reolver el problema, pero no a como esto se vaya a realizar).

La estructura común de un algoritmo de brute force es:

c = firstState(Problem)