Skip to content

About

C++ implementations of graph, greedy, knapsack, prime sieve and string-matching algorithms, with sample inputs

Topics

Resources

Stars

5 stars

Watchers

1 watching

Forks

Latest commit

 

History

28 Commits

Folders and files

Repository files navigation

Data Structures and Algorithms in C++

A personal collection of C++ implementations of classic data structures and algorithms, written between 2022 and 2024 while learning DSA and competitive programming. It covers graph traversal and shortest paths, greedy scheduling, knapsack, prime sieves, string matching and a few STL examples. Most programs read from standard input, and several folders include sample inputs. Some comments in the prime-sieve files are in Bengali.

Contents

Graphs

File What it does
BFS/BFS.cpp Breadth-first search on an undirected graph. Prints the adjacency list, the visit order and the level of a destination node from the source.
DFS/DFS.cpp Depth-first traversal of an undirected graph with an explicit stack.
BellmanFord/BellmanFord_Graph.cpp Bellman–Ford on an adjacency list; reports a negative-weight cycle if there is one.
BellmanFord/Bellman_Ford_Vector.cpp Bellman–Ford on an edge list.
BellmanFord/nodes.txt Four test cases for the Bellman–Ford programs.
Dijstra/Dijkstra.cpp Dijkstra with a priority queue on a directed or undirected graph; prints every distance and the path to a chosen destination.
Dijstra/Dijkstra_Alphabet.cpp The same program with nodes named by lowercase letters.
Dijstra/Dijkstra_Fixed.cpp Adjacency-matrix Dijkstra on a fixed 9-vertex graph, from GeeksforGeeks (credited in the file).
Dijstra/Nodes.txt Test cases for the Dijkstra programs. Sample outputs: Solution.png and Solution_Alphabet.png.

Greedy and dynamic programming

File What it does
Job Sequence/Activity_Selection_Problem.cpp Activity selection: sorts activities by finish time and picks the non-overlapping ones. Activity_Selection_Problem_Char.cpp is the same program with <bits/stdc++.h>.
Job Sequence/Job_Sequence_With_Deadline.cpp Job sequencing with deadlines, taking the most profitable jobs first. Test input: Job_Sequence_With_Deadline.txt.
Knapsack/0_1_knapsack.cpp 0/1 knapsack with a bottom-up DP table.
Knapsack/Fractional_knapsack.cpp Fractional knapsack, greedy by profit-to-weight ratio.

Prime numbers

File What it does
0_Check_Prime.cpp Primality test by trial division over 6k ± 1.
1_Native_Sieve_of_Eratosthenes_with_sqare_optimization.cpp Sieve of Eratosthenes that starts crossing out at i², with timings up to 10⁹.
2_1_Sieving_till_root.cpp The same sieve with the outer loop stopping at √n.
2_2_Sieving_till_root_with_odd_only.cpp Sieves only odd numbers after handling 2, and prints the primes up to 1,000.
3_Segmented_Sieve.cpp Segmented sieve that counts the primes up to n in blocks of 10,000.
4_Linear_Sieve.cpp Linear sieve storing the lowest prime factor of every number up to 10⁸.
5_Bitwise_Sieve.cpp Bitwise sieve up to 10⁸; for the first n primes p, prints the p-th prime.
6_Factorization_SPF.cpp Smallest-prime-factor sieve and the factorisation of every number up to 10⁶.

Strings

File What it does
String/Aho_Corasick.cpp Aho–Corasick automaton that finds several patterns in one pass over the text.
String/KMP.cpp Knuth–Morris–Pratt search with the LPS (longest proper prefix-suffix) array.
String/Rabin_Karp.cpp Rabin–Karp search with a rolling hash.

STL, maths and other notes

File What it does
STL/Algorithm/next_permutation.cpp Prints every permutation of an array with std::next_permutation.
STL/Algorithm/prev_permutation.cpp The same in descending order with std::prev_permutation.
STL/Containers/vector.cpp Common std::vector operations: initialising, copying, min/max, sum, counting, finding, sorting and the erase-remove idiom.
Math/Sum_of_Reminders.cpp Sum of n mod i for i = 1 to m, modulo 10⁹ + 7, by grouping equal values of n / i.
Others/Datatypes.cpp Prints the ranges of the C++ integer and character types.
cpp.json VS Code C++ snippets: a competitive-programming template with debug helpers (include), an author header (author), a shorter template (sinclude), the bitwise sieve (bitwise_sieve), the SPF sieve (spfsieve) and a header list (headerfiles).

Getting started

The programs are single files. Several include <bits/stdc++.h>, so compile them with GCC's g++:

g++ -std=c++17 -O2 Dijstra/Dijkstra.cpp -o dijkstra
./dijkstra

Then paste one test case from the matching .txt file, without its "Test case" heading. To use the snippets, copy cpp.json into your VS Code user snippets for C++.

Author

Md Arik Rayhan — mdarikrayhan.com

About

C++ implementations of graph, greedy, knapsack, prime sieve and string-matching algorithms, with sample inputs

Topics

Resources

Stars

5 stars

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages