Schedule
Top Ten Algorithms
Fall 2015

For the fall semester, 2015, this class meets on Mondays, 12:20-1:10, in room 499, Dirac Science Library.

1. August 24:
   • slides for class #1;
   • Dongarra and Sullivan Top Ten List;
   • Euclid's algorithm;
   • Bernoulli number algorithm used by Babbage;
2. August 31:
   • slides for class #2;
   • Web page indexing algorithm, reference: John MacCormick, 9 Algorithms that changed the future, chapter 2;
   • Student presentation: Mike Conry, "The Pancake Flipping Problem and the Genome", reference, Brian Hayes, "Sorting out the genome", http://amsciadmin.eresources.com/libraries/documents/2008511610596480-2007-09Hayes.pdf
3. September 14:
   • slides for class #3;
   • Student presentation: Chaolun Wang, "Prototeins" reference: Brian Hayes, "Prototeins", http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-05-Hayes-prototeins.pdf
   • Student presentation: Brett-Michael Green, "PageRank" aka "The Judge is an Idiot" "PageRank", reference: John MacCormick, 9 Algorithms that changed the future, chapter 3;
   • Directed graphs, the path counting algorithm, the transition matrix, the power method algorithm;
4. September 21:
   • slides for class #4;
   • Student Presentation: Nick Lopez, "The Britney Spears Problem" (determining the most common element in a data stream) "Britney", reference, Brian Hayes, "The Britney Spears Problem", http://amsciadmin.eresources.com/libraries/documents/2008631225466814-2008-07Hayes.pdf
   • The PageRank algorithm as solving a Monte Carlo problem, a graph problem, an eigenvalue problem;
5. September 28:
   • slides for class #5;
   • Peter Beerli will speak on the bootstrap algorithm, and the use of trees in computational biology. Peter could become your advisor...
6. October 5:
   • slides for class #6;
   • Student Presentation: Feifei Xu, "QR Codes", reference: Nick Berry, "Wounded QR Codes", http://datagenetics.com/blog/november12013/index.html
   • Error detection codes with checksums, UPC, ISBN, Luhn, bank checks; error correction with Hamming (7,4), Reed-Solomon code. 9 Algorithms that changed the future, chapter 5;
7. October 12:
   • slides for class #7;
   • Anke Meyer-Baese will speak on data-mining algorithms. Anke could become your advisor...
8. October 19:
   • slides for class #8;
   • Student Presentation: AmirHessam Tahmassebi, "Discrete Cosine Transformations - How JPGs work", http://people.sc.fsu.edu/~jburkardt/classes/tta_2015/dct2d.pdf reference, Nick Berry, "Discrete Cosine Transforms", http://datagenetics.com/blog/november32012/index.html
   • Estimating the period of periodic data, or of data with a periodic component; composing and decomposing a "true" periodic function from harmonic sine functions; The Slow Fourier Transform; the Fast Fourier Transform; 1D FFT for time series analysis; 2D FF for image analysis; variants on the FFT; FFT packages and implementations; Hartley, Haar, Walsh transforms.
9. October 26:
   (Your instructor will not be able to attend class today. He has to go learn some more algorithms! Please come to class anyway and learn from our two student presentations.)
   • Student presentation 1: Ben Crysup, "The Ripple Carry Adder", PPTX slides at: http://people.sc.fsu.edu/~jburkardt/classes/tta_2015/RippleCarry.pptx
   • Student Presentation 2: Nathan Crock, "The Backward Propagation Algorithm"
10. November 2:
    (We need to stop before 1pm today; Olmo needs the room for his defense!)
    • slides for class #10;
    • Student presentation: Joe McKenna, "The QR Algorithm for Matrix Factorization", reference, Cleve Moler, http://www.mathworks.com/moler/leastsquares.pdf
11. November 9:
    • slides for class #11;
    • Student presentation: Juan Llanos, "Zero-Knowledge Proofs", reference by Matthew Green at http://blog.cryptographyengineering.com/2014/11
    • Student presentation: Stephen Townsend, "Detecting Targets in Noisy Radar Signals" reference, Nick Berry, http://datagenetics.com/blog/may22014/index.html
12. November 16:
    • slides for class #12;
    • Student presentation: Thomas Britton, "Quasirandom Numbers", slides at: http://people.sc.fsu.edu/~jburkardt/classes/tta_2015/quasirandom_numbers.pdf
      reference Brian Hayes, "Quasirandom Ramblings", American Scientist, July-August 2011.
    • Computational Geometry: area of a triangle, collinearity, barycentric coordinates, quadrature rules for a triangle, triangulating a polygon.
13. November 23:
    • slides for class #13;
    • Student presentation: Anna Yannakopoulos, "Recovering Solutions Given Insufficient Data",
      reference: Cleve Moler, "The World's Simplest Impossible Problem", www.mathworks.com/clevescorner/dec1990,
      Cleve Moler, "Magic Reconstruction: Compressed Sensing", www.mathworks.com/tagteam/65074_91850v00_NN10_Cleve.pdf.
    • Student presentation: Isaac Lyngaas, "Computing With Very Large Numbers",
      reference: Brian Hayes, "The Higher Arithmetic", American Scientist, September/October 2010.
    • Public Key Cryptography: the balanced partition problem, the subset sum problem, encrypting data for transmission over an insecure channel.
14. November 30:
    • slides for class #14;
    • Student presentation: Amirhessam Tahmassebi, "Hilbert Curves", slides: space_filling_curves.pdf;
      reference: Brian Hayes, "Crinkly Curves", American Scientist, May-June 2013,
      Nick Berry, "Hilbert Curves - fractal space filling fun", http://datagenetics.com/blog/march22013/index.html
    • Student presentation: Juan Llanos, "Convex Hulls and the Caliper Algorithm", Nick Berry, "Bounding Boxes", http://datagenetics.com/blog/march12014/index.html

You can return to the TTA 2015 web page.