Algorithmic Design and Analysis

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Algorithmic Design and Analysis"

by

TSE Hiu Fung

Abstract:

Almost-instantaneous Fixed-to-Variable (AIFV-m) codes can perform better 
than Huffman codes. However, no polynomial time algorithms has been known 
for constructing optimal AIFV codes for m >= 3. In this report, we examine 
the existing iterative algorithm for AIFV-2 codes and prove its 
correctness using a geometric argument. We then investigate AIFV-3 code, 
prove various properties about them and fix a proof of correctness of an 
iterative algorithm for them. Finally, based on the geometric 
constructions of the polynomial time AIFV-2 algorithms, we prove an 
important technical lemma that paves way for a generalization of the 
ellipsoid method to AIFV-3 codes.


Date            : 6 May 2021 (Thursday)

Time            : 17:00-17:40

Zoom Link:
https://hkust.zoom.us/j/99373905170?pwd=VUk2TkpNL1JkTlpiUHRYUEMwUjNoZz09

Meeting ID      : 993 7390 5170
Passcode        : 522518

Advisor         : Prof. GOLIN Mordecai

2nd Reader      : Prof. CHENG Siu-Wing