In his landmark book on the fundamentals of computer programming, neatly titled Algorithms + Data Structures = Programs, Niklaus Wirth stresses the power and importance of recursion as “evidently lies in the possibility of defining an infinite set of objects by a finite statement.” Standing on the shoulders of giants, the goal of this set of computer experiments is to introduce to the students the basics of data structures and recursive algorithms using rudimentary graph-theoretic problems as a vehicle.
In the experiments, the students shall learn the basic data structures and recursive algorithms for solving a special class of graph isomorphism problems, as well as its applications in compiler optimization. At the end of the experiments, each student needs to turn in a report that includes experimental results and answers to a set of questions posed in the handout.
基本的に下記の日程で実習を進める。
Graph theory
Overview of this set of experiments
Review of graph theory and graph representations
Basic data structures for handling graphs
質疑応答
Basic algorithms for computing graph isomorphisms
Prototype implementation in C
Introduction to term unification
Connection with graph isomorphism problems