This course covers the design and analysis of randomized algorithms and, more generally, applications of randomness in computing. You will learn fundamental tools from probability and see many applications of randomness in computing.
In this blog post we will cover some of the basics of the Barnes Hut algorithm. This is completely new to me, it is not an algorithm I’ve used/studied before (and I am by no means an astrophysicist). Nonetheless it has piqued my interest so I have decided to write about it. In this blog I will be talking about 2 dimensions unless otherwise stated, this just makes the resulting code run a little quicker and output easier to visualise. Modifying the 2d code to be 3d (or even higher dimension) requires only minor revisions.
The textbook Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick enables precise quantitative predictions of the properties of large combinatorial structures.
- survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited
- study systematically alternatives to worst-case analysis
This book explains the algorithms behind those collisions using basic shapes like circles, rectangles, and lines so you can implement them into your own projects.
Q. Qu, Z. Zhu, X. Li, M. Tsakiris, J. Wright, and R. Vidal. (2020)cite arxiv:2001.06970Comment: QQ and ZZ contributed equally to the work. Invited review paper for IEEE Signal Processing Magazine Special Issue on non-convex optimization for signal processing and machine learning. This article contains 26 pages with 11 figures.