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. Bibliography: 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. Bibliography: 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 |

## Contact: | 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 |