{"id":712,"date":"2014-07-01T02:09:32","date_gmt":"2014-07-01T07:09:32","guid":{"rendered":"http:\/\/blogs.ams.org\/blogonmathblogs\/?p=712"},"modified":"2014-07-01T02:18:53","modified_gmt":"2014-07-01T07:18:53","slug":"visualize-your-algorithms","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/blogonmathblogs\/2014\/07\/01\/visualize-your-algorithms\/","title":{"rendered":"Visualize Your Algorithms"},"content":{"rendered":"

As a college student in the \u201890\u2019s with a penchant for \u201cvisual learning\u201d I was never drawn to computer science. My one computer science class focused mostly on syntax and basic logic. Had shuffling and sorting been presented as eye-catching animations and colorful braids, I might have taken more CS classes. Mike Bostock<\/a> presents such eye-catching images, specifically concerning\u00a0four different goals: sampling of images, shuffling, sorting, and maze generation. For each goal, Bostock chooses several algorithms and explains how they each work visually. Even a brief look at the visualizations, some of which are animated and some static, gives a sense of the differences between the algorithms. As Bostock points out, visualizing algorithms is entertaining, makes understanding the algorithm more intuitive to others, helps in debugging your algorithm, and deepens your own personal understanding. In short, Bostock wants you to visualize not just data, but the algorithms used to analyze the data. \u00a0From a mathematical perspective, this is similar to insisting that we find ways to visualize the proof mechanism itself and not just\u00a0the concept that it justifies. \u00a0In other words, we can draw a right triangle with appropriate labeling and call that a visualization of the pythagorean theorem, but it’s not nearly as instructive as this short animation<\/a>\u00a0or this geogebra applet<\/a>.<\/p>\n

Sampling is as ubiquitous in digital computing as the Pythagorean theorem is in geometry. \u00a0And while it is easy to understand as a concept, sampling is\u00a0difficult to execute well. Bostock takes as an example an impressionistic painting. How can we choose samples in a way that will best digitally reproduce the original image? It turns out that we can learn form our own biology; the eye\u2019s photoreceptors \u201csample\u201d the world around us and are distributed in an irregular but uniformly dense manner. Such a sampling helps combat aliasing, a phenomenon whereby regularly spaced samples distort data with high levels of periodicity (Imagine a picture of a striped sweater that is sampled at a resolution lower than the spacing between stripes). This is where Poisson Disk sampling comes in. It is computationally more complex than other options, but produces a uniformly dense yet random sampling. As Bridson\u2019s algorithm for Poisson Disk sampling plays, you immediately notice how the samples emanate from an initial seed rather than populating the entire sample space over time. This is one example of how visualization can helps us distinguish between algorithms.<\/p>\n

Bostock works for the New York Times, and has many wonderful examples and posts on his site. Being a delinquent topologist, I was drawn to\u00a0\u201cHow To Infer Topology<\/a>\u201d. Bostock is very interested in Cartography, and this leads to his writing about how to think about the data in a map more efficiently using a topological perspective. Several animations break down how one might encode a map by recording a sequence of arcs and special intersection points.<\/p>\n

After a bit of perusal I realized that I had seen some of the work of one of Bostock\u2019s collaborators, Jason Davies<\/a>\u00a0on Math Munch\u2019s page in the past. Looking over Davies\u2019 site, I can\u2019t help but recommend that you take a look at his simple but beautiful graphic of a tiling of the Poincare disc<\/a>. Zoom in and you can see the upper half plane model of the hyperbolic plane!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

As a college student in the \u201890\u2019s with a penchant for \u201cvisual learning\u201d I was never drawn to computer science. My one computer science class focused mostly on syntax and basic logic. Had shuffling and sorting been presented as eye-catching … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":62,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2,3,58,4],"tags":[228,232,229,230,231,127],"class_list":["post-712","post","type-post","status-publish","format-standard","hentry","category-applied-math","category-math-education","category-mathematics-and-computing","category-mathematics-and-the-arts","tag-algorithms","tag-animations","tag-computer-science-and-mathematics","tag-data","tag-sampling","tag-visualizations"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3tW3N-bu","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/712","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/users\/62"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/comments?post=712"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/712\/revisions"}],"predecessor-version":[{"id":715,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/712\/revisions\/715"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/media?parent=712"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/categories?post=712"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/tags?post=712"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}