# CST 370: Design and Analysis of Algorithms

Students learn important data structures in computer science and acquire fundamental algorithm design techniques to get the efficient solutions to several computing problems from various disciplines. Topics include the analysis of algorithm efficiency, hash, heap, graph, tree, sorting and searching, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, dynamic programming, and greedy programming.

## Sample Work

The code excerpt below illustrates the topological sorting algorithm based on the source-removal algorithm. The ts function is called after the client code reads in a user-defined file that represents an input graph (in this case, we assumed the input graph was always a directed acyclic graph or DAG).

``````void ts(vector<vector<int>> adjacency, vector<int> indegrees) {
// keep track of deleted vertices, which will be the solution
vector<int> solution;
// check if vertex is a source -- i.e. in-degree of 0
for (int row = 0; row < indegrees.size(); row++) {
if (indegrees[row] == 0) {
solution.push_back(row);
// Mark vertex as deleted
indegrees[row] = -1;
// Traverse column in adjacency matrix to identify edges for deletion
for (int col = 0; col < adjacency.size(); col++) {

// decrease in-degree by 1
indegrees[col] = indegrees[col] - 1;
}
}
// start from beginning vertex again
row = -1; // for loop will increment to row 0
}
}

// Print out results
cout << "Topological Order: " ;
for (int i = 0; i < solution.size() - 1; i++) {
cout << solution[i] << " -> ";
}
cout << solution[solution.size() - 1] << endl;

}``````

Two data structures are created from this input to be fed to the function–an adjacency matrix (vector) and a list of in-degrees for each vertex. The ts function takes these two parameters, and, in applying the topological sorting algorithm, outputs the topological order of the graph.

For example for the graph represented by the file t2.txt with the structure:

The algorithm would have the following output:

``````Enter filename: C:\\tmp\\t2.txt
Topological sort: 0 -> 1 -> 2 -> 3 -> 4``````