Algorithm Design and Analysis

Prof. Dr. Abeer Mahmoud

Professor of Computer Science -Head of computer science Department-Faculty of

Computer and Information Sciences- Ain Shams University
[email protected] 1
 Plz silent your mobile phone.
Never receive calls during the lecture.
Never ask permission to receive calls during the
lecture.

2
 Overall aims of the course

 This course is an introductory course on Algorithms

Design and Analysis. The main techniques for algorithms
deign are described and analyzed. Techniques for
performance analysis through complexity computation are
explained.

 we will explore a wide variety of problems, some relatively

abstract and some down-to-earth.

3
Prerequisites

Students are expected to know :

1. Good Mathematical background

2. C or C# language,
3. Data structures,

4
 Course Objectives

 Develop your general problem solving skills!

 Learn to perform theoretical analysis of algorithms
 Learn to perform empirical analysis of algorithms
 Become familiar with several families of algorithms
suitable for solving many kinds of problems

5
 References

Text Book: Introduction to

Algorithms , 3rd ed. MIT Press, 2009.
ISBN: 9780262033848.

Text Book: Algorithm Design (Foundations, Analysis,

and Internet Examples M. Goodrich and R. Tamassia John
Wiley & Sons, Inc. (2002)

6
Basis of Grading

quizzes --- 5%
Assignments --- 10%
Midterm Exam --- 15%
Practical Exam- --- 20%
Final Exam --- 50%

7
Class-taking technique

 I will use projected material (Microsoft power point)

 You should read the book
 Not all material will be covered in class
 You are responsible for material from class
→ I will probably hint at good test questions in class

 The course is not a programming course, hence the Project

is graded on functionality, and originality (never present a
copy from someone else effort)
 See me or the TA in office hours if you have questions 8
 Contents
• Introduction
• Asymptotic Complexity
• Recurrence Relations
• Divide and Conquer
• Elementary Graph Theory
• Dynamic Programming and Graph Algorithms
• Greedy Algorithms
• Network Flow
• …..
• …..
• Additional Topics

9
Introduction to Algorithms

LECTURE1

• Introduction
• Quick Mathematical Overview
• Analysis of Algorithms
• Examples

10
Introduction

11
 Why algorithms?

Q: Can I get a good programming job without knowing

something about algorithms and data structures?

A: Yes... but do you really want to be programming GUIs your

entire life?

12
 Algorithms are the heart of computer science, and their
essential nature is to automate some aspect of collecting,
organizing and processing information.

 Today, information of all kinds is increasingly available in

enormous quantities. However, our ability to make sense of
this information, to manage, organize and search it, and to
use it for practical purposes, e.g., self-driving cars,
adaptive computation, search algorithms for the Internet or
for social networks, artificial intelligence, and many
scientific applications, relies on the design of correct
and efficient algorithms,

 algorithms must perform as intended on all inputs and are

fast, use little memory and provide guarantees on their
performance.
Prof. Aaron Clauset, CSCI 5454, CU-
Boulder, Lecture 0
 The business pitch

1. Almost all big companies want programmers with

knowledge of algorithms: Microsoft, Apple, Google,
Facebook, Oracle, IBM, Yahoo, NIST, NOAA, etc.

2. In most programming job interviews, they will ask you

several questions about algorithms and/or data
structures. They may even ask you to write pseudo or
real code on the spot.

Prof. Aaron Clauset, CSCI 5454, CU-

Boulder, Lecture 0
14
 The intellectual pitch

1. You will improve your research skills in almost any area.

2. You will write better, faster, more elegant code.

3. You will think more clearly, more abstractly and more

mathematically.

4. It’s one of the most challenging and interesting area of

Computer Science.

Prof. Aaron Clauset, CSCI 5454, CU-

Boulder, Lecture 0
15
An example

o You are given an array containing integers between 1 and

1,000,000.
o Every integer from 1 and 1,000,000 is in the array once,
but one is in the array twice.

Q: Can you determine which integer is in the array twice?

Q: Can you do it while iterating through the array only once?

Prof. Aaron Clauset, CSCI 5454, CU-

Boulder, Lecture 0
16
 A naive solution

• Here’s a simple and intuitive solution for solving this problem:

1. Create a new array L of ints between 1 and 1,000,000; we’ll use

this array to count the occurrences of each number.

2. Initialize all entries to 0.

3. Iterate over the input array; each time a number i is seen,

increment the count L[i] in the new array

4. Iterate over L and see which number occurs twice, L[i] > 1.

5. Return that number, i. Prof. Aaron Clauset, CSCI 5454, CU-

Boulder, Lecture 0
17
o How long does this algorithm take? This algorithm
iterates through 1,000,000 numbers 3 times.

o It also uses twice as much space as the original input

sequence.

o The good news is that, while inefficient, this algorithm is

correct, meaning that on every possible input, it returns the
correct answer.

18
In fact, this solution is not efficient: it wastes both
time and space. How much better can we do?

19
 A better solution

o Recall from discrete mathematics that

o Let S be the sum of the values in the input array.

o Let n be the largest integer in the array; in this case,

n = 1, 000, 000.

o Let x be the value of the repeated number.

o Then, S = n(n + 1)/2 + x,  x = S − n(n + 1)/2.
20
 Thus, an efficient algorithm is the following:

1. Iterate through the input array, summing the numbers;

let S be this sum; let n be the largest value observed in
this iteration.

2. Let x = S − n(n + 1)/2.

3. Return x.

How much time does this take?

 We iterate through the input array exactly once, so it’s
roughly three times faster than the first algorithm.
 we use only three constants to store our intermediate work,
so this uses much less space.
21
Definitions
 What is a problem?

 What is a solution?

22
 Problems and Their Solutions
Problem:
Input Set Output Set

Problem
Instances

Solution:
Algorithm

Computing
Device
Domain Range
23
 The Solution is the Algorithm
Problem:
Input Set Output Set

Problem
Instances

Solution:
Algorithm

Computing
Device
Domain Range
24
 Designing good algorithms matters.
 As computer scientists, we aim to design correct solutions to
problems (does not fail on any input),
 design elegant solutions to problems
 design efficient solutions (use as few resources as possible),
and
 provide performance guarantees where possible (you have
thought carefully about the worst possible behavior).

25
 Achieving these goals is not always easy.
Many of the algorithms we’ll see in this
course are clever,
 but very few are the most efficient solution
possible.

26
 What is an algorithm?

 a step-by-step procedure to solve a problem

 every program is the instantiation of some algorithm

Definition: An algorithm is a finite set of instructions that,

it followed, accomplishes a particular task.
In addition, all algorithms must satisfy the following
criteria:
Input. Zero or more quantities are externally supplied.
Output. At least one quantity is produced.
27
Properties of an Algorithm

 Required Properties?
 Finite Domain
 Finite Range
 Must Terminate
 Correctness
 Relative to a Computation Device
 Including Elementary Operations

 Also Interested in Efficiency, both space and time

28
Properties of an Algorithm
 Definiteness:Each instruction is clear and unambiguous.

 Finiteness. If we trace out the instructions of an

algorithm, then for all cases, the algorithm terminates
after a finite number of steps.

 Effectiveness. Every instruction must be very basic so

that it can be carried out, in principle, by a person using
only pencil and paper.

29
Correctness

 How do you know an algorithm is correct?

 produces the correct output on every input
 Since there are usually infinitely many inputs, it is
not trivial
How to Prove Correctness?
 There exist formal methods
 even automated tools
 more advanced than this course
 In this course we will primarily rely on more
informal reasoning about correctness
30
Efficiency
 Given a problem:
 what is an efficient algorithm?
 what is the most efficient algorithm?
 does there even exist an algorithm?

31
 How to Measure Efficiency

 Machine-independent way:
 analyze "pseudocode" version of algorithm
 assume idealized machine model
 one instruction takes one time unit
 "Big-Oh" notation
 order of magnitude as problem size increases
 Worst-case analyses
 consider the algorithm’s worst possible behavior, in terms of
resource usage (time & space).
 safe, often occurs most often, average case often just as bad

32
 How to Measure Efficiency

o Alternatively, we may consider the average case, which is

sometimes significantly better than the worst case, but not
always. (Note: the term “average” case is meaningless
without some reference to a probability distribution of
inputs.)

o Best case analysis is inherently optimistic, and thus is not

typically useful for providing algorithmic guarantees.

33
Efficiency
 Efficiency is how cost grows with the difficulty of the
instance
 “Difficulty” means “size” of the instance
 i.e., the number of parameters needed to completely characterize
the instance
 Size of a list, matrix, etc.
 Example: we expect the cost of sorting a list of 100
numbers to be worse than sorting 10 numbers

34
Modeling the Real World
 Cast your application in terms of well-studied abstract data
structures
Concrete Abstract
arrangement, tour, ordering, sequence permutation
cluster, collection, committee, group, packaging, selection subsets
hierarchy, ancestor/descendants, taxonomy trees
network, circuit, web, relationship graph
sites, positions, locations points
shapes, regions, boundaries polygons
text, characters, patterns strings

35
 Real-World Applications

 Hardware design: VLSI  Computer aided design and

chips manufacturing
 Compilers  Security: e-commerce,
 Computer graphics: movies, voting machines
video games  Multimedia: CD player, DVD,
 Routing messages in the MP3, JPG, HDTV
Internet  DNA sequencing, protein
 Searching the Web folding
 Distributed file sharing  and many more!

36
Some Important Problem Types
 Sorting  Combinatorial
 a set of items  find desired permutation,
 Searching combination or subset
 among a set of items  Geometric
 String processing  graphics, imaging,
robotics
 text, bit strings, gene
sequences  Numerical
 Graphs  continuous math: solving
equations, evaluating
 model objects and their functions
relationships
37
Algorithm Design Techniques
 Brute Force &  Dynamic Programming
Exhaustive Search  break problem into overlapping
follow definition / try all subproblems
possibilities  Greedy
 Divide & Conquer  repeatedly do what is best now

 break problem into  Iterative Improvement

distinct subproblems
 repeatedly improve current
 Transformation solution
 convert problem to  Randomization
another one
 use random numbers
38
Plan of the Course

 Cover a variety of fundamental algorithm design and

analysis techniques as applied to a number of basic
problems
 Organize by technique

39
A Quick Mathematical Review

40
A Quick Mathematical Review

- Summations A notation that appears again

and again in the analysis of data structures
and algorithms is the summation, which is
defined as
b

 f (i)  f (a)  f (a  1) 
i a
f (a  2)  ...  f (b)

41
 A Quick Mathematical Review

 Theorem: For any integer n > 0, and any real number, consider
n

a
i 0
i
 1  a  a 2  ...  a n

(remembering that a0 = 1 if a > 0).

1248
0000
1  a n 1
This summation is equal to 1 a =23 =8
(geometric summations)
 Everyone working in computing should know that
1+ 2 + 4 + 8 + … + 2n-1 = 2n – 1,
for this is the largest integer that can be represented00000=??
in binary notation
using n bits.

42
 A Quick Mathematical Review

Another summation that arises in several contexts is

n
n(n  1)

i 1
i 1  2  3  ...  (n  2)  (n 1)  n 
2
.

This summation often arises in the analysis of loops in cases

where the number of operations performed inside the loop
increases by a fixed, constant amount with each iteration.

43
 A Quick Mathematical Review

 Logarithms and Exponents

 Let a, b, and c be positive real numbers. We
have
logb a  c if a b .c

 As in the custom in the computing literature, we

omit writing the base b of logarithm when b=2.
For example, log 1024 = 10.

44
 A Quick Mathematical Review

 Theorem: Let a, b, and c be positive real numbers. We have

1. log b a c  log b a  log b c

2. log b a / c  log b a  log b c
3. log b a c  c log b a
4. (b a ) c  b ac
5. b a b c  b a  c
6. b a / b c  b a  c

45
 A Quick Mathematical Review

 The Floor and Ceiling Functions

 x  = the smallest integer greater than or equal to x.
 x  = the largest integer less than or equal to x.

3.3  = 4, -3.3  = -3, -3.7  = -3.

 3.3  = 3,  -3.3 = -4,  -3.7  = -4.

46
A Quick Mathematical Review

Mathematical Induction:
We using induction to prove that some statement concerning the
positive integer is true, we use the following terminology:
 Induction base is the proof that the statement is true for
n = 1 (or some other initial value).
 Induction hypothesis is the assumption that the
statement is true for an arbitrary n >= 1 (or some other
initial value).
 Induction step is the proof that if the statement is true
for n, it must also be true for n +1

47
 A Quick Mathematical Review

Combinations
The binomial Theorem states that for any nonnegative
integer n and real numbers a and b,
n
n!
( a  b) 
n

k 0 k! (n  k )!
a k bn  k

Because the number of combinations of n objects

taken k at a time is the coefficient of ak bn – k in
this expression, that number is called the binomial
coefficient.

48
Algorithms Performance Analysis

49
 Performance Analysis

Algorithm
 Definition: An algorithm is a finite step-by-step list of
well-defined instructions for solving a particular problem.
 Algorithm complexity is a key task in comparing the
efficiency of algorithms.
 Two factors are considered:
 1- the (running) time Time Complexity
 2- the space (usage) Space Complexity

50
 Performance Analysis

 Time Complexity estimates the running time of the

algorithm.
 Measured by the number of key step of the basic steps
used by the algorithm.
 Basic Steps are:
 Arithmetic operations
 Comparison operations
 Reading from a memory, file
 Writing to memory, file,

51
 Performance Analysis

Key step
 The most costly step of the algorithm
 Takes most of the running time

 Other steps is much less or at most

proportional to the time of the key step.

Basic Steps Key Step

Multiplication & Division Multiplication

Arithmetic Operations & Comparison

Comparison Operations
Addition of two integers Single-digit addition
52
 Performance Analysis

Worse-Case & Average-Case Analysis

 In worse-case analysis:
 We find the maximum value of the number of the
key steps.
 In Average-case analysis:
 We find the average value of the number of the key
steps.

53
 Performance Analysis

Analyzing An Algorithm
 Three steps in algorithm analysis
 1- Describe the algorithm precisely
 2- Define the input size n.
 3- Count the number of key steps in
function of the input size n, I,e., f (n).

54
 Performance Analysis

Example#1
 Algorithm:
 // Search for value in the list of n items x[0], x[1], …, x[n-1]
for (int i=0; i<n; i++)
if (value = = x[i] ) // key step
return true;
else
return false

Input Size n
Key Step Comparison
Worse-case n
Average case n/2 55
 Performance Analysis

Example#2
 Algorithm
 // Finding a minimum of the list of n items x[0], x[1], …, x[n-1]
 int min = x[0];

 for (int i=1; i<n; i++)

 if (min > x[i]) // key step

 min = x[i];

Input Size n
Key Step Comparison
Worse-case n -1
Average-case n -1

56
 Performance Analysis

Example#3
 Algorithm
 // Summation of n integers
 int sum = 0;

 for (int i=0; i<y; i++)

 sum = sum + x;

 return sum

Input Size n
Key Step Addition
Worse-case n
Average-case n

57
 Test Yourself

Differentiate between algorithm efficiency and

algorithm correctness

58
Thank you
59