Search

Search Results

• Teaching graph algorithms with Visage

  35-50

  Andreas Fest

  Ulrich Kortenkamp

  Views:

  16

  Combinatorial optimization is a substantial pool for teaching authentic mathematics. Studying topics in combinatorial optimization practice different mathematical skills, and because of this have been integrated into the new Berlin curriculum for secondary schools. In addition, teachers are encouraged to use adequate teaching software. The presented software package "Visage" is a visualization tool for graph algorithms. Using the intuitive user interface of an interactive geometry system (Cinderella), graphs and networks can be drawn very easily and different textbook algorithms can be visualized on the graphs. An authoring tool for interactive worksheets and the usage of the build-in programming interface offer new ways for teaching graphs and algorithms in a classroom.

• The single-source shortest paths algorithms and the dynamic programming

  25-35

  Zoltán Kátai

  Views:

  25

  In this paper we are going to present a teaching—learning method that help students look at three single-source shortest paths graph-algorithms from a so called "upperview": the algorithm based on the topological order of the nodes, the Dijkstra algorithm, the Bellman-Ford algorithm. The goal of the suggested method is, beyond the presentation of the algorithms, to offer the students a view that reveals them the basic and even the slight principal differences and similarities between the strategies. In order to succeed in this object, teachers should present the mentioned algorithms as cousin dynamic programming strategies.

• Linear clause generation by Tableaux and DAGs

  109-118

  Gergely Kovásznai

  Views:

  24

  Clause generation is a preliminary step in theorem proving since most of the state-of-the-art theorem proving methods act on clause sets. Several clause generating algorithms are known. Most of them rewrite a formula according to well-known logical equivalences, thus they are quite complicated and produce not very understandable information on their functioning for humans. There are other methods that can be considered as ones based on tableaux, but only in propositional logic. In this paper, we propose a new method for clause generation in first-order logic. Since it inherits rules from analytic tableaux, analytic dual tableaux, and free-variable tableaux, this method is called clause generating tableaux (CGT). All of the known clause generating algorithms are exponential, so is CGT. However, by switching to directed acyclic graphs (DAGs) from trees, we propose a linear CGT method. Another advantageous feature is the detection of valid clauses only by the closing of CGT branches. Last but not least, CGT generates a graph as output, which is visual and easy-to-understand. Thus, CGT can also be used in teaching logic and theorem proving.

• Brute force on 10 letters

  183-193

  Zoltán Kovács

  István Hudi

  Views:

  26

  We deal with two problems in the set of 10-character-long strings. Both problems can be solved by slightly different methods, but our approach for each is brute force. As we point out, there can be differences in effectivity even in different brute force algorithms. As an additional result, we answer an open question of Raymond Smullyan's.