Advanced Algorithms and Scientific Writing
	         (202-2-5521, 2 points)
	           prof. Yefim Dinitz

The course is destined for Ph.D. and M.Sc. students, whose
thesis concerns CS theory, and for 3rd year undergrads
interested (with average in theory at least 80). For those
that like to learn algorithmic ideas, and to elaborate
why an algorithm achieves its goal and does this fast.
As well, for those who wishes to study scientific writing.

   The grade will be defined by a few midterms and homeworks,
and by the final work (no exam).

   I will choose, for the course, a few algorithms which
students of Technion and BGU liked. The list of topics,
to choose from, is:

 - an improvement for finding one-source shortest paths;

 - network flow algorihms and their running time;

 - finding the network connectivity (the value of its globally
   minimum cut);

 - finding an optimal matching;

 - a variant of the knapsack problem with two constraints;

 - finding an optimal schedule, in presence of precedence constraints;

 - off-line scheduling, for two dependent agents moving in a network;

 - efficient listing of all combinatorial objects of a given type
   (e.g., cycles in a given graph, or non-isomorphic trees with
   a given number of vertices).

   The "top-down" way of exposition will be the main one, in
the course. Among the important methods used is the primal-dual
method of optimization.

   In the course, students will study to write, aiming to help
them with their thesis and papers. The tasks suggested for
writing will be, for example, either to give a full overall
exposition of a certain algorithm or of its part, or to
compose an explanation or proof, or a short ``mini-paper''.
Students will study and use the English version of Latex
(bad but understandable English would be acceptable).