The project contains the following files:
-
Final_Paper.pdf
- The analysis performed on all algorithms, written in Romanian using LateX
-
algo.h
- Contains a description of the prototype of a function that solves the problem.
-
main.cpp
- The source contains the implementation of the read and output functions.
- Its main role is to process the data received by the function that solves the LCA and to display the results.
-
lca_disjoint-set.cpp
- Contains a class that implements the most important functionalities of the data structure of disjoint set forests.
- Contains the solution of the LCA problem with an iterative implementation of Tarjan's algorithm.
-
lca_rmq.cpp
- Contains the solution of the LCA problem by reducing it to the RMQ problem.
- euler_tour makes the euler representation of the tree and calculates the levels on which each node is.
- rmq_sparse_table applies the dynamic programming method to preprocess the information needed for answers.
-
Makefile
- build rule builds both solution implementations.
- run_tests rule only runs the checker
-
Folder 'in' with the entrance tests on infoarena
- Each test is called "testID.in", where ID is the number test (e.g. test0.in)
- Each test is structured as follows:
- On the first line, N (int - number of nodes in the tree), M (int - number of queries)
- N-1 pairs of integers, representing the edges of the graph
- M pairs of numbers, representing a query
- The root of the graph is node 1.
- N, M <= 10 ^ 6
-
Folder 'out' with the output tests generated by one of the two implementations
- Each test will be named "testID.out", where ID is the test number (e.g. test0.out)
- Each test will contain the answers to the M queries.
-
Folder 'ok'
- Contains the correct results for each test in the 'in' folder
-
'Other_tests' folder contains tests generated with an Octave script
- test generator source code used
- I did not generate more than 6 tests due to the memory occupied by each of them
-
The 'checker' folder (contains sources inspired by this homework, but has been modified)
- check_one_test.sh tests the running of a single program and compares the results with a reference test, it has the option of analyzing the memory used, but I did not call it in tests due to the long running time
- check_tests.sh verifies the integrity of tests and the program by running tests within a certain range
- checker.sh does a static code analysis and runs tests on the https://infoarena.ro to verify correctness