{"486431":{"#nid":"486431","#data":{"type":"event","title":"ARC Colloquium: Ian Munro - University of Waterloo","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch5 align=\u0022center\u0022\u003EIan Munro \u2013 University of Waterloo\u003C\/h5\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 1, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003Cbr \/\u003E \u003C\/strong\u003EOptimal Search Trees with 2-way Comparisons\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003Cbr \/\u003E \u003C\/strong\u003EThis talk is about finding a polynomial time algorithm that you probably thought was known almost a half century ago, but it wasn\u2019t. The polynomial time algorithm is still rather slow and requires a lot of space to solve, so we also look at extremely good and fast approximate solutions. More specifically \u2026\u003Cbr \/\u003E In 1971, Knuth gave an O(n\u003Csup\u003E2\u003C\/sup\u003E)-time algorithm for the now classic problem of finding an optimal binary search tree. Knuth\u2019s algorithm works only for search trees based on 3-way comparisons, but most modern programming languages and computers support only 2-way comparisons (\u0026lt;, = and \u0026gt;). Until this work, the problem of finding an optimal search tree using 2-way comparisons remained open \u2014 polynomial time algorithms were known only for restricted variants. We solve the general case, giving\u003C\/p\u003E\u003Cp\u003E(i)\u0026nbsp; an O(n\u003Csup\u003E4\u003C\/sup\u003E)-time algorithm and\u003C\/p\u003E\u003Cp\u003E(ii) a linear time algorithm that gives a tree with expected search cost within 2 comparisons of the optimal.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Marek Chrobak, Mordecai Golin, and Neal E. Young.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2016-01-14 15:10:33","changed_gmt":"2017-04-13 21:17:09","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-01T12:00:00-05:00","event_time_end":"2016-02-01T13:00:00-05:00","event_time_end_last":"2016-02-01T13:00:00-05:00","gmt_time_start":"2016-02-01 17:00:00","gmt_time_end":"2016-02-01 18:00:00","gmt_time_end_last":"2016-02-01 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}