## 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?
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 (
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) An algorithm is
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.
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 To compare the performance of two algorithms, we further introduce the Big-O notation: So for algorithm A with time complexity and algorithm B with time complexity , if , then Note that the two example algorithms (find min/max) in section 1.1 both have time complexity .
## 1.4 PseudocodePseudocode 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. |

© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk |