Topics for
		  GUI for Algorithms mini-project
			  by Yefim Dinitz


 I. Support of MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE course
    (for phisicists and economists)

1. Graph representation of relations.
   Hasse diagram. Topological sort algorithm.

2. Equations on binomial coefficients.


 II. GRAPH ALGORITHMS

1. Given two groups of k disjoint paths each, in a graph: (i) from A to B, 
   and (ii) from B to C, to compose from them such a group from A to C,
   using simple Stable Marriage Algorithm (1 theorist(?) + 2 programmers).

2. Matching algorithm. Hall theorem.

3. Network planning with AND- and OR-type nodes: algorithm and its
   proof. (The algorithm is a hybrid of Dijkstra and topological sort.)

4. Backtracking algorithms for generating all simple paths
   and all spanning trees in a graph.

5. Maintaining reachability sets for all vertices in a directed graph,
   when edges are added (1 theorist + 2 programmers).

6. Maintaining connectivity components of a graph, when edges are added to
   and deleted from a graph (1 theorist + 2 programmers).

7. Routing: Turning any flow in a multi-sink network into a flow
   on a single path to each sink (1 theorist + 2 programmers).


 III. ALGORITHMS

1. Two currencies optimization: Given a set of banknotes, each one
   costs both some dollars and some franks, to get at least A dollar
   and B frank, taking the minimum number of banknotes.

2. Knapsak (or thief) problem.

3. Two simple algorithms for compactization of digital pictures.


 IV. Additions to some existing program

1. Some program shows graphs, by its means; written in Paskal.
  A few additional operations (seem to be almost independent
  of the main program):
    (i) to show the same graph through a magnifying glass;
        parameters: center, size and spheric radius,
        (in fact, only node coordinates must be recomputed),
   (ii) to add possibilities to save and load the graph.

-----------------------
Last modified on November 5, 2000