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) {
            // add vertex to solution
            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++) {
                if (adjacency[row][col] == 1) {

                    // 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