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. :)

Leave a Reply

Your email address will not be published. Required fields are marked *