Algorithms-And-Data-Structures

This repository contains a collection of projects in C++ and Python that implement various data structures and algorithms. The projects are organized by language and topic, and include detailed explanations and examples to help you understand how they work.

About

Ever since I first tackled Algorithms and Data Structures at university in 2015, I've found it super useful to regularly go back to the basics. This becomes even more important when you're trying to learn a new programming language - a strong foundation is key. To help others, I've decided to share my code and notes on the subject with everyone.

My code is written in two programming languages I really enjoy, C++ and Python. I've done my best to stick to the latest best practices. Alongside the code, you'll find the notes I made while learning. These notes give more context and could be really handy for anyone new to Algorithms and Data Structures.

Requirements

The following requirements are necessary to build and run the code in this repository:

• For C++ projects:
  • A C++ compiler supporting C++14
  • CMake 3.15 or later
• For Python projects:
  • Python 3.10 or later

No additional libraries or modules are required.

Running the Examples

This repository is organized into distinct algorithm implementations, each contained in its own subdirectory. These subdirectories provide the source code, unit tests, and build configuration files necessary for each algorithm. Because each algorithm forms a separate project, you should handle the build and test processes individually.

Building and Testing C++ Projects

Building and testing C++ projects involve a sequence of steps. Here's a detailed walkthrough:

1. Navigate to the project directory: Start by moving into the directory containing the specific project you want to build and test.

2. Create and navigate into the build directory:

mkdir -p build && cd build

This command creates a new directory named build (if it doesn't already exist) and then navigates into it. The build directory is where the output files of the build process will be stored.

3. Generate the build files with CMake:

cmake ..

This command runs CMake to generate the build files. .. tells CMake to look for the CMakeLists.txt file in the directory above build.

4. Build the project:

make

This command compiles the source code using the instructions specified in the CMakeLists.txt file.

5. Run the unit tests:

ctest --verbose

The ctest --verbose command executes the unit tests and uses the verbose flag to provide a detailed output.

Testing Python Projects

To test a Python project, execute the following command in the project directory:

python -m unittest discover -v

This command uses Python's built-in unittest module to discover and run the tests. The -v (verbose) flag is used to get more detailed output from the tests.

Using the Testing Utility Script

For convenience, this repository includes a utility script named run_tests.sh. Execute the following commands from the repository's root to run tests in all subprojects:

• To run all unit tests: ./run_tests.sh
• To run all Python tests: ./run_tests.sh --python
• To run all C++ tests: ./run_tests.sh --cpp
• To read all options from terminal: ./run_tests.sh --help

Code Formatting Conventions

Consistent code formatting is essential for maintaining readability and understanding of the codebase. Therefore, we have adopted specific formatting guidelines for each programming language used in this repository.

C++ Formatting

We adhere to the Google C++ Style Guide. To automatically format the code, we use clang-format. Use the following command to format your code:

find . -regex '.*\\.(cpp|hpp|cu|c|h)' -exec clang-format -style=file -i {} \\;

This command recursively finds all files with .cpp, .hpp, .cu, .c, or .h extensions and formats them using clang-format.

CMake Formatting

CMake files should have a consistent style as well. For this, we use cmake-format. To format a CMakeLists.txt file, execute the following command:

cmake-format CMakeLists.txt -i

This command applies the cmake-format to the CMakeLists.txt file.

Python Formatting

We follow the PEP 8 - Style Guide for Python Code for Python projects and use black to automatically format the code. Use the following command to format your Python code:

black .

This command formats all Python files in the current directory and its subdirectories using black.

Notes

• Basic concepts.
• Data structures.
• Graph algorithms.
• Backtracking.
• Dynamic programming.
• Sorting.
• Brain teasers.

List of projects

Data structures

#	Structure	Implementation
1	Linked List	Python	Cpp
2	Vector	Python	Cpp
3	Stack	Python	Cpp
4	Queue	Python	Cpp
5	Heap	Python	Cpp
6	Binary Search Tree	Python	Cpp
7	Avl Tree	Python	Cpp
8	Red Black Tree	Python	Cpp
9	Hash Table	Python	Cpp

Graphs

#	Algorithm	Implementation
1	General graph	Python	Cpp
1	Is Bipartite?	Python	Cpp
2	BFS	Python	Cpp
3	DFS	Python	Cpp
4	Dijkstra	Python	Cpp
5	A*	Python	Cpp
6	Bellman-Ford	Python	Cpp
7	Kruskal	Python	Cpp
8	Prim	Python	Cpp

Backtracking

#	Problem	Solution
1	Permutations	Python	Cpp
2	Combinations	Python	Cpp
3	String Pattern	Python	Cpp
4	Generating words	Python	Cpp
5	K-colorable configurations	Python	Cpp
6	Hamiltonian paths	Python	Cpp
7	Knigt tour	Python	Cpp
8	Topological orderings	Python	Cpp
9	Tic-tac-toe (minimax)	Python	Cpp

Dynamic Programming

#	Problem	Solution
1	Fibonacci	Python	Cpp
2	Grid travelers	Python	Cpp
3	Stairs	Python	Cpp
4	Can sum	Python	Cpp
5	How sum	Python	Cpp
6	Best sum	Python	Cpp
7	Can construct	Python	Cpp
8	Count construct	Python	Cpp
9	All construct	Python	Cpp
10	Coins	Python	Cpp
11	Longest increasing subsequence	Python	Cpp
12	Longest common subsequence	Python	Cpp
13	Knuth-Morris-Pratt	Python	Cpp
14	Minimum insertions to form a palindrome	Python	Cpp

Sorting

#	Algorithm	Implementation
1	Insertion sort	Python	Cpp
2	Selection sort	Python	Cpp
3	Heap sort	Python	Cpp
4	Merge sort	Python	Cpp
5	Quick sort	Python	Cpp

Brain Teasers

#	Problem	Solution
1	Minimum deletions to make valid parentheses	Python	Cpp
2	Is palindrome after at most one char deletion?	Python	Cpp
3	K closest points to origin	Python	Cpp
4	Subarray sum equals K	Python	Cpp
5	Add numbers given as strings	Python	Cpp
6	Dot product of two sparse vectors	Python	Cpp
7	Range sum of BST	Python	Cpp
8	Product of array except self	Python	Cpp
9	Convert BST to sorted doubly linked list	Python	Cpp
10	Lowest common ancestor of a binary tree	Python	Cpp
11	LRU Cache	Python	Cpp
12	Randomize An Array	Python	Cpp
13	Binary Tree Right Side View	Python	Cpp
14	Design Browser History	Python	Cpp
15	Score After Flipping Matrix	Python	Cpp

Clearing Solutions

For convenience, this repository includes a utility script named clear_solutions.sh that will erase all Python and/or C++ solutions so you can solve and document the challenges yourself. Test cases and helper files will not be cleared. You can optionally clear all challenge READMEs to document your own solutions.

Execute the following commands from the repository's root to clear solutions:

• To read all options from terminal: ./clear_solutions.sh or ./clear_solutions.sh --help
• To clear all Python solutions: ./clear_solutions.sh --python
• To clear all C++ solutions: ./clear_solutions.sh --cpp
• To clear all C++ and Python solutions: ./clear_solutions.sh --cpp --python
• To clear READMEs for selected langauge(s): ./clear_solutions.sh --<language> --readme

References

• L. V. Narashima Prasad, E. Kishna Rao Patro "Lecture Notes on Data Structures using C"
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. "Introduction to Algorithms, 3rd Edition (The MIT Press)"
• Steven Halim "Competitive Programming 3"
• Narasimha Karumanchi "Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles"
• Brian Kernighan, Dennis Ritchie "The C Programming Language"
• Steven Skiena, Miguel Revilla "Programming Challenges: The Programming Contest Training Manual"
• Antti Laaksonen " Guide to Competitive Programming: Learning and Improving Algorithms Through Contests (Undergraduate Topics in Computer Science) "
• Nite Nimajneb "The Hitchhiker’s Guide to the Programming Contests"
• http://cslibrary.stanford.edu/
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/lecture-slides-and-files/index.htm
• https://www.cs.bham.ac.uk/~jxb/DSA/
• https://www.ics.uci.edu/~eppstein/161/syl.html
• http://www.columbia.edu/~cs2035/oldcourses.html
• https://www.cs.auckland.ac.nz/courses/compsci220s1t/lectures/lecturenotes/GG-lectures/
• https://sp19.datastructur.es/
• https://www.csc.kth.se/~viggo/problemlist
• https://cp-algorithms.com/
• https://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
• https://codeahoy.com/learn/cprogramming/toc/

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

Please make sure to update tests as appropriate.

License

MIT