Introduction to Algorithms

An algorithm is a set of steps defined for solving a problem in finite time and space. Generally, an algorithm is written to express the method of problem-solving; it may include mathematical notations.

As an algorithm is expressed in a language, developers can implement the logic in any programming language. If you are familiar with Data Structures, you know that algorithm is very important in implementing Data Structures.

Hence, we can say:

An algorithm is an explicit, precise, unambiguous, mechanically-executable sequence of elementary instructions.

Computer programs are concrete representations of algorithms, but algorithms are not programs; they should not be described in a particular programming language. The whole point of this course is to develop computational techniques that can be used in any programming language.

On the other hand, a plain English prose description is usually not a good idea either. Algorithms have a lot of structure-especially conditionals, loops, and recursion-that are far too easily hidden by unstructured prose. Algorithms must be described as accurately as possible.

The best way to write down an algorithm is using pseudocode that uses formal languages and mathematics to represent the primitive steps. Well-written pseudocode makes the algorithm easier to understand, analyze, debug, and implement.

The precise syntax of pseudocode is a personal choice, but the overriding goal should have clarity and precision. Ideally, pseudocode should allow any competent programmer to implement the underlying algorithm, quickly and correctly, in their favorite programming language, without understanding why the algorithm works.

---

Guidelines for writing an Algorithm

---

Use standard imperative programming keywords (if/then/else, while, for, repeat/until, case, return) and notation (variable value, Array[index], function(argument), bigger > smaller, etc.).

Indent everything carefully and consistently.

Use mnemonic algorithm and variable names. Short variable names are good, but readability is more important than concision; except for idioms like loop indices, short but complete words are better than single letters.

Use standard mathematical notation for standard mathematical things.

Each statement should fit on one line, and each line should contain either exactly one statement or exactly one structuring element (for, while, if).

---

Algorithmic Strategies

---

Divide and Conquer

There are many problems, which can be divided into sub-problems and the sub-problems can be solved individually, finally, the solutions of individual problems can be merged together to form the final result. Examples include the merge sort, quicksort algorithms, etc.

---

Dynamic Programming

This is an optimization technique. When sub-problems need to be solved repetitively, the solutions of the sub-problems are stored in a table to reduce time consumption. In the future, when the result of the subproblems is needed, instead of solving the sub-problem the stored solutions are used.

---

Greedy Approach

A greedy algorithm is useful when sufficient information is known about possible choices. The best choice can be determined without considering all possible choices. Thus this approach may not give the best solution. But, the advantage of this approach is that the result can be obtained in less time.

---

Approximation Algorithms

This technique deals with NP-completeness for optimization problems as NP-complete problems are not solvable in a reasonable time. It does not guarantee the best (optimal) solution. The problems, for which optimal solution can not be determined in a reasonable time, are solved by approximation algorithms to get a near-optimal solution in polynomial time.

---

Happy Exploring!