Introduction

What is an algorithm?

A sequence of steps which provides a solution to a given problem, irrespective of the input.

What does "design & analysis of algorithms" mean?

We should understand this — it is the name of the course, after all.

• Correctness of the algorithms
• Does it terminate?
• Efficient (fast):
  • Estimate the running time.
  • Count the number of steps*.***
  • Is it optimal? Can we do better?

Remarks:

• Near the end of the term, we will speak about the limits of efficiency. Even all of the tools we will learn about in this course have their limits, since some problems simply *cannot *****be solved efficiently.
• This course requires no programming; we will be using pseudocode to write algorithms.

Insertion Sort

Insertion sort demo.

Input: An array A[1..n] of n numbers.

Output: An array containing the numbers of A in increasing order.

// Note: all indices are 1-indexed
**for** *j* = 2 to *n* **do**
	*key* = *A*[*j*]
	*i* = *j* - 1;
	**while** *i* > 0 and *A*[*i*] > *key* **do**
		*A*[*i*+1] = *A*[*i*]
		*i* = *i* - 1
	**end while**
	*A*[*i*+1] = *key*
**end for**

What is the "best" input for Insertion Sort?

An array sorted in increasing order.

What is the "worst" input for Insertion Sort?