tonysheng01/Algorithms-and-Data-Structures

An assortment of commonly used algorithms and data structures implemented with C++.

Algorithms-And-Data-Structures

This repo contains C++ implementations of common algorithms and data structures, grouped by topics. The list will be sporadically updated.

Data Structures:

• Binary heap
• Huffman Tree
• Trie (Prefix tree)
• Union-find

Algorithms:

Graphs

• BFS & DFS

Undirected Graphs

• Bipartiteness testing
• Connected components
• Articulation points and bridges: Tarjan's Algorithm
• Minimum spanning trees: Prim's Algorithm
• Minimum spanning trees: Kruskal's Algorithm
• Maximum spacing k-clustering

Directed Graphs

• Topological sorting
• Strongly connected components: Kosaraju's Algorithm and Tarjan's Algorithm
• Shortest paths: Dijkstra's Algorithm
• (Trees) Lowest common ancestor: Tarjan's Offline Algorithm

Pattern Searching

• Single-pattern searching: Knuth-Morris-Pratt Algorithm
• Multi-pattern searching: Aho-Corasick Algorithm

Divide and Conquer

• Binary search
• Merge sort and counting inversions
• Closest pair of points in a 2D plane

Miscellaneous

• A selection of greedy algorithms focused on interval scheduling and optimal caching
• Stable matching: Gale-Shapley Algorithm