:pushpin: Algorithm Notebook

Este repositorio contiene una recopilación de algorimtos y estructuras de datos populares codificados en Java y C++.

Cada algoritmo y estructura de datos tiene su propio README con explicaciones relacionadas y enlaces de referencias.

Algoritmos

Un algoritmo es una especificación inequívoca de cómo resolver una clase de problemas. Es un conjunto de reglas que definen con precisión una secuencia de operaciones.

P - Principiante, I - Intermedio, A - Avanzado

• Strings

  • P Hamming Distance - número de posiciones en las que los símbolos son diferentes
  • I Longest Common Subsequence
  • I Longest Common SubString
  • I Trie (Prefix Tree) Arbol de Prefijos
  • I Knuth–Morris–Pratt Algorithm (KMP Algorithm) - búsqueda de subcadenas (coincidencia de patrones)
  • A Levenshtein Distance distancia mínima de edición entre dos strings

• Busquedas

  • P Búsqueda Binaria - Busqueda eficiente en un campo ordenado.
  • P LowerBound & UpperBound

• Matemáticas

  • P Greatest Common Divisor - Euclides - calcular el máximo común divisor (MCD)
  • P Least Common Multiple - calcular el minimo común multiplo (MCM)
  • P Algoritmo de Euclides Extendido
  • P Criba de Eratostenes - Sieve of Eratosthenes - encontrar todos los números primos hasta un límite dado
  • P Factores Primos - Prime Factors - encontrar todos los factores primos y sus multiplicidades de un numero
  • P Test de Primalidad - verificar si un numero es primo de forma eficiente
  • P Fibonacci - Secuencia de Fibonacci
  • P ¿Es potencia de N? - Verifica si un numero es potencia de N.
  • P Suma de múltiplos de un número desde 1 hasta N - Calcula la suma de todos los divisores de un numero dado desde 1 hasta N incluyendolo.

• Arboles

  • I Lowest Common Ancestor of a Binary Search Tree - encontrar el ancestro común más bajo

• Programación Dinamica

  • P Algoritmo de Kadane - Suma Maxima de SubArrays - Encontrar un sub array cuya suma sea maxima

  • P Range Sum Query - Immutable - Realizar sumas entre rangos para un array immutable

  • A Aliens Trick - Dado un array y un k, encontrar k sub arrays cuya suma sea maxima

• Graphs

  • P Depth-first search (DFS) Metodo para recorrer todos los nodos de un Grafo, de forma recursiva

  • I Breadth-first search (DFS) Metodo para recorrer todos los nodos de un Grafo, de forma iterativa

  • I Dijkstra's Algorithm - encontrar los caminos más cortos a todos los vértices del grafo desde un solo vértice

  • I Save Path - Dijkstra - encontrar los caminos más cortos y la ruta a todos los vértices del grafo desde un solo vértice

  • I Disjoint Set Union - Verificar conectividad de dos nodos de un grafo óptimamente

  • I Algoritmo de Floyd-Warshall encontrar los caminos más cortos entre todos los pares de vértices

  • I Algoritmo de Kruskal - Minimum Spanning Tree encontrar el árbol de cubrimiento mínimo (MST) para un grafo no dirigido ponderado

  • I Topological Sort Metodo para Ordenar los vertices de un Grafo Dirigido

  • I Bridges Algoritmo para encontrar los puentes de un Grafo no Dirigido

  • I Kosaraju's Algorithm - SCC Algoritmo para encontrar los componentes fuertemente conexos en un Grafo Dirigido

• Geometry

  • P Operaciones entre Vectores 2D (+-*/) Operaciones elementales entre vectores (Suma, Resta, Multiplicación y División)

  • P Producto Punto de Vectores 2D Producto punto entre vectores 2D

  • P Producto Cruz de Vectores 2D Producto Cruz entre vectores 2D

  • P Orientación de Vectores 2D Verificar la orientación de un vector con respecto a otros vectores

  • P Distancia Euclideana 2D Distancia Euclideana en un plano 2D

  • P Distancia Manhattan 2D Distancia Manhattan en un plano 2D

  • P Distancia Chebyshev 2D Distancia Chebyshev en un plano 2D

  • I Area de un Poligono Calcular el area de un poligono

  • I Perimetro de un Poligono Calcular el perimetro de un poligono

  • A Convex Hull - Monotone Chain Calcular el minimo envolvente convexa que cubra todos los puntos dados

• Backtracking

  • P Generate all the binary strings of N bits Calcular todos los string binarios de N bits

  • I Generate all Permutations Calcular todas las permutaciones de los valores de un vector

Estructuras de Datos

Una estructura de datos es una forma particular de organizar y almacenar datos en un ordenador para que puedan accederse y modificarse de forma eficiente. Más concretamente, una estructura de datos es un conjunto de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a los datos.

P - Principiante, I - Intermedio, A - Avanzado

• Grafos

  • I Algoritmo de Floyd-Warshall - encontrar los caminos más cortos entre todos los pares de vértices
  • I Disjoint Set Union
  • I Kruskal - Minimum Spanning Tree - encontrar el árbol de cubrimiento mínimo (MST) para un grafo no dirigido ponderado

• Arboles

  • I Binary Search Tree
  • I N-ary Tree
  • I Trie (Prefix Tree)

:books: Libros

• :blue_book: Competitive Programmer’s Handbook by Antti Laaksonen
• :blue_book: Handbook of geometry for competitive programmers by Victor Lecomte

:bookmark_tabs: Paginas de Consulta

• :bookmark: Geeks For Geeks

• :bookmark: Codeforces

• :bookmark: CP Algorithms

• :bookmark: A Bit of CS

• :bookmark: Techie Delight

• :bookmark: Emre.me

• :bookmark: Iq OpenGenus