CSCI570_Fall22_Project
CSCI-570 Fall 2022
Analysis of Algorithms
Copyright By PowCoder代写 加微信 powcoder
Final Project
Due: December 8, 2022
I. Guidelines
The project is related to the implementation of the two different solutions discussed in
Week 8 of the Lecture for the Sequence Alignment problem. You can work on this
project in groups of no more than 3 people.
II. Project Description
Implement the basic Dynamic Programming solution to the Sequence Alignment
problem. Run the test set provided and show your results.
A. Algorithm Description
Suppose we are given two strings and , where consists of the sequence of𝑋 𝑌 𝑋
symbols and consists of the sequence of symbols .𝑥
, … , 𝑥
, … , 𝑦
Consider the sets and as representing the different{1, 2, … , 𝑚} {1, 2, … , 𝑛}
positions in the strings and , and consider a matching of these sets; Recall that𝑋 𝑌
a matching is a set of ordered pairs with the property that each item occurs in at
most one pair. We say that a matching of these two sets is an alignment if there𝑀
are no “crossing” pairs: if , and , then . Intuitively,(𝑖, 𝑗) (𝑖’, 𝑗’) ϵ 𝑀 𝑖 < 𝑖' 𝑗 < 𝑗'
an alignment gives a way of lining up the two strings, by telling us which pairs of
positions will be lined up with one another.
Our definition of similarity will be based on finding the optimal alignment
between and , according to the following criteria. Suppose is a given𝑋 𝑌 𝑀
alignment between and :𝑋 𝑌
1. First, there is a parameter that defines a gap penalty. For eachδ
position of or that is not matched in — it is a gap — we incur a cost𝑋 𝑌 𝑀
2. Second, for each pair of letters in our alphabet, there is a mismatch𝑝, 𝑞
cost of for lining up with . Thus, for each , we pay theα
𝑝 𝑞 (𝑖, 𝑗) ϵ 𝑀
appropriate mismatch cost for lining up with . One generallyα
assumes that = 0 for each letter —there is no mismatch cost to line upα
a letter with another copy of itself—although this will not be necessary in
anything that follows.
3. The cost of is the sum of its gap and mismatch costs, and we seek an𝑀
alignment of minimum cost.
B. Input string Generator
The input to the program would be a text file containing the following
information:
1. First base string ( )𝑠
2. Next lines consist of indices after which the copy of the previous𝑗
string needs to be inserted in the cumulative string. (eg given below)
3. Second base string ( )𝑠
4. Next lines consist of indices after which the copy of the previous𝑘
string needs to be inserted in the cumulative string. (eg given below)
This information would help generate 2 strings from the original 2 base strings.
This file could be used as an input to your program and your program could use
the base strings and the rules to generate the actual strings. Also note that the
numbers and correspond to the first and the second string respectively. Make𝑗 𝑘
sure you validate the length of the first and the second string to be 2
and . Please note that the base strings need not have to be of equal2
length and similarly, need not be equal to .𝑗 𝑘
Using the above numbers, the generated strings would be
ACACTGACTACTGACTGGTGACTACTGACTGG and
TATTATACGCTATTATACGCGACGCGGACGCG
Following is the step by step process on how the above strings are generated.
ACTGACTACTGACTGG
ACACTGACTACTGACTGGTGACTACTGACTGG
TATTATACGCGACGCG
TATTATACGCTATTATACGCGACGCGGACGCG
C. Values for Delta and Alphas
Values for ’s are as follows. is equal to 30.α δ
A 0 110 48 94
C 110 0 118 48
G 48 118 0 110
T 94 48 110 0
D. Programming/Scripting Languages
Following are the list of languages which could be used:
5. Python3
1. Basic Algorithm
0 <= 𝑗, 𝑘 <= 10
1 <= 𝑙𝑒𝑛(𝑠
2. Memory Efficient Algorithm
0 <= 𝑗, 𝑘 <= 20
1 <= 𝑙𝑒𝑛(𝑠
) <= 20000
) <= 20000
III. Goals
Following are the goals to achieve for your project
A. Your program should take 2 arguments
1. input file path
2. output file path (If path is valid and file not found, your program should
create it)
`python2 basic_2.py input.txt output.txt`
`java Basic input.txt output.txt`
`python3 basic_3.py input.txt output.txt`
Note: As mentioned in Part II-B input file will have data to generate strings. Since
Gap penalty and Mismatch penalty are FIXED, you have to hardcode(δ
them in your program.
You are not allowed to use any libraries.
B. Implement the Dynamic Programming algorithm. Your program should print the
following information at the respective lines in output file:
1. Cost of the alignment (Integer)
2. First string alignment ( Consists of A, C, T, G, _ (gap) characters)
3. Second string alignment ( Consists of A, C, T, G, _ (gap) characters )
4. Time in Milliseconds (Float)
5. Memory in Kilobytes (Float)
Note: There can be multiple alignments which have the same cost. You can print
ANY alignment generated by your program. The only condition is it should have a
minimum cost.
e.g. For strings : A and : C, alignments A_, _C and _A, C_ both have𝑠
alignment cost 60 which is minimum. You can print any one of them.
C. Implement the memory efficient version of this solution and repeat the tests in
D. Plot the results of Part B and Part C using a line graph
Please use the provided input files in the ‘datapoints’ folder for generating the data
points to plot the graph.
1. Single plot of CPU time vs problem size for the two solutions.
2. Single plot of Memory usage vs problem size for the two solutions.
Units: CPU time - milliseconds, Memory in KB, problem size m+n
IV. Submission
A. You should submit the ZIP file containing the following files.
a. Basic algorithm file
Name of the program file should be ‘basic.c’ / ‘basic.cpp’ / ‘Basic.java’ /
‘basic_2.py’ (Python 2.7) / ‘basic_3.py’ (Python 3)
b. Memory efficient algorithm file
Name of the program file should be ‘efficient.c’ / ‘efficient.cpp’ /
‘Efficient.java’ / ‘efficient_2.py’ (Python 2.7) / ‘efficient_3.py’ (Python 3)
c. Summary.pdf
It must contain following details
1. datapoints output table (which are generated from provided input
2. Two graphs and Insights
3. Contribution from each group member e.g.coding, testing, report
preparation, etc if everybody did not have equal contribution
(Please use the provided Summary.docx file, fill in the details and upload it
d. 2 Shell files ‘basic.sh’ and ‘efficient.sh’ with the commands to compile and
run your basic and efficient version. These are needed to provide you
flexibility in passing any additional compiler/run arguments that your
programs might need. See More Hints (VII part E for more details)
javac Basic.java
java Basic “$1” “$2”
Execution: ./basic.sh input.txt output.txt
./efficient.sh input.txt output.txt
B. The name of your zip file should have the USC IDs (not email ids) of everyone in
your group separated by underscore. e.g.
- 1234567890_1234567890_1234567890.zip
- 1234567890_1234567890_1234567890
- basic_2.py
- efficient_2.py
- Summary.pdf
- basic.sh
- efficient.sh
V. Grading
Please read the following instructions to understand how your submission will be
evaluated.
A. Correctness of algorithms - 70 points
1. Both programs (basic/ efficient) are correctly outputting file having all 5
lines in correct order: 15 points
2. Basic Algorithm: 25 points
3. Memory Efficient Algorithm: 30 points
Note: Graders will execute your program on the `Linux` OS. The goal of Part A is
to check correctness. The program should output valid alignment having minimum
cost. Memory and Time will be evaluated in Part B.
B. Plots, analysis of results, insights and observations: 30 points
1. Your program will be run on the input files (provided by us in the ‘data
points’ folder) to generate output files. The memory and time in the output
files should be in “close range” to what is given by you in the Summary.pdf
2. Correctness of the graph
3. Correctness of Analysis/ Insights
Note: Unlike Part A, evaluation of Part B is subjective so it will be done manually.
So it is alright if your graphs/data points have ‘some’ outliers.
VI. What is provided to you in the zip file?
A. SampleTestCases folder containing sample input and output files
B. Datapoint folder containing input files to generate graph data points.
C. Summary.docx file for reference
VII. HINTS, NOTES, and FAQs
A. Regarding Input and string generation
1. We will never give an invalid input to your program. Input strings will always
contain A, C, G, T only.
2. The length of the final input string should be equal to the
, as mentioned in the document.2
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑙𝑖𝑛𝑒𝑠
* 𝑙𝑒𝑛(𝑏𝑎𝑠𝑒 𝑠𝑡𝑟𝑖𝑛𝑔)
3. The string generation mechanism is the same irrespective of the basic or the
efficient version of the algorithm.
4. The entire program (string generation, solution, write output) should be written in a
single file. You may break those functions in different classes to make the code
modular, but there should be only one file. Your program won’t be evaluated based
on how modular it is.
B. Regarding Algorithm and output
1. DO NOT REFER TO THE PSEUDOCODE PROVIDED IN KLEINBERG AND
2. DO NOT USE ANY LIBRARIES FOR WRITING YOUR ALGORITHMS.
3. Samples for time and memory calculation are provided. Please use them for
consistency.
4. Your solutions for the regular and memory-efficient algorithms should be in two
different programs.
5. There can be multiple valid sequences with the same optimal cost, you can output
any of those. All of them are valid.
6. You should code both the basic version and memory-efficient algorithm. Even
though the memory-efficient version will pass all the bounds of the simple
version, You must not use the memory-efficient version in both of the
sub-problems.
7. Your program should not print anything when it runs. It should only write to the
output file.
8. There is no specific requirement for the precision of Time and Memory float
9. Time and Memory depend on so many factors such as CPU, Operating System,
etc. So there might be differences in the output. Therefore, it will be evaluated
subjectively. There must be a clear distinction in behavior between programs
whose Time/ Memory complexity is O(n) vs O(n2) vs O(logn).
C. Regarding the plot
1. Both the graphs are line graphs. X-axis represents problem size as m+n, where m
and n are lengths of the generated string and Y-axis of Memory plot represents
memory in KB, and Y-axis of Time Plot represents time in milliseconds. The 2
lines in the graph will represent stats of basic and memory-efficient algorithms.
2. You can use any libraries/packages in any language to plot the graphs.
3. You do not have to provide code for generating the plots. Only add images in the
Summary.pdf
D. Regarding Submission
1. Only 1 person in the group needs to submit the project. We’ll get the USC IDs of
all the other team members from the filenames.
2. To allow for grading the whole class in a reasonable amount of time, we’ll kill
your program if it runs for more than a minute on a single input file.
E. Regarding Shell File
To make the evaluation seamless on our end, please make sure you also have a shell script
named ‘basic.sh’ and ‘efficient.sh’ with the commands required to run your program. For
example, the contents of this file can be one of the following:
basic.sh gcc basic.c
./a.out "$1" "$2"
efficient.sh gcc efficient.c
./a.out "$1" "$2"
basic.sh g++ basic.cpp
./a.out "$1" "$2"
efficient.sh g++ efficient.cpp
./a.out "$1" "$2"
basic.sh javac Basic.java
java Basic "$1" "$2"
efficient.sh javac Efficient.java
java Efficient "$1" "$2"
python 2.7
basic.sh python2 basic_2.py "$1" "$2"
efficient.sh python2 efficient_2.py "$1" "$2"
basic.sh python3 basic_3.py "$1" "$2"
efficient.sh python3 efficient_3.py "$1" "$2"
Note that the above are just examples. You can modify them according to your
convenience. The goal is to have a language-independent mechanism to run your script to
get your outputs.
Also note that for python2 or python3 users, it's important that they have 2 or 3 suffixes at
F. Sample code for memory and time calculation
import sys
from resource import *
import time
import psutil
def process_memory():
process = psutil.Process()
memory_info = process.memory_info()
memory_consumed = int(memory_info.rss/1024)
return memory_consumed
def time_wrapper():
start_time = time.time()
call_algorithm()
end_time = time.time()
time_taken = (end_time - start_time)*1000
return time_taken
private static double getMemoryInKB() {
double total = Runtime.getRuntime().totalMemory();
return (total-Runtime.getRuntime().freeMemory())/10e3;
private static double getTimeInMilliseconds() {
return System.nanoTime()/10e6;
double beforeUsedMem=getMemoryInKB();
double startTime = getTimeInMilliseconds();
alignment = basicSolution(firstString, secondString, delta, alpha);
double afterUsedMem = getMemoryInKB();
double endTime = getTimeInMilliseconds();
double totalUsage = afterUsedMem-beforeUsedMem;
double totalTime = endTime - startTime;
#include
#include
#include
extern int errno;
// getrusage() is available in linux. Your code will be evaluated in
long getTotalMemory() {
struct rusage usage;
int returnCode = getrusage(RUSAGE_SELF, &usage);
if(returnCode == 0) {
return usage.ru_maxrss;
//It should never occur. Check man getrusage for more info to
// printf(“error %d”, errno);
return -1;
int main() {
struct timeval begin, end;
gettimeofday(&begin, 0);
//write your solution here
//Please call getTotalMemory() only after calling your solution
function. It calculates max memory used by the program.
double totalmemory = getTotalMemory();
gettimeofday(&end, 0);
long seconds = end.tv_sec – begin.tv_sec;
long microseconds = end.tv_usec – begin.tv_usec;
double totaltime = seconds*1000 + microseconds*1e-3;
printf(“%f\n”, totaltime);
printf(“%f\n”, totalmemory);
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com