1/17/2019

Tassos Dimitriou

CpE-203
Discrete Structures

Set 7

Prof. Tassos Dimitriou

Computer Engineering Department

Kuwait University

CpE-203: Discrete Structures 1

Tassos Dimitriou

Outline
Algorithms
 Why study them?
 Definitions
 Problems and instances
 Analysis of Algorithms
 Examples

CpE-203: Discrete Structures 2

1
 1/17/2019

Tassos Dimitriou

Algorithms
There are many general classes of problems that arise in
discrete mathematics.
 Given a sequence of integers, find the largest one; given a set, list
all its subsets; given a set of integers, put them in increasing
order; given a network, find the shortest path between two
vertices, and so on.
 First thing to do is to construct a model. Discrete structures used
in such models include sets, sequences as well as permutations,
relations, graphs, trees, networks, etc..

To complete the solution, a method is needed that will solve

the general problem using the model. Such a method is called
an algorithm.

CpE-203: Discrete Structures 3

Tassos Dimitriou

Why study algorithms?

Algorithms are everywhere
 Routing in communication networks -> classical shortest-path
algorithms
 The effectiveness of security in the Internet -> number-theoretic
algorithms
 Computer graphics -> computational primitives supplied by
geometric algorithms
 Database search -> balanced search tree data structures
 Computational biology -> dynamic programming algorithms to
measure genome similarity, and so on.

CpE-203: Discrete Structures 4

2
 1/17/2019

Tassos Dimitriou

Why study algorithms?

Algorithms play a key role in modern technological
innovation
 Effectiveness of search engines -> Google’s “PageRank”
algorithm to measure similarity of web pages
 “Everyone knows Moore’s Law – a prediction made in 1965 by
Intel co-founder Gordon Moore that the density of transistors in
integrated circuits would continue to double every 1 to 2
years….in many areas, performance gains due to improvements
in algorithms have vastly exceeded even the dramatic
performance gains due to increased processor speed.”
 Excerpt from Report to the President and Congress: Designing a Digital
Future, December 2010 (page 71).

It can be good for the brain!

CpE-203: Discrete Structures 5

Tassos Dimitriou

What is an Algorithm?
An algorithm is a procedure for solving a usually
complicated problem by carrying out a precisely
determined sequence of simpler, unambiguous steps.

Basically a recipe for solving a problem!

This is a rather
Step 1: Do something vague definition.
You will get to know
Step 2: Do something a more precise
Step 3: Do something else definition when you
attend CpE300
…

CpE-203: Discrete Structures 6

3
 1/17/2019

Tassos Dimitriou

A tribute to Al-Khawarizmi
The word algorithm comes from the world algorism which means
working with decimal numerals.
 Abu Abdullah Mohammad Ibn Musa al-Khawarizmi was born at
Khawarizm (Kheva), south of Aral sea. Very little is known about his
early life, except for the fact that his parents had migrated to a place
south of Baghdad.
 His work on algebra was outstanding, which established him as the
founder of Algebra. The very name Algebra has been derived from his
famous book Al-Kitāb al-mukhtaṣar fī hīsāb al-ğabr wa’l-muqābala. It
was this book which introduced this new science to the West
“completely unknown till then”.
 The influence of Khawarizmi on the growth of science, in general, and
mathematics, astronomy and geography in particular, is well
established in history. Several of his books were readily translated into
a number of other languages, and, in fact, constituted the university
textbooks till the 16th century.

CpE-203: Discrete Structures 7

Tassos Dimitriou

Properties of Algorithms
• Input from a specified set,
• Output from a specified set (solution to the problem),
• Definiteness of every step in the computation,
• Correctness of output for every possible input,
• Finiteness of the number of calculation steps,
• Effectiveness of each calculation step and
• Generality for a class of problems.

CpE-203: Discrete Structures 8

4
 1/17/2019

Tassos Dimitriou

Problems and Instances

When an input set is given and some output result is
required, we say we have an instance of a problem.
 Different instances with the same input-output relationship will
constitute a problem given in some general form like:
Input: sequence <a1, a2, …, an> of n numbers.
Sorting
problem Output: permutation <a'1, a'2, …, a'n> such
that a'1  a'2  …  a'n .

Example:
Input: 8 2 4 9 3 6
Output: 2 3 4 6 8 9
Instances
Input: 5 -1 2 1 9 3 4 8
Output: -1 1 2 3 4 5 8 9
CpE-203: Discrete Structures 9

Tassos Dimitriou

Algorithm Examples
Can be described using pseudocode, which slightly reminds
us of JAVA or C, etc.

Example: Can you come up with an algorithm that finds the

maximum element of a sequence of n numbers a1, a2, …, an?

procedure max(a1, a2, …, an)

max = a1
for i = 2 to n
if (max < ai) then max = ai

CpE-203: Discrete Structures 10

5
 1/17/2019

Tassos Dimitriou

Linear search
An algorithm that linearly searches a sequence for a particular
element.

procedure linear_search(x; a1, a2, …, an)

i = 1
while (i  n and x  ai)
i = i + 1
end-while

if i  n then
OUTPUT “Found at location i"
else
OUTPUT “Not Found“

CpE-203: Discrete Structures 11

Tassos Dimitriou

Binary search
But what if the terms in a sequence are ordered? Can we do
better than just scanning a list from left to right?

YES! A binary search algorithm is more efficient than linear

search.

The binary search algorithm iteratively restricts the relevant

search interval by half until it closes in on the position of the
element to be located.

CpE-203: Discrete Structures 12

6
 1/17/2019

Tassos Dimitriou

Binary search (cont.)

Binary search for the letter ‘j’

search interval

a c d f g h j l m o p r s u v x z

center element

CpE-203: Discrete Structures 13

Tassos Dimitriou

Binary search (cont.)

Binary search for the letter ‘j’

search interval

a c d f g h j l m o p r s u v x z

center element

CpE-203: Discrete Structures 14

7
 1/17/2019

Tassos Dimitriou

Binary search (cont.)

Binary search for the letter ‘j’

search interval

a c d f g h j l m o p r s u v x z

center element

CpE-203: Discrete Structures 15

Tassos Dimitriou

Binary search (cont.)

Binary search for the letter ‘j’

search interval

a c d f g h j l m o p r s u v x z

center element

CpE-203: Discrete Structures 16

8
 1/17/2019

Tassos Dimitriou

Binary search (cont.)

Binary search for the letter ‘j’

search interval

a c d f g h j l m o p r s u v x z

center element

Found !
CpE-203: Discrete Structures 17

Tassos Dimitriou

Binary search
// Find x in ordered list a1, a2, …, an

procedure BinarySearch(x; a1, a2, …, an)

i := 1 // i is left endpoint of search interval
j := n // j is right endpoint of search interval

while (i < j) do
m := (i + j)/2 // middle point
if x > am then i := m + 1
else j := m
end-while

if x = ai then then OUTPUT “Found at location i“

else OUTPUT “Not Found“

CpE-203: Discrete Structures 18

9
 1/17/2019

Tassos Dimitriou

Complexity of algorithms
Big questions
 When does an algorithm provide a satisfactory solution to a
problem?
 Given an algorithm, how can we compare it with other
algorithms that solve the same problem?
 How can the efficiency of an algorithm be analyzed?
 What are the criteria that help us judge the quality of an
algorithm?

Questions as the above are important from both a theoretical

and a practical point of view.

CpE-203: Discrete Structures 19

Tassos Dimitriou

Worst case analysis

When analyzing an algorithm we (usually) look at the number
of steps required in the worst case scenario (no matter what
the input is)

Worst-case:

T(n) = maximum time of algorithm on any input of size n.

CpE-203: Discrete Structures 20

10
 1/17/2019

Tassos Dimitriou

Why look at worst case analysis?

Clean interface:
 A guarantee on running time suggests that we can use the algorithm as a
subroutine without needed to worry about the inputs..
Scaling
 Worst case analysis tells us how the running
time scales with the size of the input.
 This gives us an idea about how big problem
instances we can handle

Designing better algorithms

 Analyzing the worst case running time often
leads to an understanding that helps design
even better algorithms or tell what parts of the
algorithm are crucial

CpE-203: Discrete Structures 21

Tassos Dimitriou

Why look at worst case analysis?

Murphy’s Law: Anything that can go wrong, will go wrong

CpE-203: Discrete Structures 22

11
 1/17/2019

Tassos Dimitriou

Time complexity
In general, we are not so much interested in the time and
space complexity for small inputs.

For example, while the difference in time complexity between

linear and binary search is meaningless for a sequence with
n = 10, it is gigantic for n = 230.

CpE-203: Discrete Structures 23

Tassos Dimitriou

Time complexity (cont.)

For example, let us assume two algorithms A and B that solve
the same problem.

The time complexity of A is 5,000n, the one for B is 1.1n for

an input with n elements.

 For n = 10, A requires 50,000 steps, but B only 3, so B seems to

be superior to A.

 For n = 1000, however, A requires 5,000,000 steps, while B

requires 2.51041 steps.

CpE-203: Discrete Structures 24

12
 1/17/2019

Tassos Dimitriou

Time complexity (cont.)

This means that algorithm B cannot be used for large inputs,
while algorithm A is still feasible.

So what is important is the growth of the time complexity

function.

 The growth of time and space complexity as a function of the

input size n is a suitable measure for the comparison of
algorithms.

CpE-203: Discrete Structures 25

Tassos Dimitriou

Time complexity (cont.)

Comparison: Time complexity of algorithms A and B

Input Size Algorithm A Algorithm B

n 5,000n 1.1n

10 50,000 3

100 500,000 13,781

1,000 5,000,000 2.5*1041

1,000,000 5*109 4.8*1041392

CpE-203: Discrete Structures 26

13
 1/17/2019

Tassos Dimitriou

Oh-notation
Generally, the complexity is expressed using “big O”
notation.
 Captures the order of magnitude of the computational complexity
and hides the underlying constants.
 Thus an algorithm taking 2n2 + 3n +100 steps to sort a sequence
of numbers is O(n2). [It is read “order n squared”]

Why do that?
 Makes complexity analysis system independent. You don’t have
to know the exact timings of various instructions or the speed of
the processor.
 These differences “disappear” when the size of the input
increases…

CpE-203: Discrete Structures 27

Tassos Dimitriou

Oh-notation
Definition
 The running time T(n) of an algorithm is O(f(n)) if there is some
constant c such that for large enough inputs, T(n) < cf(n)

In pictures cf(n)

T(n)

n0 n

CpE-203: Discrete Structures 28

14
 1/17/2019

Tassos Dimitriou

Growth of Functions
This notation can be used for any functions f and g.

Definition: Let f and g be positive functions from the integers

to the real numbers.
 We say that f(n) is O(g(n)) if there are constants c and k such
that
f(n)  c g(n),
whenever n > k.

If we want to show that f(x) is O(g(x)), we only

need to find one pair (c, k) such that f(n)  c g(n).

CpE-203: Discrete Structures 29

Tassos Dimitriou

Oh-notation
5000000 40000
T1(n) 35000
T3(n)
4000000 0.01n2 = O(n2) 30000
10-6 2n =O(2n)
3000000 25000

2000000
T2(n) 20000

15000

1000000 100n = O(n) 10000 106n2

5000 T4(n)
0
1000 5000 9000 13000 17000 0
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

This notation allows us to see how the input size affects the time
and space requirements

CpE-203: Discrete Structures 30

15
 1/17/2019

Tassos Dimitriou

Growth of Functions (cont.)

The idea behind the big-O notation is to establish an upper
bound for the growth of a function f(n) for large n.

 This boundary is specified by a function g(n) that is usually

much simpler than f(n).

 We accept the constant c in the requirement f(n)  c g(n),

whenever n > k, because c does not grow with x.

We are only interested in large n, so it is OK if

f(n) > cg(n) for x  k.

CpE-203: Discrete Structures 31

Tassos Dimitriou

Growth of Functions (cont.)

Example: Show that f(x) = x2 + 2x + 1 is O(x2).

 For x > 1 we have:

x2 + 2x + 1  x2 + 2x2 + x2  4x2

 Therefore, for c = 4 and k = 1, f(x)  cx2 whenever x > k.

 Thus f(x) = O(x2).

CpE-203: Discrete Structures 32

16
 1/17/2019

Tassos Dimitriou

Growth of Functions (cont.)

Question: If f(x) is O(x2), is it also O(x3)?

 Yes. x3 grows faster than x2, so x3 grows also faster than f(x).

 Therefore, we always have to find the smallest simple function

g(x) for which f(x) is O(g(x)).

CpE-203: Discrete Structures 33

Tassos Dimitriou

Growth of Functions (cont.)

“Popular” functions are

n log n, 1, 2n, n2, n!, n, n3, log n

Listed from slowest to fastest growth:

• 1 Vertical scale in this

• log n graph is logarithmic
• n
• n log n
• n2
• n3
• 2n
• n!

CpE-203: Discrete Structures 34

17
 1/17/2019

Tassos Dimitriou

Growth of Functions (cont.)

A problem that can be solved with polynomial worst-case
complexity is called tractable.

Problems of higher complexity are called intractable.

Problems that no algorithm can solve are called unsolvable.

CpE-203: Discrete Structures 35

Tassos Dimitriou

Classification of algorithms
Algorithms are classified according to their time or space
complexities:
 An algorithm is constant if its complexity is independent of
n; in symbols O(1)
 An algorithm is linear if its time complexity is O(n)
 Algorithms can also be quadratic, cubic, and so on. All
these algorithms are called polynomial time algorithms.
Their complexity is O(nk), for some constant k.
 Algorithms whose complexity is O(cf(n)), where c is some
constant greater than 1 and f(n) some polynomial function
of n, are called exponential.

CpE-203: Discrete Structures 36

18
 1/17/2019

Tassos Dimitriou

Useful Rules for Big-Oh

For any polynomial f(x) = anxn + an-1xn-1 + … + a0, where a0,
a1, …, an are real numbers,
f(x) = O(xn).

If f1(x) is O(g1(x)) and f2(x) is O(g2(x)), then

(f1 + f2)(x) = O(max(g1(x), g2(x)))

If f1(x) is O(g(x)) and f2(x) is O(g(x)), then

(f1 + f2)(x) = O(g(x)).

If f1(x) is O(g1(x)) and f2(x) is O(g2(x)), then

(f1f2)(x) = O(g1(x) g2(x)).

CpE-203: Discrete Structures 37

Tassos Dimitriou

Analysis of Algorithms - example

What does the following algorithm compute?

procedure who_knows(a1, a2, …, an)

m=0
for i = 1 to n-1
for j = i + 1 to n
if |ai – aj| > m then m := |ai – aj|
return m

Answer: The algorithm returns the maximum difference

between any two numbers in the input sequence
What is the number of comparisons made?
Answer: n-1 + n-2 + n-3 + … + 1 = (n – 1)n/2 = 0.5n2 – 0.5n

Time complexity is O(n2).

CpE-203: Discrete Structures 38

19
 1/17/2019

Tassos Dimitriou

Analysis of Algorithms - example

Another algorithm for the same problem:

Procedure max_diff (a1, a2, …, an)

min = max = a1
for i = 2 to n
if ai < min then min = ai
else if ai > max then max = ai
return max – min

What is the number of comparisons made?

Answer: 2n – 2

Time complexity is O(n).

CpE-203: Discrete Structures 39

Tassos Dimitriou

CpE-203: Discrete Structures 40

20