Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
graph_coloring.cpp File Reference

prints the assigned colors using Graph Coloring algorithm More...

#include <iostream>
#include <array>
#include <vector>
Include dependency graph for graph_coloring.cpp:

Namespaces

 backtracking
 Backtracking algorithms.
 

Functions

template<size_t V>
void backtracking::printSolution (const std::array< int, V > &color)
 
template<size_t V>
bool backtracking::isSafe (int v, const std::array< std::array< int, V >, V > &graph, const std::array< int, V > &color, int c)
 
template<size_t V>
void backtracking::graphColoring (const std::array< std::array< int, V >, V > &graph, int m, std::array< int, V > color, int v)
 
int main ()
 

Detailed Description

prints the assigned colors using Graph Coloring algorithm

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Author
Anup Kumar Panwar
David Leal

Function Documentation

◆ main()

int main ( void  )

Main function

96  {
97  // Create following graph and test whether it is 3 colorable
98  // (3)---(2)
99  // | / |
100  // | / |
101  // | / |
102  // (0)---(1)
103 
104  const int V = 4; // number of vertices in the graph
106  std::array <int, V>({0, 1, 1, 1}),
107  std::array <int, V>({1, 0, 1, 0}),
108  std::array <int, V>({1, 1, 0, 1}),
109  std::array <int, V>({1, 0, 1, 0})
110  };
111 
112  int m = 3; // Number of colors
113  std::array <int, V> color{};
114 
115  backtracking::graphColoring<V>(graph, m, color, 0);
116  return 0;
117 }
mov
void mov(tower *From, tower *To)
Definition: tower_of_hanoi.cpp:39
merge_insertion
Combined Intersion-Merge sorting algorithm.
std::srand
T srand(T... args)
main
int main()
Definition: knuth_morris_pratt.cpp:76
main
int main()
Definition: fenwick_tree.cpp:69
std::max_element
T max_element(T... args)
std::vector::resize
T resize(T... args)
ternary_search
void ternary_search(int N, int A[], int target)
Definition: ternary_search.cpp:127
std::floor
T floor(T... args)
test3
void test3()
Definition: smallest_circle.cpp:188
main
int main(void)
Definition: decimal_to_hexadecimal.cpp:11
method2
void method2(int number)
Definition: decimal_to_binary.cpp:27
main
int main()
Definition: exponential_search.cpp:74
mat_size
ll mat_size
Definition: matrix_exponentiation.cpp:45
main
int main()
Definition: stairs_pattern.cpp:17
hash_search
int hash_search(int key, int *counter)
Definition: hash_search.cpp:76
std::string
STL class.
sorting::shell_sort
void shell_sort(T *arr, size_t LEN)
Definition: shell_sort2.cpp:45
main
int main()
Definition: fibonacci_search.cpp:123
tolowerRoman
std::string tolowerRoman(int n)
Definition: decimal_to_roman_numeral.cpp:24
test_f
void test_f(const int NUM_DATA)
Definition: shell_sort2.cpp:145
string_search
String search algorithms.
Definition: brute_force_string_searching.cpp:13
range_queries::heavy_light_decomposition::HLD::chain_query
X chain_query(int a, int b)
Utility function to break down a path query into two chain queries.
Definition: heavy_light_decomposition.cpp:409
MAX
#define MAX
Definition: fibonacci_fast.cpp:27
range_queries::heavy_light_decomposition::Tree::t_size
std::vector< int > t_size
a vector to store the subtree size rooted at node
Definition: heavy_light_decomposition.cpp:89
show_data
void show_data(T *arr, size_t LEN)
Definition: shell_sort2.cpp:18
range_queries::heavy_light_decomposition::Tree::dfs_lca
void dfs_lca(int u, int p=-1)
Utility function to populate the t_par vector.
Definition: heavy_light_decomposition.cpp:116
heapSort
void heapSort(T *arr, int n)
Definition: heap_sort.cpp:84
std::clock_t
range_queries::heavy_light_decomposition::Tree::t_root
int t_root
the root of the tree
Definition: heavy_light_decomposition.cpp:91
std::move
T move(T... args)
main
int main()
Definition: binomial_dist.cpp:84
addition_rule_dependent
double addition_rule_dependent(double A, double B, double B_given_A)
Definition: addition_rule.cpp:25
range_queries::heavy_light_decomposition::Tree::t_maxlift
const int t_maxlift
maximum possible height of the tree
Definition: heavy_light_decomposition.cpp:85
range_queries::heavy_light_decomposition::Tree::lca
int lca(int a, int b)
The function returns the least common ancestor of two nodes.
Definition: heavy_light_decomposition.cpp:229
range_queries::heavy_light_decomposition::Tree::set_node_val
void set_node_val(const std::vector< X > &node_val)
Set the values for all the nodes.
Definition: heavy_light_decomposition.cpp:175
test2
void test2()
Definition: smallest_circle.cpp:173
range_queries::heavy_light_decomposition::Tree::init
void init()
This function must be called after the tree adjacency list and node values are populated The function...
Definition: heavy_light_decomposition.cpp:186
test_3
static void test_3()
Definition: heavy_light_decomposition.cpp:592
std::pair
range_queries::heavy_light_decomposition::Tree
A Basic Tree, which supports binary lifting.
Definition: heavy_light_decomposition.cpp:78
range_queries::heavy_light_decomposition::SG::update
void update(int p, X v)
Update the value at a node.
Definition: heavy_light_decomposition.cpp:293
range_queries::heavy_light_decomposition::Tree::Tree
Tree(int nodes)
Class parameterized constructor, resizes the and initializes the data members.
Definition: heavy_light_decomposition.cpp:140
random_tests
bool random_tests()
random tests which cover cases when we have one, multiple or zero occurences of the value we're looki...
Definition: fibonacci_search.cpp:96
std::vector
STL class.
std::find
T find(T... args)
range_queries::heavy_light_decomposition::SG::sret_init
X sret_init
inital query return value
Definition: heavy_light_decomposition.cpp:264
std::vector::size
T size(T... args)
Point::x
double x
Definition: smallest_circle.cpp:16
test_2
static void test_2()
Definition: heavy_light_decomposition.cpp:549
main
int main()
Definition: decimal_to_roman_numeral.cpp:90
sorting::pigeonSort
std::array< int, N > pigeonSort(std::array< int, N > arr)
Definition: pigeonhole_sort.cpp:34
FenwickTree::sum_range
int sum_range(int l, int r)
Definition: fenwick_tree.cpp:65
test
void test()
Definition: heap_sort.cpp:99
absolutePrecision
#define absolutePrecision
Definition: ternary_search.cpp:22
ans
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
range_queries::heavy_light_decomposition::HLD::init
void init()
This function must be called after the tree adjacency list and node values are populated The function...
Definition: heavy_light_decomposition.cpp:450
range_queries::heavy_light_decomposition::SG::combine
X combine(X lhs, X rhs)
Function that specifies the type of operation involved when segments are combined.
Definition: heavy_light_decomposition.cpp:274
FenwickTree
Definition: fenwick_tree.cpp:17
range_queries::heavy_light_decomposition::Tree::add_edge
void add_edge(const int u, const int v)
Adds an undirected edge from node u to node v in the tree.
Definition: heavy_light_decomposition.cpp:157
main
int main()
Definition: gnome_sort.cpp:130
sorting::insertionSort
void insertionSort(T *arr, int n)
Insertion Sort Function.
Definition: insertion_sort.cpp:59
HASHMAX
#define HASHMAX
Determines the length of the hash table.
Definition: hash_search.cpp:22
PRIME
#define PRIME
Prime modulus for hash functions.
Definition: rabin_karp.cpp:16
sorting::partition
int partition(int arr[], int low, int high)
Definition: quick_sort.cpp:37
std::distance
T distance(T... args)
binary_s
Type * binary_s(Type *array, size_t size, Type key)
Definition: exponential_search.cpp:34
node
Definition: avltree.cpp:13
Point::y
double y
Definition: smallest_circle.cpp:17
std::search
T search(T... args)
node
struct list node
FindNextGap
int FindNextGap(int gap)
Definition: comb_sort.cpp:29
MAX
#define MAX
Determines how much data.
Definition: hash_search.cpp:21
main
int main()
Definition: pascal_triangle.cpp:52
main
int main()
Definition: bayes_theorem.cpp:26
std::scanf
T scanf(T... args)
multiply
vector< vector< ll > > multiply(const vector< vector< ll >> &A, const vector< vector< ll >> &B)
Definition: matrix_exponentiation.cpp:57
test_double
static void test_double()
Definition: quick_sort_3.cpp:160
std::reverse
T reverse(T... args)
test
static void test()
Definition: gnome_sort.cpp:85
main
int main(void)
Definition: qr_decomposition.cpp:23
main
int main()
Definition: palindrome_of_number.cpp:19
sorting
Sorting algorithms.
main
int main()
Definition: vector_important_functions.cpp:11
std::queue
STL class.
sorting::merge
void merge(Iterator, Iterator, const Iterator, char[])
merges 2 sorted adjacent segments into a larger sorted segment
Definition: non_recursive_merge_sort.cpp:57
strings
Algorithms with strings.
sorting::shuffle
std::array< T, N > shuffle(std::array< T, N > arr)
Definition: bogo_sort.cpp:36
main
int main()
Definition: linear_search.cpp:27
range_queries::heavy_light_decomposition::HLD::update
void update(int node, X val)
This function updates the value at node with val.
Definition: heavy_light_decomposition.cpp:475
eqd
static float eqd(float y)
Definition: successive_approximation.cpp:17
show_array
void show_array(const std::array< T, N > &arr)
Definition: bogo_sort.cpp:68
range_queries::heavy_light_decomposition::SG::SG
SG(int size)
Class parameterized constructor. Resizes the and initilizes the data members.
Definition: heavy_light_decomposition.cpp:282
std::sort
T sort(T... args)
fill
std::string fill(char c, int n)
Definition: decimal_to_roman_numeral.cpp:15
mat_mul
void mat_mul(const std::valarray< std::valarray< double >> &A, const std::valarray< std::valarray< double >> &B, std::valarray< std::valarray< double >> *OUT)
Definition: qr_eigen_values.cpp:54
string_search::create_hash
int64_t create_hash(const std::string &s, int n)
Definition: rabin_karp.cpp:25
std::sqrt
T sqrt(T... args)
stack_idx
int stack_idx
pointer to track stack index
Definition: paranthesis_matching.cpp:23
main
int main(int argc, char *argv[])
Definition: shell_sort2.cpp:183
range_queries::heavy_light_decomposition::HLD
The Heavy-Light Decomposition class.
Definition: heavy_light_decomposition.cpp:336
main
int main()
Definition: interpolation_search2.cpp:32
compare
int compare(const void *a, const void *b)
Definition: shell_sort2.cpp:87
string_search::brute_force
int brute_force(const std::string &text, const std::string &pattern)
Definition: brute_force_string_searching.cpp:21
main
int main()
Definition: buzz_number.cpp:9
std::vector::clear
T clear(T... args)
std::is_sorted
T is_sorted(T... args)
fibonacci_search
int fibonacci_search(const std::vector< int > &arr, int value)
using fibonacci search algorithm finds an index of a given element in a sorted array
Definition: fibonacci_search.cpp:23
qr_algorithm
Functions to compute QR decomposition of any rectangular matrix.
range_queries::heavy_light_decomposition::Tree::lift
void lift(int *const p, int dist)
The function lifts a node, k units up the tree. The lifting is done in place, and the result is store...
Definition: heavy_light_decomposition.cpp:200
FenwickTree::offset
int offset(int x)
Definition: fenwick_tree.cpp:22
create_matrix
void create_matrix(std::valarray< std::valarray< double >> *A)
Definition: qr_eigen_values.cpp:28
main
int main()
Definition: happy_number.cpp:29
query
Definition: mo.cpp:6
search
Search algorithms.
main
int main()
Definition: text_search.cpp:15
show
void show(int *arr, int size)
Definition: merge_sort.cpp:96
test_set
const std::vector< std::vector< std::string > > test_set
Definition: brute_force_string_searching.cpp:41
rec_ternary_search
int rec_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:90
Node
Definition: linkedlist_implentation_usingarray.cpp:14
std::vector::push_back
T push_back(T... args)
main
int main()
Definition: pigeonhole_sort.cpp:127
Point::y
int y
Point respect to x coordinate.
Definition: line_segment_intersection.cpp:14
qr_algorithm::eigen_values
std::valarray< double > eigen_values(std::valarray< std::valarray< double >> *A, bool print_intermediates=false)
Definition: qr_eigen_values.cpp:98
std::clock
T clock(T... args)
string_search::recalculate_hash
int64_t recalculate_hash(const std::string &s, int old_index, int new_index, int64_t old_hash, int patLength)
Definition: rabin_karp.cpp:42
fastinput
void fastinput(int *number)
Definition: fast_integer_input.cpp:11
main
int main()
Definition: smallest_circle.cpp:198
test_int
void test_int(const int NUM_DATA)
Definition: shell_sort2.cpp:105
range_queries::heavy_light_decomposition::HLD::dfs_par
void dfs_par(int u, int p=-1)
Utility function to assign highest parent that can be reached though heavy chains.
Definition: heavy_light_decomposition.cpp:371
pascal_triangle
int ** pascal_triangle(int **arr, int n)
Definition: pascal_triangle.cpp:36
CombSort
void CombSort(int *arr, int l, int r)
Definition: comb_sort.cpp:42
sorting::quicksort
void quicksort(std::vector< T > *arr, int32_t low, int32_t high)
Definition: quick_sort_3.cpp:94
insert
node * insert(node *root, int item)
Definition: avltree.cpp:66
std::printf
T printf(T... args)
std::array::at
T at(T... args)
range_queries::heavy_light_decomposition::HLD::h_heavychlid
std::vector< int > h_heavychlid
stores the heavy child of a node
Definition: heavy_light_decomposition.cpp:340
FenwickTree::FenwickTree
FenwickTree(const std::vector< int > &arr)
Definition: fenwick_tree.cpp:28
mergeSort
void mergeSort(int *arr, int l, int r)
Definition: merge_sort.cpp:83
main
int main()
Definition: matrix_exponentiation.cpp:126
range_queries::heavy_light_decomposition::Tree::t_adj
std::vector< std::list< int > > t_adj
an adjacency list to stores the tree edges
Definition: heavy_light_decomposition.cpp:83
std::cout
range_queries::heavy_light_decomposition::SG::s_tree
std::vector< X > s_tree
Everything here is private, and can only be accessed through the methods, in the derived class (HLD)
Definition: heavy_light_decomposition.cpp:262
qr_decompose.h
Library functions to compute QR decomposition of a given matrix.
merge
void merge(int *arr, int l, int m, int r)
Definition: merge_sort.cpp:33
range_queries::heavy_light_decomposition::Tree::kth_ancestor
int kth_ancestor(int p, const int &dist)
The function returns the kth ancestor of a node.
Definition: heavy_light_decomposition.cpp:218
create_random_array
static void create_random_array(T *arr, int N)
Create a random array objecthelper function to create a random array.
Definition: insertion_sort.cpp:101
h
int h(int key)
Definition: hash_search.cpp:45
sorting::non_recursive_merge_sort
void non_recursive_merge_sort(const Iterator first, const Iterator last)
bottom-up merge sort which sorts elements in a non-decreasing order
Definition: non_recursive_merge_sort.cpp:86
FenwickTree::update
void update(int id, int val)
Definition: fenwick_tree.cpp:45
main
int main(int argc, char const *argv[])
Definition: binary_search.cpp:31
tower
Definition: tower_of_hanoi.cpp:11
std::min_element
T min_element(T... args)
_target
#define _target
Definition: ternary_search.cpp:27
test
void test()
Definition: bogo_sort.cpp:78
binary_search
int binary_search(int a[], int r, int key)
Definition: binary_search.cpp:15
range_queries::heavy_light_decomposition::Tree::t_nodes
const int t_nodes
number of nodes
Definition: heavy_light_decomposition.cpp:84
opening
char opening(char ch)
Definition: paranthesis_matching.cpp:36
range_queries::heavy_light_decomposition::HLD::dfs_hc
void dfs_hc(int u, int p=-1)
Utility function to assign heavy child to each node (-1 for a leaf node)
Definition: heavy_light_decomposition.cpp:350
is_happy
bool is_happy(T n)
Definition: happy_number.cpp:14
string_search::check_if_equal
bool check_if_equal(const std::string &str1, const std::string &str2, int start1, int end1, int start2, int end2)
Definition: rabin_karp.cpp:60
main
int main()
Definition: median_search.cpp:128
main
int main()
Definition: ternary_search.cpp:134
binomial_range_successes
double binomial_range_successes(double n, double p, double lower_bound, double upper_bound)
Definition: binomial_dist.cpp:74
LenghtLine
double LenghtLine(const Point &A, const Point &B)
Definition: smallest_circle.cpp:37
std::qsort
T qsort(T... args)
std::to_string
T to_string(T... args)
std::array
STL class.
string_search::kmp
bool kmp(const std::string &pattern, const std::string &text)
Definition: knuth_morris_pratt.cpp:56
poisson_range_successes
double poisson_range_successes(double expected, double lower, double upper)
Definition: poisson_dist.cpp:54
main
int main()
Definition: tower_of_hanoi.cpp:65
sorting::non_recursive_merge_sort
void non_recursive_merge_sort(const Iterator first, const Iterator last, const size_t n)
bottom-up merge sort which sorts elements in a non-decreasing order
Definition: non_recursive_merge_sort.cpp:25
range_queries::heavy_light_decomposition::HLD::label
int label
utility member to assign labels in dfs_labels()
Definition: heavy_light_decomposition.cpp:338
ll
#define ll
Definition: matrix_exponentiation.cpp:33
std::string::erase
T erase(T... args)
std::valarray
STL class.
binomial_standard_deviation
double binomial_standard_deviation(double n, double p)
Definition: binomial_dist.cpp:36
test_1
static void test_1()
Definition: pigeonhole_sort.cpp:68
sorting::gnomeSort
void gnomeSort(T *arr, int size)
Definition: gnome_sort.cpp:34
range_queries::heavy_light_decomposition::Tree::t_par
std::vector< std::vector< int > > t_par
a matrix to store every node's 2^kth parent
Definition: heavy_light_decomposition.cpp:87
TriangleArea
double TriangleArea(const Point &A, const Point &B, const Point &C)
Definition: smallest_circle.cpp:54
main
int main()
Definition: brute_force_string_searching.cpp:47
std::int64_t
binomial_x_successes
double binomial_x_successes(double n, double p, double x)
Definition: binomial_dist.cpp:65
test2
void test2()
Definition: qr_eigen_values.cpp:210
std::remove
T remove(T... args)
endl
#define endl
Definition: matrix_exponentiation.cpp:36
link
struct list * link
pointer to nodes
spiralPrint
void spiralPrint(int **a, int r, int c)
Definition: spiral_print.cpp:29
bayes_BgivenA
double bayes_BgivenA(double AgivenB, double A, double B)
Definition: bayes_theorem.cpp:20
main
int main()
Definition: quick_sort_3.cpp:183
fib_b
vector< ll > fib_b
Definition: matrix_exponentiation.cpp:50
poisson_rate
double poisson_rate(double events, double timeframe)
Definition: poisson_dist.cpp:17
list::key
int key
key value for node
Definition: hash_search.cpp:30
main
int main(int argc, char **argv)
Definition: qr_eigen_values.cpp:243
search::median_search::median_of_medians
int median_of_medians(const std::vector< int > &A, const int &idx)
Definition: median_search.cpp:62
std::ceil
T ceil(T... args)
circle
double circle(const std::vector< Point > &P)
Definition: smallest_circle.cpp:87
test
static void test()
Function with test cases for Horspool's algorithm.
Definition: horspool.cpp:100
print
void print(uint32_t N, const std::vector< bool > &is_prime)
Definition: sieve_of_eratosthenes.cpp:44
eq
static float eq(float y)
Definition: successive_approximation.cpp:12
test_int
static void test_int()
Definition: quick_sort_3.cpp:138
struzik_search
Type * struzik_search(Type *array, size_t size, Type key)
Definition: exponential_search.cpp:59
main
int main()
Definition: poisson_dist.cpp:65
std::rand
T rand(T... args)
std::swap
T swap(T... args)
std::min
T min(T... args)
binomial_expected
double binomial_expected(double n, double p)
Definition: binomial_dist.cpp:22
main
int main()
Definition: heap_sort.cpp:120
hashtab
node hashtab[HASHMAX]
array of nodes
Definition: hash_search.cpp:35
std::string::substr
T substr(T... args)
heavy_light_decomposition
Heavy light decomposition algorithm.
it_ternary_search
int it_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:48
jumpSearch
int jumpSearch(int arr[], int x, int n)
Definition: jump_search.cpp:12
data
int data[MAX]
test data
Definition: hash_search.cpp:24
method1
void method1(int number)
Definition: decimal_to_binary.cpp:11
test1
void test1()
Definition: qr_eigen_values.cpp:177
no_occurence_tests
bool no_occurence_tests()
random tests for checking performance when an array doesn't contain an element
Definition: fibonacci_search.cpp:72
test_1
static void test_1()
Definition: heavy_light_decomposition.cpp:505
range_queries::heavy_light_decomposition::SG::query
X query(int l, int r)
Make a range query from node label l to node label r.
Definition: heavy_light_decomposition.cpp:305
range_queries::heavy_light_decomposition::HLD::dfs_labels
void dfs_labels(int u, int p=-1)
Utility function to lable the nodes so that heavy chains have a contigous lable.
Definition: heavy_light_decomposition.cpp:390
printArray
void printArray(T *arr, int sz)
Definition: heap_sort.cpp:37
std::lower_bound
T lower_bound(T... args)
main
int main()
Definition: hash_search.cpp:99
std::endl
T endl(T... args)
range_queries::heavy_light_decomposition::Tree::t_val
std::vector< X > t_val
values of nodes
Definition: heavy_light_decomposition.cpp:92
range_queries::heavy_light_decomposition::SG::s_size
int s_size
number of leaves in the segment tree
Definition: heavy_light_decomposition.cpp:263
main
int main()
Main function.
Definition: merge_insertion_sort.cpp:159
std::left
T left(T... args)
test_3
static void test_3()
Definition: pigeonhole_sort.cpp:109
create_list
void create_list(int key)
Definition: hash_search.cpp:55
fact
double fact(double x)
Definition: poisson_dist.cpp:30
main
int main()
Main Function that calls test function.
Definition: horspool.cpp:119
range_queries::heavy_light_decomposition::SG::set_sret_init
void set_sret_init(X new_sret_init)
Set the initialization for the query data type, based on requirement.
Definition: heavy_light_decomposition.cpp:329
std::exp
T exp(T... args)
main
int main()
Definition: fast_integer_input.cpp:39
std::string::begin
T begin(T... args)
std::getline
T getline(T... args)
std
STL namespace.
range_queries::heavy_light_decomposition::SG
Segment Tree, to store heavy chains.
Definition: heavy_light_decomposition.cpp:254
std::unordered_map::insert
T insert(T... args)
main
int main()
Definition: heavy_light_decomposition.cpp:634
median_search
Functions for Median search algorithm.
addition_rule_independent
double addition_rule_independent(double A, double B)
Definition: addition_rule.cpp:14
sorting::randomized_bogosort
std::array< T, N > randomized_bogosort(std::array< T, N > arr)
Definition: bogo_sort.cpp:51
show
void show(const struct tower *const F, const struct tower *const T, const struct tower *const U)
Definition: tower_of_hanoi.cpp:19
main
int main()
Definition: sparse_matrix.cpp:9
test
void test()
Definition: smallest_circle.cpp:158
range_queries
Algorithms and Data Structures that support range queries and updates.
compare
Definition: huffman.cpp:28
test
void test()
Definition: median_search.cpp:107
main
int main()
Definition: spiral_print.cpp:69
MAX
#define MAX
Definition: paranthesis_matching.cpp:16
stack
Definition: stack.h:26
power
vector< vector< ll > > power(const vector< vector< ll >> &A, ll p)
Definition: matrix_exponentiation.cpp:76
sorting::merge_insertion::InsertionSort
static void InsertionSort(std::array< T, N > *A, size_t start, size_t end)
Insertion merge algorithm.
Definition: merge_insertion_sort.cpp:37
graph
Graph algorithms.
main
int main()
Definition: successive_approximation.cpp:20
range_queries::heavy_light_decomposition::HLD::h_parent
std::vector< int > h_parent
stores the top of the heavy chain from a node
Definition: heavy_light_decomposition.cpp:341
std::count
T count(T... args)
tests
void tests()
Definition: insertion_sort.cpp:109
range_queries::heavy_light_decomposition::HLD::query
X query(int a, int b)
This function returns the sum of node values in the simple path from from node_1 to node_2.
Definition: heavy_light_decomposition.cpp:489
LinearSearch
int LinearSearch(int *array, int size, int key)
Definition: linear_search.cpp:16
std::vector::empty
T empty(T... args)
std::vector::assign
T assign(T... args)
IsPrime
bool IsPrime(int number)
Definition: primality_test.cpp:18
nCr
double nCr(double n, double r)
Definition: binomial_dist.cpp:47
tower::values
int values[10]
Values in the tower.
Definition: tower_of_hanoi.cpp:13
qr_algorithm::qr_decompose
void qr_decompose(const std::valarray< std::valarray< T >> &A, std::valarray< std::valarray< T >> *Q, std::valarray< std::valarray< T >> *R)
Definition: qr_decompose.h:146
main
int main()
Definition: insertion_sort.cpp:150
genArray
void genArray(int **a, int r, int c)
Definition: spiral_print.cpp:12
main
int main()
Definition: comb_sort.cpp:88
operator<<
static std::ostream & operator<<(std::ostream &out, matrix< T > const &v)
Definition: hill_cipher.cpp:54
range_queries::heavy_light_decomposition::Tree::dfs_size
void dfs_size(int u, int p=-1)
Utility function to compute sub-tree sizes.
Definition: heavy_light_decomposition.cpp:101
main
int main()
Definition: interpolation_search.cpp:37
add
std::string add(std::string a, std::string b)
Definition: string_fibonacci.cpp:24
std::make_pair
T make_pair(T... args)
std::time
T time(T... args)
main
int main()
Definition: addition_rule.cpp:30
toupperRoman
std::string toupperRoman(int n)
Definition: decimal_to_roman_numeral.cpp:58
LIMS
#define LIMS
Definition: qr_eigen_values.cpp:20
std::string::end
T end(T... args)
bayes_AgivenB
double bayes_AgivenB(double BgivenA, double A, double B)
Definition: bayes_theorem.cpp:14
FenwickTree::sum
int sum(int id)
Definition: fenwick_tree.cpp:54
std::setw
T setw(T... args)
main
int main()
Definition: quick_sort.cpp:82
std::max
T max(T... args)
test
static void test()
Function to test code using random arrays.
Definition: merge_insertion_sort.cpp:132
range_queries::heavy_light_decomposition::Tree::change_root
void change_root(int new_root)
Set the root for the tree.
Definition: heavy_light_decomposition.cpp:167
FenwickTree::FenwickTree
FenwickTree(int x)
Definition: fenwick_tree.cpp:39
Point::Point
Point(double a=0.f, double b=0.f)
Definition: smallest_circle.cpp:23
main
int main()
Definition: primality_test.cpp:31
range_queries::heavy_light_decomposition::HLD::h_label
std::vector< int > h_label
stores the label of a node
Definition: heavy_light_decomposition.cpp:339
list::next
struct list * next
pointer to next link in the chain
Definition: hash_search.cpp:31
tower::top
int top
top tower ID
Definition: tower_of_hanoi.cpp:15
Point
Definition: line_segment_intersection.cpp:12
TH
void TH(int n, tower *From, tower *Using, tower *To)
Definition: tower_of_hanoi.cpp:52
interpolation_search
int interpolation_search(int arr[], int value, int len)
Definition: interpolation_search.cpp:15
push
void push(char ch)
push byte to stack variable
Definition: paranthesis_matching.cpp:26
main
int main()
Definition: bogo_sort.cpp:104
test_2
static void test_2()
Definition: pigeonhole_sort.cpp:88
main
int main()
Definition: merge_sort.cpp:102
pop
char pop()
pop a byte out of stack variable
Definition: paranthesis_matching.cpp:29
InterpolationSearch
int InterpolationSearch(int A[], int n, int x)
Definition: interpolation_search2.cpp:15
horspool
Functions for Horspool's algorithm.
std::cin
poisson_expected
double poisson_expected(double rate, double time)
Definition: poisson_dist.cpp:25
poisson_x_successes
double poisson_x_successes(double expected, double x)
Definition: poisson_dist.cpp:46
main
int main(void)
Definition: rabin_karp.cpp:105
std::random_shuffle
T random_shuffle(T... args)
sorting::quickSort
void quickSort(int arr[], int low, int high)
Definition: quick_sort.cpp:63
std::unordered_map
STL class.
std::numeric_limits
std::array::data
T data(T... args)
string_search::getFailureArray
std::vector< int > getFailureArray(const std::string &pattern)
Definition: knuth_morris_pratt.cpp:33
show_pascal
void show_pascal(int **arr, int n)
Definition: pascal_triangle.cpp:18
string_search::rabin_karp
int rabin_karp(const std::string &str, const std::string &pat)
Definition: rabin_karp.cpp:83
get_input
void get_input()
Definition: ternary_search.cpp:36
PointInCircle
bool PointInCircle(const std::vector< Point > &P, const Point &Center, double R)
Definition: smallest_circle.cpp:72
std::getchar
T getchar(T... args)
tests
void tests()
Definition: comb_sort.cpp:73
list
Definition: list_array.cpp:8
std::memset
T memset(T... args)
strings::horspool::findShiftTable
std::unordered_map< char, int > findShiftTable(const std::string &prototype)
Definition: horspool.cpp:26
range_queries::heavy_light_decomposition::Tree::t_depth
std::vector< int > t_depth
a vector to store the depth of a node,
Definition: heavy_light_decomposition.cpp:88
binomial_variance
double binomial_variance(double n, double p)
Definition: binomial_dist.cpp:29
machine_learning::sum
T sum(const std::vector< std::valarray< T >> &A)
Definition: vector_ops.hpp:232
std::next
T next(T... args)
main
int main()
Definition: graph_coloring.cpp:96
sorting::shell_sort
void shell_sort(std::vector< T > *arr)
Definition: shell_sort2.cpp:75
std::pow
T pow(T... args)