Greedy algorithms — Interesting problem

Revision en1, by random_user_001, 2021-11-09 16:45:27

You are given 2n alphabets a1, a2, ..., a{2n} with positive frequencies f1, f2, ..., f{2n} respectively. (We assume that f1 + f2 + ... + fn = 1.) Alphabets a1, a2, ..., an are colored blue, and alphabets a{n+1}, a{n+2}, ..., a{2n} are colored red. A prefix-free code C for {a1, a2, ..., a{2n}} is called valid if and only if every subtree of Trie(C) with at least two leaves has equal number of blue and red alphabets.

We need a polynomial time algorithm to find a valid prefix-free code of minimum cost. If possible explain running time analysis of algorithm.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English random_user_001 2021-11-09 16:45:27 607 Initial revision (published)