Algoritmos

Table of contents

Algoritmos que todo programador deveria conhecer bem.

C++/STL

• count_if
• for_each
• max_element

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

• What algorithms should I know to become a good programmer?
• C++20/17/14/11