-
Notifications
You must be signed in to change notification settings - Fork 10
SICP 2.3.4
- When is Huffman encoding optimal?
- history
- variable frequency, responsive codes...
- 2.3.4 (Pg 223): "The algorithm does not always specify a unique tree" -- how could it? What advantages would there be?
- long message blows stack?
- snacks
If we assume that a message has the same character frequencies as the corpus, Dann's version of encode-symbol is faster than Andrey's.
Example: n = 5. Characters: 1, 2, 3, 4, 5; frequencies: 1, 2, 4, 8, 16. Let's take a test message with one 1, two 2s, four 3s, eight 4s, and sixteen 5s. In total: N = 31 characters.
Andrey's encode-symbol: (n+1)N = 6 * 31 = 186. Dann's encode-symbol: 116 + 68 + 94 + 102 + 8*1 = 128.
- Finite State Entropy coding [blog].
Hey gang!
We're ushering in the new year with a few minor logistic changes to the meetings. We'll start the meeting at 6:30 sharp and end around 8:30, with a half hour of socializing on either side and a short break in the middle.
I've posted the upcoming reading schedule here: https://github.com/CompSciCabal/SMRTYPRTY/wiki/Reading-Schedule
Also new for 2014 we'll be experimenting with community moderation, so take a gander at the schedule and pick a section you'd like to moderate. You can claim your week directly on the wiki to prevent scheduling contention.
As a moderator you'll be responsible for asking questions and steering the dialog along interesting paths. You'll want to study the material that week extra carefully, both to select interesting questions to drive the conversation forward and so you can point people back to the source when it wanders too far afield. It's a great chance to get some group-leading experience, and we can jump in and help whenever needed.
Here's the schedule for the next two months: Jan 10: Huffman Encoding (2.3.4) [11 & 6] Jan 17: Data Representations (2.4) [24 & 4] Jan 24: Generic Operations (2.5.1, 2.5.2) [19 & 10] Jan 31: Symbolic Algebra (2.5.3) [20 & 11] Feb 07: Local State (3.1) [25 & 8] Feb 14: The Environmental Model (3.2) [20 & 3] Feb 21: Mutable Lists and Queues (3.3.1, 3.3.2) [19 & 12] Feb 28: Mutable Tables and Circuit Simulation (3.3.3, 3.3.4) [25 & 9]
Hope your new year is off to a fantastic start. I'm looking forward to catching up with you this Friday!
Happy coding!
Jan 7 2014
Greetings, friends!
We had a great time chatting about Huffman encoding last night, with the conversation eventually expanding to encompass persistent data structures, referential transparency, analog computers, the dominance of base two, and quantum computing algorithms. We explored the time and space complexities of encoding, decoding and tree building for context-free compression, and traded apocryphal stories of ancient compsci history.
Next week we'll be tackling section 2.4 on Data Representations. Remember the time change: we'll be running from 6:30-8:30, with half an hour of social on either side. Tea, coffee, hot chocolate and cookies provided; feel free to bring additional snacks if inspiration strikes.
Happy coding!
Jan 11