Week 15 Day 2 - Advanced Topics, Histogramming
3We went over some of the weirder corners of C++ today, including some things that are completely legal but maybe shouldn't be (like initializing a variable with itself, and mixing up the array and index with square brackets).
We then did something called a histogram, where we count how often a certain thing happens. In four lines of code, we could output the top words (sorted by count) from Hamlet. Not bad, eh? Modern C++ lets us write powerful and expressive code without needing to worry about memory leaks or manually allocating memory. For this one, we used an unordered map (hash table) to associate strings and integers. Each time the same string came up, we incremented the integer it was associated with by 1.
We then tossed it into a multimap (a BST that allows duplicates) that associated ints and strings, sorting by ints. We allow duplicates since without it keys would have to be unique, and counts of words like 1 will come up a lot, and would overwrite each other in the data structure.
I then solved (in the last 15 minutes of class) a homework assignment one of my former students send to me from his current school, asking for help. This assignment didn't require anything fancy from a data structures standpoint, just three 2D arrays of equal size. By being clever about the solution, we can solve it in O(N) time, rather than O(2^N) which it would be if we tried brute forcing it.