Timeline for Is Huffman coding dynamic programming
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2022 at 12:58 | comment | added | Rinkesh P | You are implying that every algorithm which works in a similar manner (bottom up) is a DP solution, as I have mentioned, top down/bottom up are ways to implement DP algorithms. There is more to the idea of solving an optimization problem through DP(it looks for all possible solutions, it may backtrack). Huffman coding clearly doesn't generate all possible trees. | |
| Jul 21, 2022 at 11:32 | comment | added | Sam | 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? | |
| Jul 21, 2022 at 10:48 | comment | added | Rinkesh P | 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. | |
| Jul 21, 2022 at 10:45 | history | edited | Rinkesh P | CC BY-SA 4.0 |
removed ambiguous terms in this context
|
| Jul 21, 2022 at 9:10 | comment | added | gnasher729 | Yves: What about a feasible one that isn't obviously non-optimal. | |
| Jul 21, 2022 at 9:08 | comment | added | gnasher729 | 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). | |
| Jul 21, 2022 at 6:54 | comment | added | user16034 | I would not even say a best candidate, just a feasible one. | |
| Jul 21, 2022 at 3:27 | history | answered | Rinkesh P | CC BY-SA 4.0 |