bigoquiz.com
Over the last few weeks I’ve been working on bigoquiz.com. I wanted to learn the Big-O algorithmic complexity of the main algorithms and data structures by heart. So, of course, I first built a system to help me do that.
bigocheatsheet.com and bigoref.com already do a good job of listing the information, but bigoquiz.com lets you check that you really know each one, and shows you the ones you keep getting wrong.
Tech I learned along the way
I find it very hard to resist a project when I see that it would let me play with multiple new things. This one was a chance to learn about:
- GWTP instead of plain GWT.
- Using a flat NoSQL database structure (via Google’s AppEngine DataStore) instead of the full relational databases that I’m so familiar with. I’ll blog about that later.
- Using AppEngine’s simple Users API to offer Google Sign-In after struggling, and not properly succeeding, to implement user login in OnlineGlom and then never quite managing to use SpringSecurity in OnlineGlom instead. This was a much nicer experience, though I see nothing that makes it quite as easy to add login via Twitter, Facebook, etc.
- Modern CSS, such as using CSS media queries to make the web site responsive on various screen sizes. I used media queries to hide sidebars and reduce margins on smaller screens.
Details
I noticed that bigoref.com had some corrections and additions compared to bigcheatsheet.com. And I made some additions of my own. I’ve listed it all here for anybody who is interested:
For instance, bigoref.com adds Graph Search algorithms such as Dijkstra’s and Bellman-Ford (missing from bigocheatsheet.com), under “Searching“. I instead listed the graph search algorithms in bigoquiz.com under “Graph Search” and added more graph algorithms that I’d learned about recently in my Coursera course, though I’m tempted to create a completely different graph algorithms quiz: Kruskal’s Minimum Spanning Tree, Prim’s Minimum Spanning Tree, Floyd Warshall All Pairs Shortest Path, and Johnson’s All Pairs Shortest Path.
bigoref.com also adds linear and binary search of arrays (missing from bigocheatsheet.com). For bigoquiz.com I just split Array into sorted and unsorted in “Data Structure Operations”.
I found just one error on bigoquiz.com that was corrected on bigoref.com, though there might be others:
And I noticed that bigoref.com has some additional errors so I corrected those on bigoquiz.com and filed github issues for bigoref:
- The Binary Heap and Binomial Heap complexities seem to be wrong.
- The Shell Sort best case time seems to be wrong.
- The Bucket Sort worst case space seems to be wrong.
Also:
- bigocheatsheet.com has entries for Stack, but bigoref.com does not. I kept that in bigoquiz.com.
- bigoref.com has entries for Ternary Search Tree, apparently a kind of Trie (Prefix Tree), but bigocheatsheet.com does not. I kept this in bigoquiz.com. Curiously, bigoref.com doesn’t have entries for regular Tries (Prefix Trees), or Suffix Trees. I added them to bigoquiz.com, though I’m not completely sure about the various best/worst/average time/space complexities.
- bigoref.com uses the term “indexing” where bigocheatsheet.com uses “access”. I’ve stuck with “access” for bigoquiz.com.
- bigoref.com splits array into Basic Array and Dynamic Array, not allowing insertion or deletion in a Basic Array. I don’t find the distinction useful, so I kept it as just Array in bigoquiz.com.