Git Product home page Git Product logo

2024-group-04-collaboration-practice's Introduction

Algorithms-And-Data-Structures

GitHub stars GitHub forks GitHub license

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.

algorithms

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.

  1. 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.

  1. Build the project:
make

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

  1. 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

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

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

2024-group-04-collaboration-practice's People

Contributors

mahnaznabizada avatar sediqem avatar han4573 avatar mahdig7 avatar zainab-hussaini avatar samim772 avatar colevanderswands avatar

Watchers

avatar

2024-group-04-collaboration-practice's Issues

Challenge: Knigt tour

Given a chessboard of size n x n, find all sequences of moves of a knight on the chessboard such that the knight visits every square only once. The size of the chessboard n is given as input.

Challenge: add_string_numbers

this program is adding two string numbers together and returning the result as a string. those two string numbers can be float or integer

Challenge: test_hash_table

This code defines a set of unit tests for the HashTable class. Here's a summary:

  1. Import Statements:

    • Imports the HashTable class from the src.hash_table module.
    • Imports the TestCase class from unittest.
    • Imports the unittest module.

  2. Test Case Class:

    • Defines a test case class named TestHashTable that inherits from unittest.TestCase.

  3. Test Methods:

    • test_add: Tests the add method of the HashTable class by adding elements and checking if the size is as expected.
    • test_contains: Tests the contains method of the HashTable class by checking if certain elements are present or not.
    • test_remove: Tests the remove method of the HashTable class by removing elements and checking if the size is updated.
    • test_remove_exception: Tests the remove method with an exception scenario.
    • test_access_operator: Tests the access operator ([]) of the HashTable class for adding and retrieving elements.
    • test_access_operator_exception: Tests the access operator with an exception scenario.
    • test_clear: Tests the clear method of the HashTable class by clearing the hash table and checking if the size is zero.
    • test_string_key: Tests the HashTable class with string keys.

  4. Test Data:

    • Various test cases include different operations on the HashTable class, such as adding, removing, and accessing elements.

  5. Assertion Statements:

    • Uses self.assertEqual and self.assertTrue methods to check if the actual output matches the expected output.

  6. Running Tests:

    • The script checks if it's being run directly (if __name__ == "__main__":) and, if so, runs the tests using unittest.main().

In summary, this code sets up and executes unit tests for various methods of the HashTable class, checking if the class behaves as expected for different scenarios and input data.

Challenge: Score After Flipping Matrix

We are given a matrix that contains only 0s and 1s. Each row represents a binary number. We can flip any number of rows and columns. We want to maximize the sum of the numbers in the matrix after flipping

Challenge: binary_tree_right_side_view

This code defines a set of unit tests for the right_side_view function, which seems to be related to a binary tree. Here's a summary:

  1. Import Statements:

    • Imports the unittest module.
    • Imports the TreeNode class and the right_side_view function from the src.binary_tree_right_side_view module.

  2. Test Case Class:

    • Defines a test case class named TestBinaryTreeRightSideView that inherits from unittest.TestCase.

  3. Test Methods:

    • test_full_tree: Tests the right_side_view function with a full binary tree and checks if the actual output matches the expected output.
    • test_empty_tree: Tests the right_side_view function with an empty tree and checks if the actual output matches the expected output.
    • test_single_node_tree: Tests the right_side_view function with a tree containing a single node and checks if the actual output matches the expected output.
    • test_right_skewed_tree: Tests the right_side_view function with a right-skewed tree and checks if the actual output matches the expected output.
    • test_left_skewed_tree: Tests the right_side_view function with a left-skewed tree and checks if the actual output matches the expected output.

  4. Test Data:

    • Various test cases include different binary tree structures defined using the TreeNode class.
    • The expected results (expected) are predefined lists of integers representing the right side view of the corresponding trees.

  5. Assertion Statements:

    • Each test method uses the self.assertEqual method to compare the actual output of right_side_view with the expected output.

  6. Running Tests:

    • The script checks if it's being run directly (if __name__ == "__main__":) and, if so, runs the tests using unittest.main().

In summary, this code sets up and executes unit tests for the right_side_view function with different binary tree scenarios, checking if the function produces the expected results for the right side view of the trees.

Challenge: generating_words

This code defines a set of unit tests for the generate_words function. Here's a summary:

  1. Import Statements:

    • Imports the generate_words function from the src.generate_words module.
    • Imports the unittest module.

  2. Test Case Class:

    • Defines a test case class named TestGenerateWords that inherits from unittest.TestCase.

  3. Test Methods:

    • test_3x3_board: Tests the generate_words function with a 3x3 board and a word dictionary. It checks if the actual output matches the expected output.
    • test_empty_board: Tests the generate_words function with an empty board and an empty word dictionary. It checks if the actual output matches the expected output.
    • test_empty_word_dict: Tests the generate_words function with a non-empty board and an empty word dictionary. It checks if the actual output matches the expected output.

  4. Test Data:

    • Various test cases include different combinations of boards (board) and word dictionaries (word_dict).
    • The expected results (expected) are predefined tuples of strings.

  5. Assertion Statements:

    • Each test method uses the self.assertEqual method to compare the actual output of generate_words with the expected output. The sorted function is used to ensure the order of elements doesn't affect the comparison.

  6. Running Tests:

    • The script checks if it's being run directly (if __name__ == "__main__":) and, if so, runs the tests using unittest.main().

In summary, this code sets up and executes unit tests for the generate_words function with different input scenarios, checking if the function produces the expected results.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.