|
Department of Computer Science
Theory of Computer Algorithms (Winter 2008) 4005-800-01 (Calendar Description) |
Instructor: Richard Zanibbi, Office hours: Tues 2-4pm, Thursday 10am-12pm (or by appointment), 70-3551 (Golisano College)
Lectures (NOTE: two locations):
Mondays 12-1:50pm (70-2590, Golisano College)
Wednesdays 12-1:50pm (70-3435, Golisano College)
In Assignment 1, you implemented Dijkstra's shortest path algorithm. For the project, you will use brute force and dynamic programming algorithms to find shortest paths for string alignments (e.g. for aligning DNA sequences) and graphs with negative edge costs (e.g. for a financial investment model where there are both potential costs and profits).
You will implement four algorithms, using Java or C++; if you work in Java, you are welcome to use any of the code posted as part of the solution to Assignment 1. Otherwise, all of the code must be your own.
You will then write a report that summarizes experiments in which you compare your algorithms on test data, focusing on space and time usage. Your report should also examine the relationship between the observed time and space utilizations of your implementations, and the asymptotic complexity of the algorithms themselves. In order to do this in a meaningful way, you will need to create test data for problem instances of different sizes and complexity.
You should use graphs and tables to summarize the experimental outcomes. It is recommended that before you write any code, you consider how your tables/plots will be structured, and what they will contain while designing your test cases (i.e. make sure to design an experiment, rather than produce an implementation and then create test inputs without a clear goal). Use LaTeX to produce your report, which should be at most 10 pages in length (10 point font).
This project is to be completed in groups of two.
When you have finished the project, email a .zip archive of your program's source code (remember to use the 'rit_' prefix in the filename). Submit a printed copy of your report at the start of class on Wed Feb 18 (Week 10). In addition to summarizing and analyzing results, the report should describe clearly how to run your individual programs and experiments.
We discussed in class how the string alignment problem may be understood as a shortest path problem (find the sequence (path) of operations with minimum cost). In Part One of the project, you will implement the following algorithms:
Design your programs so that they can compare DNA sequences (containing the letters G, A, C, and T). Your programs should be able to be parameterized for different costs of adding a blank (delta), and character mismatches (alpha costs, e.g. the cost of aligning G with A (alpha 1), versus G with C (alpha 2), etc.). To start you will probably want to count all mismatches using the same alpha (cost). As DNA sequences can get very long, have your programs compare two strings stored in text files.
In Part Two you will implement the Bellman-Ford algorithm for finding minimum cost paths in graphs with negative edge weights (but no negative cycles). Implement the following algorithms:
Graphs should be defined in text files using a format similar to that used in assignment one. For the project, nodes will be labeled using positive integers rather than letters (the solution for assignment one assumes that nodes are labeled using A through Z), for example,
1 2 5
1 3 -1
3 2 4
defines a graph with three nodes, with edges (1,2) of cost 5, (1,3) of cost -1, and (3,2) of cost 4. The goal (target) node should be the node with the largest integer label, in this example, node 3. Your programs should produce the minimum cost paths from all nodes in the graph to the goal node.
Important: the code in the solution for Assignment 1 allows graphs to be read in and converted to .dot files, which can then be used to visualize the graphs. You will probably want to modify this or create something similar to assist you in testing and debugging your programs.