CSE408

in
Fundamentals of

y.
ud
Algorithms

st
ty
si
er
iv
un

Lecture #1

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
What is an algorithm?

An algorithm is a sequence of unambiguous instructions

for solving a problem, i.e., for obtaining a required

in
output for any legitimate input in a finite amount of time.

y.
ud
st
problem

ty
si
er
iv
algorithm
un

input “computer” output

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm

An algorithm is a sequence of unambiguous

instructions for solving a problem, i.e., for obtaining a

in
y.
required output for any legitimate input in a finite

ud
amount of time.

st
ty
• Can be represented various forms
si
er
iv
• Unambiguity/clearness
un

• Effectiveness
• Finiteness/termination
• Correctness
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Historical Perspective

Euclid’s algorithm for finding the greatest common divisor

in
Muhammad ibn Musa al-Khwarizmi – 9th century

y.
mathematician

ud
www.lib.virginia.edu/science/parshall/khwariz.html

st
ty
si
er
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Notion of algorithm and problem

problem

in
y.
ud
algorithm

st
ty
si
er
input “computer” output
iv

(or instance)
un

algorithmic solution
(different from a conventional solution)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Example of computational problem: sorting

Statement of problem:
• Input: A sequence of n numbers <a1, a2, …, an>

in
• Output: A reordering of the input sequence <a´1, a´2, …, a´n> so that a´i

y.
≤ a´j whenever i < j

ud
st
Instance: The sequence <5, 3, 2, 8, 3>

ty
si
Algorithms: er
• Selection sort
iv
• Insertion sort
un

• Merge sort
• (many others)

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Selection Sort

Input: array a[1],…,a[n]

in
Output: array a sorted in non-decreasing order

y.
ud
st
Algorithm:

ty
si
er
iv
for i=1 to n
un

swap a[i] with smallest of a[i],…,a[n]

• Is this unambiguous? Effective?

• See also pseudocode, section 3.1
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Some Well-known Computational Problems

Sorting
Searching

in
Shortest paths in a graph

y.
Minimum spanning tree

ud
Primality testing

st
Traveling salesman problem

ty
Knapsack problem
Chess
si
er
Towers of Hanoi
iv
un

Program termination

Some of these problems don’t have efficient algorithms,

or algorithms at all!
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Basic Issues Related to Algorithms

How to design algorithms

How to express algorithms

in
y.
ud
Proving correctness

st
Efficiency (or complexity) analysis

ty
• Theoretical analysis
si
er
• Empirical analysis
iv
un

Optimality

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm design strategies

in
Brute force Greedy approach

y.
ud
Divide and conquer Dynamic programming

st
ty
Decrease and conquer

si
er Backtracking and branch-and-bound
Transform and conquer
iv
Space and time tradeoffs
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Analysis of Algorithms

How good is the algorithm?

• Correctness

in
• Time efficiency

y.
• Space efficiency

ud
st
Does there exist a better algorithm?

ty
si
• Lower bounds er
• Optimality
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
What is an algorithm?

Recipe, process, method, technique, procedure, routine,…

with the following requirements:

in
1. Finiteness

y.
terminates after a finite number of steps

ud
2. Definiteness

st
rigorously and unambiguously specified

ty
3. Clearly specified input
valid inputs are clearly specified
si
er
4. Clearly specified/expected output
iv
can be proved to produce the correct output given a valid input
un

5. Effectiveness
steps are sufficiently simple and basic

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Why study algorithms?

Theoretical importance

in
• the core of computer science

y.
ud
Practical importance

st
ty
si
• A practitioner’s toolkit of known algorithms er
iv
• Framework for designing and analyzing algorithms for new problems
un

Example: Google’s PageRank Technology

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Euclid’s Algorithm

Problem: Find gcd(m,n), the greatest common divisor of two

nonnegative, not both zero integers m and n

in
y.
Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?

ud
st
ty
Euclid’s algorithm is based on repeated application of equality
gcd(m,n) = gcd(n, m mod n) si
er
iv
until the second number becomes 0, which makes the problem
un

trivial.

Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Two descriptions of Euclid’s algorithm

Step 1 If n = 0, return m and stop; otherwise go to Step 2

Step 2 Divide m by n and assign the value of the remainder to r

in
Step 3 Assign the value of n to m and the value of r to n. Go to

y.
Step 1.

ud
st
ty
while n ≠ 0 do
si
er
r ← m mod n
iv
un

m← n
n←r
return m

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Other methods for computing gcd(m,n)

Consecutive integer checking algorithm

Step 1 Assign the value of min{m,n} to t

in
Step 2 Divide m by t. If the remainder is 0, go to Step 3;

y.
otherwise, go to Step 4

ud
Step 3 Divide n by t. If the remainder is 0, return t and stop;

st
ty
otherwise, go to Step 4
Step 4 Decrease t by 1 and go to Step 2
si
er
iv
un

Is this slower than Euclid’s algorithm?

How much slower?

O(n), if n <= m , vs O(log n)

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Other methods for gcd(m,n) [cont.]

Middle-school procedure
Step 1 Find the prime factorization of m

in
Step 2 Find the prime factorization of n

y.
ud
Step 3 Find all the common prime factors

st
Step 4 Compute the product of all the common prime factors

ty
and return it as gcd(m,n)
si
er
iv
Is this an algorithm?
un

How efficient is it?

Time complexity: O(sqrt(n))
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Fundamentals of Algorithmic Problem Solving

in
y.
ud
st
ty
si
er
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Two main issues related to algorithms

How to design algorithms

in
y.
ud
How to analyze algorithm efficiency

st
ty
si
er
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm design techniques/strategies

Brute force Greedy approach

in
y.
ud
Divide and conquer Dynamic programming

st
ty
Decrease and conquer Iterative improvement
si
er
iv
Transform and conquer Backtracking
un

Space and time tradeoffs Branch and bound

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Analysis of algorithms

How good is the algorithm?

• time efficiency

in
• space efficiency

y.
• correctness ignored in this course

ud
st
ty
Does there exist a better algorithm?
• lower bounds si
er
iv
• optimality
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Important problem types

sorting

in
searching

y.
ud
string processing

st
ty
graph problems
si
er
combinatorial problems
iv
un

geometric problems

numerical problems

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Sorting (I)

Rearrange the items of a given list in ascending order.

• Input: A sequence of n numbers <a1, a2, …, an>
• Output: A reordering <a´1, a´2, …, a´n> of the input sequence such that a´1≤

in
a´2 ≤ … ≤ a´n.

y.
Why sorting?

ud
• Help searching

st
• Algorithms often use sorting as a key subroutine.

ty
Sorting key

si
• A specially chosen piece of information used to guide sorting. E.g., sort
er
student records by names.
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Sorting (II)

Examples of sorting algorithms

in
• Selection sort

y.
• Bubble sort

ud
• Insertion sort
• Merge sort

st
• Heap sort …

ty
Evaluate sorting algorithm complexity: the number of key comparisons.
Two properties
si
er
• Stability: A sorting algorithm is called stable if it preserves the relative order of any
iv
two equal elements in its input.
un

• In place : A sorting algorithm is in place if it does not require extra memory,

except, possibly for a few memory units.

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Selection Sort

in
Algorithm SelectionSort(A[0..n-1])

y.
//The algorithm sorts a given array by selection sort

ud
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order

st
for i  0 to n – 2 do

ty
min  i
for j  i + 1 to n – 1 do
si
er
if A[j] < A[min]
iv
min  j
un

swap A[i] and A[min]

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Searching

Find a given value, called a search key, in a given set.

Examples of searching algorithms

in
• Sequential search

y.
• Binary search …

ud
Input: sorted array a_i < … < a_j and key x;

st
ty
m (i+j)/2;
while i < j and x != a_m do si
er
if x < a_m then j  m-1
iv
un

else i  m+1;
if x = a_m then output a_m;

Time: O(log n)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
String Processing

A string is a sequence of characters from an alphabet.

Text strings: letters, numbers, and special characters.

in
String matching: searching for a given word/pattern in a text.

y.
ud
st
ty
Examples:
si
er
(i) searching for a word or phrase on WWW or in a
iv

Word document
un

(ii) searching for a short read in the reference genomic

sequence

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
 in
y.
ud
st
ty
si
er
iv
un

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1