CSCI570_Final_Project

The project is the c++ implementation of the two different solutions provided in chapter 6 of the Kleinberg textbook for the Sequence Alignment problem (see project description).

• Basic implementation
• Memory efficient implementation
• Shell scripts
• Graphs
• Summary

Compile & Run

# Compile and run basic program
./run_basic.sh

# Compile and run efficient program
./run_efficient.sh

Measure time & memory performance

# Measure programs and write metrics into the corresponding output files
# %e - Elapsed real time (in seconds).
# %M - Maximum resident set size of the process during its lifetime (in Kbytes).

# Measure basic program
/usr/bin/time -a -f "%e\n%M" -o ../data/output_basic.txt ./basic ../data/input.txt

# Measure efficient program
/usr/bin/time -a -f "%e\n%M" -o ../data/output_efficient.txt ./efficient ../data/input.txt

Graphs

gnuplot --persist ../graphs/time_plot.p

gnuplot --persist ../graphs/memory_plot.p

Note

The optimal table is unique but the optimal alignment is not unique