1.  Basic concepts

1.1 What are algorithms?

To answer what is an algorithm, we consider the following problem. Assume we are given n distinct integers. We want to find both the maximum and minimum integers in the input. What method can we use to solve this problem?

Method 1.  Find-max-and-then-min
Input: n distinct  integers 
Let max = 
For each x = 
    If x > max, replace max by x
Let min = 
For each x = 
    If x < min, replace min by x
Return both max and min

The correctness of this method is obvious. Assume is the maximum. When we set , is true, so max will be replaced by . And for any other , x > max is false, so will remain as the max value, which is finally returned by the method. How many integer comparisons are done by the method? Simple counting shows that the total number of comparisons is 2 (n - 1). Can we have another method to find both max and min in less than 2 (n - 1) comparisons? Below is more efficient method. For simplicity, we assume n is even.

Method 2. Find-max-and-min-together
Input: n distinct integer 
If , let max =  and min = 
Otherwise, let max =  and min = 
For each j = 3, 5, …, n-1
    If 
        If  > max, replace max by 
        If  < min, replace min by 
    Otherwise, i.e., 
        If  < min, replace min by 
        If  > max, replace max by 
Return both max and min

Simple argument can show that Method 2 is correct. To count the number of comparisons, notice that at most three comparisons are made for every two integers. Hence the number of comparisons is at most (3 / 2) n, which is less than 2(n - 1) for any . Hence, we have a more efficient method (in fact the method could be proved optimal, see [1] if you are interested).

An algorithm is a method to solve a problem. A typical algorithm initially takes in some input (could be empty), follows a well-defined sequence of steps, and finally yields the output. While different books may have slightly different definition on algorithms, we use the following definition from Wikipedia.

1.2 Performance of different algorithms

For any specific problem, there are many different algorithms (or methods) to solve the problem. Different algorithms can have widely different performance. We usually decide which algorithm to use for a specific problem based on the following performance measures.

• Time efficiency
• Some methods are more effective and faster than others
• Space efficiency
• Implementation simplicity
• Degree of correctness

It is important to know how to evaluate a program’s performance, and it is always beneficial if we manage to design efficient algorithms which are running faster, occupying less memory space, being more accurate, etc. Though it is worth mentioning that in many situations the method to solve a problem appears very natural. It is not the case in some others, i.e. there are ‘hard’ problems which require algorithmic knowledge to deal with.

1.3  Time Complexity

To evaluate an algorithm’s time efficiency, a classical way is to count the number of atom steps executed. Let  be the maximum number of steps that the algorithm uses on any input of size n, then is called the algorithm’s time complexity.

To compare the performance of two algorithms, we further introduce the Big-O notation:
Definition (Definition 7.2 [1]):
Let f and g be functions  . Say that  if positive integers c and  exist such that for every integer

So for algorithm A with time complexity and algorithm B with time complexity , if , then asymptotically algorithm A is better than or at least equal to algorithm B.

Note that the two example algorithms (find min/max) in section 1.1 both have time complexity .

1.4 Pseudocode

Pseudocode is used for expressing algorithms. Compared with purely natural language described algorithms, pseudocode has an explicit control structure (e.g. branch, loop) which make it looks similar to programming languages. Meanwhile pseudocode keeps the flexibility of using natural language and mathematical symbols which are independent of specific programming languages. Thus pseudocode is widely used as an intermediate representation among programmers of different languages. Also, pseudocode written algorithms usually could be conveniently translated into working ones with practical programming languages.

The two example algorithms in section 1.1 are written in pseudocode.

1.5 How to be good at algorithms?

With this website, you will learn algorithms by the following three steps.

• Fundamental problems: Sorting, searching and selection, data structures
• General algorithm design methodologies: Divide-and-conquer, greedy, dynamic programming
• Specific topics: Graphs, coordinate geometry, numerical algorithms, string processing, linear programming

[1] A proof for the lower bound of find-min-max problem.
[2] M. Sipser. Introduction to the theory of computation. Computer Science Series. Thomson Course Technology, 2006.