Howdy, y’all! After a summer in Oregon, I’m back in warm (oh, blessedly warm) Georgia. Yes, the rumors of constant drizzling in OR are true. However, once the sun decided to grace us with its presence (right around the 4th of July), it was glorious. There’s a running joke that Intel hires interns during summer to lull them into thinking Hillsboro is always that gorgeous in order to entice them to stay. 😛
Anyway, my course load this semester isn’t too bad; I’m taking Computer Architecture, Data Structures, Calculus II and another Statistics class. Data Structures is a key class for Computer Science students to take and really grok because (a) a lot of technical interviews will test you on knowledge learned from this class (b) it teaches you to think & dives into fundamentals like designing data structures, algorithms, knowing when to pick certain abstract data types subject to contraints (like limited space, large input, etc), etc.
It’s been over a month into the Data Structures course and it feels like drinking from a firehose of abstract data types! Our first project was to implement the Huffman coding using C++ and it was a lot of fun. Huffman coding is a lossless algorithm for encoding variable length strings. Read more on Wikipedia if you’re so inclined. For this project, we were given a .txt file containing a large block of text from which we were required to generate a Huffman tree and store this to a file on disk.Then, to encode a string entered from std::cin, we were to:
a) recreate the Huffman tree from this file that was stored to disk (I chose a lookup table that contained the character and its bitstring)
b) encode or decode strings using the Huffman tree..
For the encoding and decoding portions, we were barred from using lookup tables which made me sad because I had just learned about maps in C++. Maps are ‘associative containers’ and they geared towards scenarios when you need to search by key to find the key’s value. My initial strategy for encoding was to store my Huffman lookup table in a map<char,string> container. Then, using the string iterator, I could translate the user’s string to bits by finding map[‘userChar’] which yielded ‘010101’ or some sequence of bits which would be appended to by reading more characters.
To complete this project, I got reacquainted with vectors, string iterators and pointers. For constructing my Huffman tree, I went for a binary tree made up of Nodes and stored this in a vector of Node pointers. I used a Node class because I wanted to be a little more familiar with classes in C++ and I fleshed out my Node class (private vars with getters/setters, private method, overloaded some operators, etc). I know some classmates used structs.
Overall, I’m pretty happy with the structure of my program especially because without too much work, I was able to reuse my code for another written assignment. We were required to ‘write’ out a Huffman tree and rather than do this by hand, I fed the .txt file of characters & frequencies into my method which did the dirty work of listing the nodes to merge and presenting the final lookup table for me. 😛 It could be more efficient and as time permits, I’ll revise my code.