Graph theory in an undergraduate lower-division computer science algorithms course
Mary Courtney Fleming · 1991
Since the field of computer science has grown dramatically, a need exists to design good curricula. Much has been written about teaching programming courses, but less discussion has taken place concerning algorithms courses. In preparing to teach an algorithm, the teacher must be concerned with motivating the students, eliciting an algorithm from the students, and deciding on a good data structure. The field of graph theory offers fascinating algorithms to teach. Unfortunately, it is only recently that the study of graph theory and discrete mathematics has been established in college curricula. Therefore, many of the faculty in computer science have modest backgrounds in this field. With this in mind, the author wrote a sourcebook on graph theory to aid faculty in preparing their lectures for a computer science algorithms course. Included in the sourcebook are historical anecdotes, problems for classwork and homework, different types of mathematical proofs, techniques for teaching algorithms, and a Pascal program demonstrating the algorithms. The sourcebook contains such topics as isomorphism, computer representation of graphs, planar graphs, graph traversals, Euler and Hamilton circuits, graph coloring, minimum spanning tree algorithms, Dijkstra's shortest path algorithm, topological sort and efficiency and classification of algorithms. The sourcebook was submitted to two different juries for evaluation. The first jury, consisting of computer science faculty from Pace University, used the book as a reference for their lectures during the spring semester of 1990. The second jury, consisting of mathematics and computer science faculty in the metropolitan area, performed a critical reading. Both juries responded to the same survey asking technical, pedagogical and theoretical questions. Most jury members agreed to the combining of the mathematical and computing aspects of graph theory in an algorithms course. There was some disagreement as to the use of tracing code during class. A few jury members preferred leaving an algorithm in pseudo-code. Others felt that for some algorithms the students needed the detailed explanation of executable code. The teaching of efficiency of algorithms and NP completeness is difficult, yet the graph theory offers rich examples for this topic. All of the jury members were grateful for the opportunity to discuss pedagogy.