Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Aug 17
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Aug 17
Event date: Friday, August 17, 2012, at 2:00 PM
Location: PT266
Speaker: Jeremy Barbay
University of Chile
Title: Prefix Free Codes in Linear Time
Abstract:
Considering the computation of an *optimal prefix-free code* over n symbols from their frequencies f_1,...,f_n given in arbitrary order, we give a *linear time algorithm* in the *word-RAM memory model* and an (input order oblivious) *instance optimal* algorithm in the *algebraic model*. These complexities improve over both the traditional O(n\lg n) algorithm from Huffman and the O(nk) adaptive algorithm from Belal and Elmasry, where k is the number of distinct code lengths in any optimal code.
**Please note the room change from BA 5256 to PT266