A c++ implementation of different algorithms and data structures.
I make generous use of C++ STL and all data structures are designed to be used as is and are templated wherever applicable and can be readily used in your own projects.
It contains the following data structures and algorithms as of now and more will be coming each day.
- Strings - Reversal, permutations, basic string compression, Anagram testing, wild card expansion
- Sorting - Merge sort, randomized quick sort, median-of-3 quick sort
- Linked Lists - insertion, deletion, detecting cycles, detecting palindromes
- Stacks - Towers of hanoi problem, Min-stack, Set of stacks, Three-in-one stack, Computation of max-area under histogram using stacks, Stacks using queues
- Queues - insertion, deletion, Queues using stacks
- Binary Trees - Tree traversals - in order, pre order, post order, get levels in a tree, ancestry, balance, height, diameter computation
- Binary Search Trees - insertion, deletion, search, successor, converting to sorted linked list
- Heaps - construction, insertion, extract-min, deletion, increase key, finding top k elements
- Graphs - BFS, DFS, Finding minimum cuts using kragers algorithm, Dijkstra shortest path algorithm, Finding Eulers path, Find connected components in undirected graphs, strongly connected components in directed graphs using Kosaraju's two-pass algorithm
- Selection - Randomized selection in linear time
- Divide and Conquer paradigm - Karatsuba integer multiplication, closest pair points in 2-dimensional plane, Counting inversions
- Integer arrays - partitioning arrays, longest increasing sub sequence, max product sub array problem, maximum number of overlapping intervals problem, median of two sorted arrays, finding all permutations of arrays, biggest interval of contiguous numbers in an array
- Dynamic Programming - Fibonacci number computation, Longest common subsequence, Largest sum subsequence, Edit distance problem, Minimum coins required to provide a sum, integer knapsack problem, subset sum problem Longest palindromic sub sequence of a given string
- Data structures - LRU Cache, Fixed capacity boolean vector
- Greedy algorithms - Scheduling jobs minimizing weighted completion times.