Huffman coding follows a bottom-up approach where as Shannon-Fano coding is top-down. Is that contrast similar to dynamic programming versus greedy algorithm (dynamic programming always give optimal solution whereas greedy algorithm is sub-optimal)? If yes why is Huffman called greedy? Why greedy algorithm can also be bottom-up? Isn't that a feature for DP?
1 Answer
$\begingroup$
$\endgroup$
6
dynamic programming always give optimal solution whereas greedy algorithm is sub-optimal
Not True. There are problems where even a greedy approach would result in an optimal solution(Fractional knapsack, Minimum cost spanning tree, etc). An algorithm is said to be greedy if at every step it chooses a candidate and adds it to the solution set, without worrying about optimality, which is very clear in how the Huffman algorithm works(follows the optimal merge pattern, which again is a greedy procedure).
Top down and Bottom up approaches are terms related to dynamic programming implementations, and huffman coding uses neither. One might feel that since we build the huffman tree from the leaves to root it is a bottom up approach, however it is not the same as bottom up dynamic programming.
-
$\begingroup$ I would not even say a best candidate, just a feasible one. $\endgroup$– user16034Commented Jul 21, 2022 at 6:54
-
$\begingroup$ Take the coin changing problem with its obvious greedy algorithm. For certain sets of coins the greedy algorithm is optimal, for others it isn't, and writing a program that determines which one it is, given a set of coins, is an interesting problem. And there isn't just one greedy algorithm. For coin changing: Find the single coin or two coins with largest combined value that fit, return the larger one, and repeat. If you have 50 cents and 26 and 25 cent coins, this slightly more complicated greedy algorithm will be optimal (it will pick 25 cent, instead of the non-optimal 26 cent). $\endgroup$ Commented Jul 21, 2022 at 9:08
-
$\begingroup$ Yves: What about a feasible one that isn't obviously non-optimal. $\endgroup$ Commented Jul 21, 2022 at 9:10
-
$\begingroup$ By best candidate, I was hinting at the best candidate the greedy approach comes up with and that would not necessarily be a part of the optimal solution set. But yes that terminology was ambiguous so I removed it. $\endgroup$ Commented Jul 21, 2022 at 10:48
-
$\begingroup$ why is 'merging the two nodes with the least probabilities of occurrence in the current available set of nodes' not solving the subproblem in DP? $\endgroup$– SamCommented Jul 21, 2022 at 11:32