Back to TIL list

# Algoritmos

Last uptate at
Created at

Algoritmos que todo programador deveria conhecer bem.

## Estruturas lineares de dados

• [Arrays](null)
• 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