Publicado em: 03/Jan/2020
Atualizado em: 04/Jan/2020

Algoritmos

Algoritmos que todo programador deveria conhecer bem.

Estruturas lineares de dados

  • Arrays
  • Linked List - Single and Doubly
  • Stack
  • Queues

Algoritmos básicos

  • Sorting - Merge Sort, Insertion Sort, Quick Sort, Number of inversions
  • Matrix Multiplication (just know the algo if not implement it)
  • Prime Sieving
  • Modular Math including multiplication and division
  • Euclidean Algorithm for GCD, Modular Inverse, Fast Exponentiation
  • Fibonacci number with matrix multiplication
  • Probability distribution and expected value
  • Stats - Mean, Median, Variance, Bayes theorem

Técnicas populares

  • Divide and Conquer - Binary Search, Maximum Subarray
  • Greedy Algorithms - Activity Selection, Huffman encoding
  • Dynamic Programming - Matrix Chain Multiplication, Knapsack,
  • Linear Programming - Variable Maximisation, Linear time sorting
  • String Algorithms - Manacher, LCS, Edit Distance

Estruturas não lineares de dados

  • Trees - Binary Tree, General Tree, Lowest Common Ancestor
  • Binary Search Tree - Inorder Traversal, Level order traversal, finding kth largest element, diameter, depth, number of nodes, etc.
  • Heaps - Array Implementation, Heapify, Heap Sort
  • Union Find
  • Hash Table - Linear Probing, Open addressing, Collision avoidance

Grafos

  • Adjacency List, Adjacency Matrix, Weighted Edge Graphs
  • Basic Traversal algos - Breadth First Search, Depth First Search, etc
  • Shortest Path Finding Algorithm - Dijkstra, Floyd Warshal, Bellman Ford
  • Minimum Spanning Tree - Kruskal's Algo, Prim's Algo

Árvores avançadas e grafos

  • Balanced Trees - AVL, Red-Black
  • Heavy Light Decomposition, B+ Trees, Quad Tree
  • Advance Graph - Min Cut, Max Flow
  • Maximum Matching - Hall's Marriage
  • Hamiltonian Cycle
  • Edge Graphs / Line Graphs
  • Strongly Connected Components
  • Dominant Sub-Graph, Vertex Cover, Travelling Salesman - Approx algos

Algoritmos avançados para String

  • Knuth Morris Pratt Algorithm
  • Rabin Karp Algorithm
  • Tries and Compressed Tries
  • Prefix Trees, Suffix Trees, Suffix Automation - Ukkonen Algorithm

Matemática avançada

  • Fast Fourier Transformation
  • Primality Testing
  • Computational Geometry - Closest point pair, Voronoi diagram, Convex Hull

Tópicos gerais avançados

  • Iterating through all combination / permutation
  • Bit manipulation

Referências

comments powered by Disqus