Month: February 2019

Introduction

Posted by – February 9, 2019

Chapter 1 of CLRS (which I may also refer to as ItA, since it’s easier to remember) is about “The role of algorithms in computing”. An algorithm is defined as any well-defined computational procecedure that takes an input and produces an output. Sounds to me a lot like a mathematical function, though I imagine an algorithm referring to the machinery that performs the computation, whereas a function is a description of a relationship. I also imagine it would be difficult to express many algorithms fully in mathematical symbols. But the distinction between an algorithm and the computer code of a function is less clear. The algorithm is the procedure, while the actual code will depend on the language you’re programming in.

More formally, an example is given where the Input and Output are stated, and the algorithm is correct if for every input instance, it halts with the correct output. (I like the sound of halting. It makes me think of the kind of computer Babbage would use, with clunking gears that finally stop and the dials come to a stop showing a number for the answer.)

Problems in the real world where algorithms are applied include:

  • The Human Genome Project (sequencing, data storage, abalysis) – using human and machine resources efficiently
  • The Internet – routing of data; search
  • Cryptography for e-commerce
  • Industry: placing oil wells, assigning crew to flights, political campaigning etc (these are Linear Programming)

ItA then talks about efficiency, and mentions that for some problems, no efficient solution is known. There is a subset known as NP-complete, for which no efficient algorithm has been found, but no-one knows if an efficient algorithm exists or not. If it does, then it’s been shown that all have an efficient solution. And many NP-complete problems are very similar to some problems for which we do have efficient solutions. NP-complete problems (e.g. the travelling salesman problem) come up very often, and while a “solution” might not be entirely efficient, it is possible to come up with “approximation algorithms”.

Example of different complexities is given in the form of insertion sort and merge sort. The former is O(n^2) while the latter is O(n lg n). Insertion sort is faster for small n, but there will always be a crossover point above which merge sort is the more efficient.

Finally, we’re asked to compute the largest size of n (the number of items the problem is applied to) that can be computed in different spaces of time, if an algorithm takes f(n) microseconds (millionths of a second) to complete. I spent a while using Excel’s “solver” to compute the answers numerically (which was difficult when using some of the huge numbers!), since I’m not sure an analytical way of solving some of these even exists. Doing the whole thing would be just a bit too tedious, since Excel only lets you solve one thing at a time, so I just did 1 second, 1 day, and 1 century, to various levels of precision. :)

Let’s learn algorithms!

Posted by – February 2, 2019

In Scala, of course… a new series of articles begins

Back in the day (circa 2011), I cut my teeth on Java participating in algorithm competitions on a site called TopCoder. There was a cool little applet you would download, and you used it to navigate problems, enter your code, run tests, check out other people’s solutions, etc. I wrote a parser for the problems in the form of a Swing application that would spit out fully formed Scala test scripts and code templates, which allowed me to tackle the problems in Scala as well, which was rather neat… if I say so myself. I wasn’t very highly rated, and by “participating”, I mean mainly tackling the problem sets post facto in my own sweet time, but it was good fun, somewhat addicitive, and a way to keep the coding skills sharp. I must have done hundreds of them.

Well, applets went out of fashion, and TopCoder went into terminal decline (they have their problems on a website now, but it er… doesn’t really work). Fortunately there are a bunch of similar sites that have sprung up in the meantime, one of the best of which is CodeForces. Its interface is a bit less friendly for JVM programmers (everything’s done in strings via the standard in and out, which requires a bit of rather tedious parsing and formatting kerfuffle, rather than filling the gaps in a method with a provided signature and return type), but it does support a wider range of languages including Scala, and some more “out-there” ones like Rust, Kotlin, and Node.js. So I’ve been playing around with those competitions lately instead.

Now I seem to do okay on the easier problems, like the ones tagged “brute force” or “implementation”, but I’ve been struggling a bit with the more advanced ones, for instance requiring use of data structures. One that had me scratching my head recently required the use of a “segment tree”. Since you don’t get to use any libraries beyond the standard one, you have to program it yourself during the course of answering the question (or, I guess, if you’ve done it before, cut-and-paste one from your bag of tricks). Lacking a formal computer science education, I’d never heard of a segment tree, which makes it kind of tricky. So far I’ve counted on pretty much working things out myself from first principles each time I see something new – but, given the limited time we have on this planet, and the time it would take to re-invent computer science in my own head, I thought maybe it would be an idea to knuckle down and learn algorithms properly.

“Introduction to Algorithms” (pictured), aka “CLRS” after its authors, is a highly regarded reference book. So I’ve got hold of my own copy, but at over 1200 densely packed pages it’s not something I’m going to fly through in a weekend. I will work through it; one interesting challenge will be to try to implement any exercises in functional style, i.e. without side-effects or mutable state. In the book, the examples are in a Python-esque pseudocode with variables and loops a-go-go.

Another reference for this blog series, will be cp-algorithms.com, which I’m going to call “CPA”, and as the name suggests is a guide to competetive programming algorithms. It is itself a translation of a Russian site (as everyone knows, the best competitors are mostly Russian – they love their C++ out there). There are a LOT of topics, which are listed in alphabetical order rather than from simplest to most complex, so I’ll use CLRS as a guide to learning order, and CPA for some juicy and pertinent examples to tackle in Scala.

There only seem to be a handful of people currently using Scala in these competitions, and their style is mostly imperative. Let’s see if we can take the world of algorithm competitions by storm writing idiomatic Scala. It will be a journey!