Hi, I’m Hamish; I’m from Watford, UK, and I’m a first-year student in Computing at Imperial. I like programming, Linear Algebra and modern foreign languages. I play water polo for IC 2s and hope to represent Imperial in Competitive Programming next year. Let’s connect on LinkedIn!
Often while wandering around doing whatever students do, I discover a relationship to what I’ve learnt in Algorithms or Competitive Programming, so I wanted to share some cases I’ve thought about recently where computing is Here To Help with student life.
O(N) Supermarket Sweep
There are many ways to go about shopping. I started with a “stochastic” algorithm ( 😛 ) – go to the supermarket and arbitrarily select groceries that seem useful.
Unfortunately, this isn’t effective; it has a low chance of yielding all correct items. A popular solution is a shopping list, which guarantees you get everything you need, but there’s a problem: if you traverse the list item-by-item and find each one in the store, you visit the whole supermarket for every list item in the worst case. This is O(nm) [m = size of list and n = size of supermarket].
We want an O(n) algorithm, so here’s a new plan: go through the supermarket linearly from entrance to exit and check if each item you see is on the list. This way I only make one pass through the supermarket1 – much faster. Alas, something tells me my algorithm isn’t exactly original so if we want any chance of a paper on this, we’ll have to move on to another problem.
Getting the Maximum from the Minimum
The other day when cooking this problem arose: you have a set of ingredients and several recipes. You want to feed yourself as many times as possible with these recipes and ingredients, but you don’t mind eating the same recipe several times. Thinking a bit, I concluded that the problem is similar to Coin Change and 0-1 knapsack; we can solve by Dynamic Programming. Define max_recipes(X) taking the set of remaining ingredients and returning the maximum number of recipes we can cook. max_recipes(X) = maximum over recipes Ri of (1 + max_recipes(X \ Ri)). The same X can arise via different recipe choices, so cache results. This is O(no. ingredient sets), which could be exponential ( 🙁 ). This doesn’t really matter since the number of ingredients is small. Also, if the problem is as difficult as CC or 0-1K it would be impossible to do substantially better. Leave a comment below if you have a better algorithm or a proof of NP-completeness.
Computing Can Help You Find Love2
There are k locations on campus where you can meet potential suitors; some yield more promising candidates than others. On each of n iterations, choose a location and evaluate the first individual there. At the end you can date the seen candidate with the highest evaluation score. What is your strategy to have the best date at the end? This is a version of the k-armed bandit problem. Instead of total reward we’re maximising maximum reward (you only have one date at the end). Various methods have been devised for this problem3; the gist is that you want to allocate some time to “exploring” (working out which locations offer higher rewards), and the rest to “exploiting” your knowledge of the best places, selecting them every time.
Concluding
Obviously, these analyses are simplified for the blog post format, but I enjoyed coming up with them, so hopefully you enjoyed reading them. I’ll leave you with one of my all-time favourite topics4: IC 2s water polo team competes in a league. Teams get 2 points for winning and 1 point for drawing. Determine (efficiently), from the league table and matches remaining whether IC 2s can still win the league.
1 Like in all good algorithms analysis, we neglect reading time of the shopping list as this is insignificant compared to walking time.
2 To be honest, I had to engineer this a bit and it’s not all that realistic, but I still think it’s a fun one
3 These will be affected by the maximum modification to the problem in this case.
4 Network Flow / “Baseball Elimination Problem”.