23rd April
The old, fat book says:
“An algorithm is said to be correct if, for every input instance, it halts with the correct output.” — So, a correct algorithm has to halt for any sorts of arrangement of the input. And a correct algorithm has to be correct. (Aha!..Thank you for that piece of information!). Easier said than done, Eh? Let's say, ‘correct’ means the solution respects the problem’s demand. But how do we know that the algorithm is indeed correct, or has solved it, at least? And how long will one have to wait before a program halts? Well, the tool to use is ‘Algorithm Analysis’.
There is an interesting thought in the book: Given that the speed and memory of computing machines keep on growing, why should you study algorithms? That is because you can prove that your algorithm halts with a correct answer by analyzing it. Also, by designing an efficient algorithm you are going to respect the fact that computing resources (time, space) are still bounded.
The book also says: Despite an algorithm being incorrect, it can sometimes be usable: should one be able to control the error rate! (More information, as per the book, comes in the form of some crazy algorithm in Chapter 31).
One good thing about this book is — as per the authors — each chapter itself is self contained, so that you can randomly jump into some chapter of your fancy and finish that off. Then you delve in another one of your liking. But at least I will go through the initial chapters (Introduction and the next chapter) — in the order — on the fundamentals. After that will do random chapter hopping.
Let me see.
Soft Introduction to ‘Hard vs Efficient’
A polynomial order of complexity is much less time consuming, and thus desirable, and often quoted as an ‘efficient’ algorithm. Example: The ‘Shortest Path Problem’ is of polynomial complexity, whereas a slightly changed (to Shortest path) problem of ‘Travelling Salesman Problem’ is Hard (It is NP Complete). More on NP complete later. A hard problem is one which does not have an easy solution (Duh!), and the solution grows exponentially, (e.g.: 2^n where n is the input size) or higher w.r.t input size.
Usual measure of efficiency is speed.
In the ‘Travelling Salesman Problem’, we start from a vertex and then we gotta reach back to the same starting vertex — with the conditions that: (a) We must cover the least possible total distance, and (b) We oughta visit every other vertex before we reach back. Apply brute-force, and apparently you gotta try the (n-1)! ways of arranging them (Factorial means this approach is exponential in complexity) in the solution space. In the closely related ‘Shortest Path Problem’ though, you don’t need to traverse all other vertices before reaching your destination — It can be a subset of existing vertices. And it has only a polynomial complexity as already hinted: So, just bring in a slight change in the problem statement, and you get a completely different situation. Algorithm analysis helps you assess this.
Given a hard problem is exponential in its outlook, there are algorithms called “Approximation Algorithms” that can be applied to reach a solution efficiently — But you have do some assumptions on the hard problem statement first to apply approximation algorithms. Will take you through it later.
