Ive successfully finished the pset, and am mid-tier on the Big Board - but I have become transfixed with reducing space/time complexity. The only secret sauce Ive been able to glean is that those people at the top of the Big Board list 'might' have used something called a "bloom filter" - which uses a bit array to register letters of the word, but which doesnt establish a firm dependency between consecutive letters of a word - therefore something called "false positives" ie words which dont belong to the dictionary, are recognised as belonging to the dictionary. If anyone has any insight, or can direct me to a successful c implementation of a "bloom filter", or a good tut on the matter PLEASE let me know. Also, a while back CS50 used to publish a video walkthrough of the ANSWERS, I forgot what they called it - there was an honesty code attached - any idea where I could find the pset5 version - it would so help pedagogically, at this point I simply dont know what it is that I dont know!
1 Answer
The people at the top of speller bigboard, to get incredibly low values in reported memory usage, use other kinds of memory than stack or heap. It requires picking a maximum dictionary size, though, failing for larger ones.
Bloom filter is interesting, I'm just not convinced it will help, as you still would have to verify your "positives". And for the large dictionary, I'd expect more hits than misses.
Edit: I also think trie solutions are underrepresented in the upper parts of the list. But I don't know. Just compare run times and memory usage with for example hash tables.
