{"id":1279,"date":"2013-02-19T22:34:36","date_gmt":"2013-02-19T21:34:36","guid":{"rendered":"http:\/\/cerezo.name\/blog\/?p=1279"},"modified":"2024-10-14T13:39:12","modified_gmt":"2024-10-14T11:39:12","slug":"analytic-combinatorics","status":"publish","type":"post","link":"http:\/\/cerezo.name\/blog\/2013\/02\/19\/analytic-combinatorics\/","title":{"rendered":"Analytic Combinatorics"},"content":{"rendered":"<p style=\"text-align: justify;\">The classic era of the analysis of algorithms exhibited limitations: worst-case running analysis and upper bound limits were not enough to compare algorithms in practice, neither to predict the real performance of algorithms. Although it enabled a fruitful research era in the design of algorithms, it had to be ignored by most practitioners. Neither lower bounds (Omega notation), nor theta notation (order of growth) were of much help: the field was in need of a profound paradigm shift.<\/p>\n<p style=\"text-align: justify;\">Analytic combinatorics was the catalyst, a calculus built on the power of generating functions to enable the creation of predictive models for algorithm performance by using precise quantitative predictions of large combinatorial structures.<\/p>\n<p style=\"text-align: justify;\">The book of Flajolet and Sedgewick, two key researchers that shaped the field with their fundamental theorem of symbolic combinatorics, is the best, self-contained source for learning (freely available on the&nbsp;web):<\/p>\n<p style=\"text-align: justify;\">\n<\/p><div class=\"gde-error\"><span class=\"caps\">GDE<\/span> Error: Error retrieving file \u2014 if necessary turn off error checking (404:Not Found)<\/div>\n\n<p style=\"text-align: justify;\">You may also want to receive some lectures from Sedgewick himself, a privilege only available if you go to Princeton (or by using the Coursera online learning platform):<\/p>\n<ul>\n<li><a href=\"https:\/\/www.coursera.org\/course\/introACpartI\" target=\"_blank\" rel=\"noopener\">Analytic Combinatorics, Part&nbsp;I<\/a><\/li>\n<li><span style=\"text-align: justify;\"><a href=\"https:\/\/www.coursera.org\/course\/introACpartII\" target=\"_blank\" rel=\"noopener\">Analytic Combinatorics, Part&nbsp;<span class=\"caps\">II<\/span><\/a><\/span><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>The classic era of the analysis of algorithms exhibited limitations: worst-case running analysis and upper bound limits were not enough to compare algorithms in practice, neither to predict the real performance of algorithms. Although it enabled a fruitful research era in the design of algorithms, it had to be ignored by most practitioners. Neither lower&nbsp;[\u2026]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"wp_typography_post_enhancements_disabled":false,"ngg_post_thumbnail":0},"categories":[9,15],"tags":[],"_links":{"self":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1279"}],"collection":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/comments?post=1279"}],"version-history":[{"count":3,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1279\/revisions"}],"predecessor-version":[{"id":1553,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1279\/revisions\/1553"}],"wp:attachment":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/media?parent=1279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/categories?post=1279"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/tags?post=1279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}