. . ..

Design and Analysis of Algorithms

. Lecture 1: Introduction
Ahmed Khademzadeh http://khademzadeh.mshdiau.ac.ir Azad University of Mashhad

. .

The slides are borrowed from Ke (Kevin) Yi. Thanks to him for his benevolence. Lecture 1: Introduction Design and Analysis of Algorithms

. Outline

What is this course about? What are algorithms? What does it mean to analyze an algorithm? Comparing time complexity Thoughts on algorithm design

Lecture 1: Introduction

Design and Analysis of Algorithms

. What is this course about?

. Example (Chain Matrix Multiplication) .. A=C = 1 1 0 1 1 0 B = D = . 1 1 [ ] . .

Want: ABCD =? Method 1: (AB)(CD) Method 2: A((BC )D) Method 1 is much more ecient than Method 2. (Expand the expression on board) . ..
Lecture 1: Introduction Design and Analysis of Algorithms

. What is this course about?

There is usually more than one algorithm for solving a problem. Some algorithms are more ecient than others. We want the most ecient algorithm.

Lecture 1: Introduction

Design and Analysis of Algorithms

. What is this course about?

If we a number of alternative algorithms for solving a problem, how do we know which is the most ecient? To do so, we need to analyze each of them to determine its eciency. Of course, we must also make sure the algorithm is correct.

Lecture 1: Introduction

Design and Analysis of Algorithms

. What is this course about?

In this course, we will discuss fundamental techniques for: .. 1 Proving the correctness of algorithms,

. ... ... ...

2 3 4

Analyzing the running times of algorithms, Designing ecient algorithms, Showing ecient algorithms do not exist for some problems

Notes: Analysis and design go hand-in-hand: By analyzing the running times of algorithms, we will know how to design fast algorithms. In Data Structure course, you have learned techniques for 1, 2, 3 w.r.t sorting and searching. In this course, we will discuss them in the contexts of other problems.
Lecture 1: Introduction Design and Analysis of Algorithms

. What is this course about?

Dierences between Data Sturcture and Algorithm Design Course: . Data Sturcture . . Algorithm Design Analysis .. .. The name is Data Sturcture The name is Algorithm Design Analysis Simpler problems You learn concrete problems: sorting, searching (binary tree), etc. You know how to solve these concrete problems. . .. . . . .. Harder problems You learn general techniques via concrete problems: divide-and-conquer, dynamic programming, etc. You can solve many new problems using these techniques. . .

Lecture 1: Introduction

Design and Analysis of Algorithms

. Outline

What is this course about? What are algorithms? What does it mean to analyze an algorithm? Comparing time complexity Thoughts on algorithm design

Lecture 1: Introduction

Design and Analysis of Algorithms

. Computational Problem
. Denition .. A computational problem is a specication of the desired input-output relationship . .. . Example (Computational Problem) .. Sorting Input: Sequence of n numbers a1 , , an Output: Permutation (reordering)
a1 , a2 , , an

. ..

such that a1 a2 an

Lecture 1: Introduction

Design and Analysis of Algorithms

. Instance

. Denition .. A problem instance any valid input to the problem. . .. . Example (Instance of the Sorting Problem) .. 8, 3, 6, 7, 1, 2, 9 . ..

. . . . . .

Lecture 1: Introduction

Design and Analysis of Algorithms

. Algorithm

. Denition . .. An algorithm is a well dened computational procedure that transforms inputs into outputs, achieving the desired input-output relationship . .. . . Denition . .. A correct algorithm halts with the correct output for every input instance. We can then say that the algorithm solves the problem . .. .

Lecture 1: Introduction

Design and Analysis of Algorithms

. Example: Insertion Sort

Pseudocode:
Input: A[1 . . . n] is an array of numbers for j=2 to n do key = A[j]; i = j-1; while i 1 and A[i] > key do A[i+1] = A[i]; i- -; end A[i+1] = key; end

key Sorted Unsorted Where in the sorted part to put key?

Lecture 1: Introduction

Design and Analysis of Algorithms

. How Does It Work?

An incremental approach: To sort a given array of length n, at the ith step it sorts the array of the rst i items by making use of the sorted array of the rst i 1 items in the (i 1)th step . Example .. Sort A = 6, 3, 2, 4, 5 with insertion sort Step 1: 6, 3, 2, 4, 5 Step 2: 3, 6, 2, 4, 5 Step 3: 2, 3, 6, 4, 5 Step 4: 2, 3, 4, 6, 5 . .. . Step 5: 2, 3, 4, 5, 6 . .

Lecture 1: Introduction

Design and Analysis of Algorithms

. Outline

What is this course about? What are algorithms? What does it mean to analyze an algorithm? Comparing time complexity Thoughts on algorithm design

Lecture 1: Introduction

Design and Analysis of Algorithms

. Analyzing Algorithms
Predict resource utilization .. 1 Running time (time complexity) focus of this course .. 2 Memory (space complexity)

. .

Running time: the number of primitive operations (e.g., addition, multiplication, comparisons) used to solve the problem Depends on problem instance: often we nd an upper bound: T(input size) and use asymptotic notations (big-Oh) To make your life easier! Growth rate much more important than constants in big-Oh. Input size n: rigorous denition given later sorting: number of items to be sorted graphs: number of vertices and edges

Lecture 1: Introduction

Design and Analysis of Algorithms

. Three Cases of Analysis: I

Best Case: An instance for a given size n that results in the fastest possible running time. . Example (Insertion sort) . .. A[1] A[2] A[3] A[n] The number of comparisons needed is equal to 1 + 1 + 1 + + 1 = n 1 = O(n) . ..
n1

.
key Sorted Unsorted key is compared to only the element right before it.

Lecture 1: Introduction

Design and Analysis of Algorithms

. Three Cases of Analysis: II

Worst Case: An instance for a given size n that results in the slowest possible running time. . Example (Insertion sort) .. A[1] A[2] A[3] A[n] The number of comparisons needed is equal to 1 + 2 + + (n 1) = n(n 1) = O(n2 ) 2

. ..

key Sorted Unsorted key is compared to everything element before it.

Lecture 1: Introduction

Design and Analysis of Algorithms

. Three Cases of Analysis: III

Average Case: T running time averaged over all possible instances for the given size, assuming some probability distribution on the instances. . Example (Insertion sort) . .. 2 ), assuming that each of the n! instances is equally likely (n (uniform distribution). . .. .
key Sorted Unsorted On average, key is compared to half of the elements before it.

Lecture 1: Introduction

Design and Analysis of Algorithms

. Three Cases of Analysis

Best case: Clearly the worst Worst case: Commonly used, will also be used in this course
Gives a running time guarantee no matter what the input is Fair comparison among dierent algorithms

Average case: Used sometimes

Need to assume some distribution: real-world inputs are seldom uniformly random! Analysis is complicated Will seldom be used in this course

Lecture 1: Introduction

Design and Analysis of Algorithms

. Outline

What is this course about? What are algorithms? What does it mean to analyze an algorithm? Comparing time complexity Thoughts on algorithm design

Lecture 1: Introduction

Design and Analysis of Algorithms

. Example
Algorithm 1 T (n)

Algorithm 2

Algorithm 2 is clearly superior T (n) for Algorithm 1 is O(n3 ) T (n) for Algorithm 2 is O(n2 ) Since n3 grows much more rapidly, we expect Algorithm 1 to take much more time than Algorithm 2 when n increases
Lecture 1: Introduction Design and Analysis of Algorithms

. Growth Rate
Given algorithms A and B with running times TA (n) and TB (n): TA (n) = 0, we say TA has a lower asymptotic growth TB (n) rate than TB . (Thus, A runs faster than B for large n.) If limn TA (n) = , we say TA has a higher asymptotic growth TB (n) rate than TB . (Thus, A runs slower than B for large n.) If limn TA (n) < , we say TA is asymptotically equivalent TB (n) to TB . (Thus, the running times of A and B are equal up to constant factors.) If 0 < limn Note that dierences in constant factors are ignored!
Lecture 1: Introduction Design and Analysis of Algorithms

. Big-Oh
Asymptotic upper bound . Denition (Big-Oh) . .. f (n) = O(g (n)): There exists constant c > 0 and n0 such that f (n)c g (n) for n n0 . .. . When estimating the growth rate of T (n) using big-Oh: ignore the low order terms ignore the constant coecient of the most signicant term . Example . .. Algorithm 1 runs in O(n3 ) time and Algorithm 2 runs in O(n2 ) time . .. . . Example . .. 3 ) time, but we usually It is also OK to say Algorithm 2 runs in O(n want to be as tight as possible . .. .
Lecture 1: Introduction Design and Analysis of Algorithms

. Example .. n2 /2 3n = O(n2 ) 1 + 4n = O(n) log10 n =

log2 n log2 10

= O(log2 n) = O(log n)

sin n = O(1), 10 = O(1), 1010 = O(1) n 2 i n n2 = O(n3 ) i=1 n 2 i=1 i n n = O(n ) 210n is not O(2n ) log(n!) = log(n) + log(n 1) + + log 1 = O(n log n) n 1 (on board) i=1 i = O(log n) . .

. ..

Lecture 1: Introduction

Design and Analysis of Algorithms

. Big Omega and Big Theta

Asymptotic lower bound . Denition (big-Omega) .. f (n) = (g (n)): There exists constant c > 0 and n0 such that f . (n) c g (n) for n n0 . .. Asymptotic tight bound . Denition (big-Theta) .. f (n) = (g (n)): f (n) = O(g (n)) and f (n) = (g (n)) . .. . Example .. n2 /2 3n = (n2 ) log(n!) = log(n) + log(n 1) + + log 1 log(n) + log(n 1) + + log(n/2) n/2 log(n/2) = n/2 (log n 1) = (n log n). . ..
Lecture 1: Introduction Design and Analysis of Algorithms

. . . . .

. Big Omega and Big Theta

. Example . .. 3 ) time (we can show that any instance If Algorithm 1 runs in O(n of size n, the algorithm takes at most O(n3 ) time), and Algorithm 1 runs in (n3 ) time (there is an instance of size n on which the algorithm spends (n3 ) time), then we say Algorithm 1 runs in (n3 ) time. . .. Usually (and in this course), it is sucient to show only upper bounds (big-Oh).

Lecture 1: Introduction

Design and Analysis of Algorithms

. Outline

What is this course about? What are algorithms? What does it mean to analyze an algorithm? Comparing time complexity Thoughts on algorithm design

Lecture 1: Introduction

Design and Analysis of Algorithms

. Some Thoughts on Algorithm Design

Algorithm Design, as taught in this class, is mainly about designing algorithms that have small big-Oh running times As n gets larger and larger, O(n log n) algorithms will run faster than O(n2 ) ones and O(n) algorithms will beat O(n log n) ones Good algorithm design & analysis allows you to identify the hard parts of your problem and deal with them eectively Too often, programmers try to solve problems using brute force techniques and end up with slow complicated code! A few hours of abstract thought devoted to algorithm design often results in faster, simpler, and more general solutions.

Lecture 1: Introduction

Design and Analysis of Algorithms

. Algorithm Tuning

After algorithm design one can continue on to Algorithm tuning concentrate on improving algorithms by cutting down on the constants in the big O() bounds needs a good understanding of both algorithm design principles and ecient use of data structures In this course we will not go further into algorithm tuning For a good introduction, see chapter 9 in Programming Pearls, 2nd ed by Jon Bentley

Lecture 1: Introduction

Design and Analysis of Algorithms