### 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.