Koło Naukowe Matematyków U¦ PL SMS

XXXII SMS' Session

Szczyrk, 1st - 3rd June 2012

Propositions for topics of talks for the session "Algorithms"

Three first topics for students of first or second year:
1. Tjan-juan and Fang-cheng - two interesting algorithms, worked out long time ago in China [Juszkiewicz "Historia matematyki", Volume I, Chapter: China]
2. Introduction to numerical analysis [based on chapters 1.2 and 1.3 from Björck, Dahlquist "Numerical Methods in Scientific Computing"]
3. Quick multiplication methods. One can begin with those applying the formula of differences of squares and using the trygonometric tables and formulas [Kordos, Wykłady z historii matematyki, p. 125-126], through Gauss' method for multiplying complex numbers, up to Karacuba algorithm for multiplying large numbers and Strassen's algorithm of matrix multiplication.

This way we smoothly worked our way to numerical linear algebra and hence [below topics may, and even should be, divided into several smaller talks]:
4. Matrix decomposition: SVD, Cholesky, LU (+ LDU and LUP), QR + Householder.
5. Iteration methods: Jacobi, Gauss-Seidel, SOR, the conjugate gradients method.

D. Kincaid, W. Cheney, Analiza numeryczna,
A. Björck, G. Dahlquist, Metody numeryczne,
A. Kiełbasiński, H. Schwetlick, Numeryczna algebra liniowa,
Ralston, Wstęp do analizy numerycznej
Demidowicz, Maron, Szuwałowa, Metody numeryczne

For those interested in things done on a computer:
6. Binary programming
7. Network optimalization - the shortest route problem, maximal flow, cheapest flow, the travelling salesman problem, the backpack problem;
8. Greedy algorithms and matroids
9. Sorting (quicksort, heapsort)
10. Dynamical programming
11. Computational geometry: computing the convex hull - Chan algorithm, Voronoi diagrams, Furtune algorithm.

Banachowski, Diks, Rytter - Algorytmy i struktury danych
Dijkstra - Umiejętno¶ć programowania
Sysło, Deo, Kowalik - Algorytmy optymalizacji dyskretnej
Cormen, Leiserson, Rivest - Wprowadzenie do algorytmów

More advanced topics, if someone would be better oriented (and knew good references):
12. FFT
13. Integer relations detection algorithms - LLL, HJLS, PSOS, PSLQ
14. Numeryczne methods for solving differential equations
15. Ant algorithms
16. Genetic algorithms
17. Quant algorithms
18. NP-completeness

In the January-February 2000 issue of "Computing in Science & Engineering", a magazine of American Institute of Physics and IEEE Computer Society, series of articles entitled "Top Ten algorithms of the Century" was published. As written by the editors in the introductory article:
"We tried to choose 10 algorithms with the biggest influence on the development and practice of science and technology in the XX century". The chronological list is:
1946: the Monte Carlo method or Metropolis algorithm, devised by John
von Neumann, Stanislaw Ulam, and Nicholas Metropolis;
1947: the simplex method of linear programming, developed by George Dantzig;
1950: the Krylov Subspace Iteration method, developed by Magnus
Hestenes, Eduard Stiefel, and Cornelius Lanczos;
1951: the Householder matrix decomposition, developed by Alston Householder;
1957: the Fortran compiler, developed by a team lead by John Backus;
1959: the QR algorithm for eigenvalue calculation, developed by J Francis;
1962: the Quicksort algorithm, developed by Anthony Hoare;
1965: the Fast Fourier Transform, developed by James Cooley and John Tukey;
1977: the Integer Relation Detection Algorithm, developed by Helaman
Ferguson and Rodney Forcade; (given N real values XI, is there a
nontrivial set of integer coefficients AI so that sum ( 1 <= I <= N ) AI
* XI = 0?
1987: the fast Multipole algorithm, developed by Leslie Greengard and
Vladimir Rokhlin; (to calculate gravitational forces in an N-body
problem normally requires N^2 calculations. The fast multipole method
uses order N calculations, by approximating the effects of groups of
distant particles using multipole expansions)

Almost every of the topics above has some more or less advanced mathematics and is a potential topic for a talk during the session.

We give our sincerest thanks for this list of topics to dr Rafał Kucharski.
last update: 07.06.2012


Students' Mathematical Society of the University of Silesia
(Koło Naukowe Matematyków Uniwersytetu ¦l±skiego)
40-007 Katowice, ul. Bankowa 14 (room 524)
tel. (032) 359-20-96, email: knm@knm.katowice.pl