Presentation, SIAM Undergraduate Seminar at UIUC, Urbana, IL, USA
Near-linear work algorithms for connectivity and single-source shortest paths (SSSP) have been known since before the 1950s. In this talk, we will describe approaches to increase their parallelism, including coarsening algorithms for connectivity, and incremental stepping algorithms for SSSP.
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
In a static graph, checking whether nodes are in the connected component takes linear time. I will describe the Kapron, King, Mountjoy algorithm supporting polylog time updates and queries.
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
Karger-Klein-Tarjan randomized algorithm for computing minimum spanning trees in linear expected time.
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
Sampling with replacement, quickly.
Presentation, CS 581, Urbana, IL, USA
Course project, Multiple Sequence Alignment, MAGUS, …
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
Multiple sequence alignment, maximum weight trace, dynamic programing, heuristics…
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
Elementary graph theory, De Bruijn sequences, and genome assembly…
Presentation, SIGma (UIUC Special Interest Group in Math and Algorithms), Urbana, IL, USA
Recursion, Inverse Ackermann, Union-Find, Range-Minimum Queries…