Introduction to Algorithms

What is an algorithms?

From chapter 1 of Introduction to Algorithms, an algorithm is any well-defined procedure that transforms a set of input to a set of output with desired properties.  It is a tool for solving a computational problem, which specifies the desired input/output relationship.

Input → Algorithms → Output

The input is organized in a certain data structure.  Each set of input is an instance.

A correct algorithm halts with the correct output and solves the computational problem.  There may be many algorithms for a given problem.  Which algorithm is best depends on many factors.  A more efficient algorithm is preferred.  The efficiency of an algorithm depends on the time required for the algorithm to solve the problem.  One way to increase efficiency is to take advantage of computers with multiple processing cores by designing algorithms that run using multiple cores at the same time (multithreaded algorithms).

The Sorting Problem

An example of a computational problem is the sorting problem, which is a common problem:

Input: A sequence of n numbers (a1,a2,…,an).
Output: A permutation (reordering) of the input sequence such that the numbers are listed from the smallest to the largest.

Two algorithms are suitable for this problem:

• Insertion sort has run time of constant*n^2.
• Merge sort has run time of constant*n*log n.

The constant of insertion sort is usually smaller than the constant of merge sort.  However, merge sort is more efficient when n is large because log n is smaller than n.

NP-complete Problems

NP-complete problems are a subset of computational problems which have no known efficient solution.  They have intrigued computer scientist because:

• There are no known efficient solution to any NP-complete problem but nobody has ever proven that an efficient algorithm for an NP-complete problem cannot exist.
• If an efficient algorithm exists for any NP-complete problem, then efficient algorithms exist for all NP-complete problems.
• There are problems for which we know of efficient algorithms that are similar to some NP-complete problems.  That is, a small change to the problem statement can cause a big change to the efficiency of the best known algorithm.
• Many real world problems are NP-complete, and therefore, it is important to realize whether a problem is NP-complete.  If it is, then your goal is to find a solution that is good enough, because an efficient algorithm is almost impossible to find.

In the next chapter, we look at the insertion sort algorithm in more detail.