velasquezerik/cpp

algorithms in c++

cpp

Algorithms and Data Structures in C++

Graph Algorithms

• DFS
• BFS
• Topological Sort: Tarjan, Kahn
• Bipartite Check
• All Pairs Shortest Paths (APSP) Floyd-Warshall
• Max Flow Edmonds Karp

Tree Algorithms

• Tree traversal
• Tree level order
• Tree vertical order
• Tree diameter
• Valid BST
• Symmetric Tree

Search Algorithms

• Generating Subsets
• Eight Queens Problem
• Branch and Bound Knapsack
• Maze Backtracking
• Hamiltonian Paths
• K-Colorable Graph
• Exact Set Cover

Greedy Algorithms

• Interval Schedule
• Coin change
• Minimum Spanning Tree: Kruskal
• Huffman Coding
• Fractional Knapsack

Divide and Conquer

• Binary Search
• Quick Select

Dynamic Programming

• Binomial Coefficients
• Knapsack
• Coin Change
• Max subarray sum
• Memoized Matrix Chain Product
• Longest Common Substring
• String Alignment Needleman-Wunsch

Sorting

• Radix sort
• Bucket sort
• Quick sort
• Merge sort
• Heap sort
• Selection sort
• Insertion sort

Data Structures

• Trie
• Binary Heap
• Circular Queue
• Queue Using 2 Stacks
• Binary Search Tree
• Disjoint Set Union Find

Misc

• Sieve of Eratosthenes
• Convex Polygon Check
• Sliding window
• String matching
• Matrix Spiral
• Two Pointers
• Intersection
• Matching Parenthesis
• Cycle Detection (Floyd)
• Flood Fill
• Tower of Hanoi
• Fast Power
• Connected Components
• Fisher-Yates shuffle
• Generating permutations

Machine Learning

• KD Tree
• Alpha Beta Pruning
• Perceptron
• Dirichlet-Process K-means
• Binary Logistic Regression
• L-BFGS optimization

Jupyter Notebooks

The notebooks were created using xeus-cling: a Jupyter kernel for C++

• xtensor: ipynb
• eigen: ipynb

Compiling

To compile the C++ files, run the following command:

g++ <filename.cpp> --std=c++11 -Wall -o test 

Dependencies

C++11