helloFOSS-21-ContributiveProgramming

Hello There! This project is a part of Hello FOSS '21 : The Noble Edition. The repository contains CP problems from various topics based on the theme of social good, and our task will be creating solution files for the problems, along with some additional tasks like creating a grader, test-case generators etc which has been discussed later on.

CP! But what's different?

You will be solving problems similar to competitive programming contests, however this time you won't be competing! Instead you can collaborate on problems.

You can:

• Discuss Approaches
• Find and resolve bugs in the code provided/ each others' code
• Write programs to generate new test cases
• Build an autograder

Guidelines

The topics have been split into 2 sections - Basic and Advanced. The basic section is a great way to get started with CP (in a non-competitive environment!). For the advanced section, you are expected to have a decent understanding of basic data structures and algorithms. However, don't worry if you don't know all the algorithms. You are free to Google stuff or collaborate on problems, as long as the implementation is yours.

The following is the list of topics. Please refer to the READMEs in the individual directories to understand the problem statement and input-output format.

Basic

1. Binary Search
2. Sorting
3. Minimum Stack
4. Dynamic Programming
5. Number Theory :
   • Sieve of Eratosthenes (in linear time)
   • Extended Euclid's Algorithm

Advanced

1. Sweep Line Algorithms
2. Disjoint Set Union
3. Lowest Common Ancestor
4. Knuth-Morris-Pratt Algorithm for Pattern Matching
5. Compression using Huffman Encoding
6. AVL Trees

Need a challenge? Try implementing Deletion in B-Trees!

Build a grader

You need to build a grader which takes 3 filenames as a command line argument : The solution file(.cpp), the input file(containing the test cases) and the expected output file(output.txt, which has not been provided in the repository).

The grader should be able to run the testcases on the solution file and compare the output with the expected output file. Also, make sure to handle extra whitespaces, as long as the outputs are correct, extra newlines or spaces shouldn't matter. You can code the grader in any programming language that you wish.

Join our Discord server for all related discussions.