Design and Analysis

Algorithms
Dr. Metwally Rashad Lecture 1
2022
 Weighting of Assessment
Mid-Term Examination 20 %

Oral Examination (Q1- Q2) 10 %

Lab 20 %

Final-term Examination 50 %
------------------------------------
Total 100 %

1/24
 Course Material

Book
T. H. Cormen, C. E. Leiserson, R. L.Rivest,
C. Stein. Introduction to Algorithms , 3rd
Edition, 2009.

Slides
- Should be available after the class
1/26
Table of Contents
1. Foundations
- The Role of Algorithms in Computing
- Design and Analysis algorithms
- Growth of Functions
2. Sorting
- Heapsort
- Quicksort
- Sorting in Linear Time
3. Graph Algorithms
- Elementary Graph Algorithms
- Minimum Spanning Trees
4. Advanced Design and Analysis Techniques
- Dynamic Programming
- Greedy Algorithms
5. Selected Topics
- Linear Programming
- String Matching
3/24
 Mathematical background needed to understand
algorithms
A. Summations C. Counting and Probability
- Summation formulas and properties - Counting
- Bounding summations - Probability
B. Sets, Etc. - Discrete random variables
- Sets - The geometric and binomial distributions
- Relations D. Matrices
- Functions - Matrices and matrix operations
- Graphs - Basic matrix properties
- Trees

4/24
Ch1: Foundations 5/24
 Algorithms
 An algorithm is a set of computational steps for solving a well-specified
computational problem.
 Properties of an algorithm
 Input: an algorithm has input values from a specified set
 Output: from each set of input values an algorithm produces output values from a specified set.
The output values are the solution to the problem
 Definiteness: the steps of an algorithm must be defined precisely
 Correctness: an algorithm should produce the correct output values for each set of input values
 Finiteness: an algorithm should produce the desired output after a finite number of steps for
input in the set
 Effectiveness: it must be possible to perform each step of an algorithm exactly and in a finite
amount of time
 Generality: the algorithm should be applicable for all problems of the desired form not just for a
particular set of input values 6/24
 What kinds of problems are solved by algorithms?
• Basic numerical algorithms
- arithmetic problems like finding the sum, product or quotient of two numbers
• Cryptographic algorithms
- digitally sign and encrypt your data when it’s sent over the internet

• Sorting and searching algorithms

- allow programmers to arrange data in memory in many different ways so that
specific pieces of data can later be retrieved efficiently when they are needed
• Signal processing algorithms
- compress audio and video data very efficiently and allow us to store a whole 3-
hour UHD movie on a single plastic disc, or stream it live over the internet
7/24
 What kinds of problems are solved by algorithms?
• Graph algorithms
- find an efficient path through some kind of network — be it a computer network, a
road network

• Computational geometry algorithms

- important in games and are also heavily used in CAD software

• Computer vision algorithms

- allow software to recognize features in images
• Computer graphics algorithms
- Video games and movies are the most spectacular uses
8/24
Algorithms Task

9/24
 Algorithms Task (cont.)
 Analysis: predict the cost of an algorithm in terms of resources
and performance

 Design: creating an efficient algorithm to solve a problem in an

efficient way using minimum time and space. 10/24
 Time Complexity & Space Complexity
• Time Complexity is a function describing the a mount of
time required to run an algorithm in terms of the size of the
input.

• Space Complexity is a function describing the a mount of

memory an algorithm takes in terms of the size of the input.

11/24
Comparing between two Algorithms
Algorithm A o Model of computation :
Hardware, Operating
Exec_Time = 10msec System, Processor, etc
RAM = 100KB

Algorithm B
o If I change the model of
computation, the time
Exec_Time = 2msec
and space may change
RAM = 10KB
12/24
 Sorting Problem
 Sort a sequence of numbers into non-decreasing order

Example:
Input: 8 2 4 9 3 6
Output:
2 3 4 6 8 9
- Input sequence is called an instance of the sorting problem. 13/24
 Sorting Problem (cont.)
 Efficiency
o Different algorithms devised to solve the same problem often differ
dramatically in their efficiency.
o These differences can be much more significant than differences due
to hardware and software
o In this chapter, we will see two algorithms for sorting problem
o The first, known as insertion sort, takes time roughly equal to 𝒄𝟏 𝒏𝟐 to sort 𝑛 items,
where 𝒄𝟏 is a constant that does not depend on 𝒏.
o The second, merge sort, takes time roughly equal to 𝒄𝟐 𝒏𝒍𝒐𝒈𝟐 n, where 𝒄𝟐 is
another constant that also does not depend on 𝒏.
14/24
 Insertion Sort
• Solves the sorting problem
• An efficient algorithm for sorting a small
number of elements
• Works the way many people sort a hand of playing
cards
• Start with an empty left hand and the cards face
down on the table
• Then remove one card at a time from the table and
insert it into the correct position in the left hand
• To find the correct position for a card, we compare
it with each of the cards already in the hand, from right to left
15/24
Insertion Sort (cont.)
keys: The numbers
that we wish to
sort

16/24
Example of Insertion Sort

17/24
 Analysis of Algorithms
 Analysis of Algorithms is the determination of the amount of time,
storage and/or other resources necessary to execute them.
 Analyzing algorithms is called Asymptotic Analysis
 We shall assume a generic one processor, random-access machine (RAM)
model of computation as our implementation technology and understand that
our algorithms will be implemented as computer programs.
 In the RAM model, instructions are executed one after another
 The running time depends on the input: an already sorted sequence is easier
to sort and short sequences are easier to sort than long ones.
18/24
 Analysis of Algorithms (cont.)
• We can have three cases to analyze an algorithm
1. Worst-case
• The case that causes maximum number of operations to be executed
• 𝑇(𝑛) = upper bound on running time of an algorithm on any input of
size 𝑛.
Example: Search for number 8

2 3 5 4 1 7 6
19/24
 Analysis of Algorithms (cont.)
2. Average-case: (sometimes)
• We take all possible inputs and calculate computing time for all of the inputs
• 𝑇(𝑛) =expected time of algorithm over all inputs of size 𝑛

3. Best-case
• Calculate lower bound on running time of an algorithm.
• The case that causes minimum number of operations to be executed.
Example: Search for number 2

2 3 5 4 1 7 6
20/24
Analysis of Insertion Sort
o We presenting the INSERTION-SORT
procedure with the time “cost” of each
statement and the number of times each
statement is executed.

o Let 𝒕𝒋 denote the number of times the

while loop test in line 5 is executed for
that value of 𝒋.

o Comments are not executable

statements, and so they take no time.

21/24
Analysis of Insertion Sort (cont.)

time number of times 22/24

 Analysis of Insertion Sort (cont.)
 Running time of insertion sort

 In insertion sort, the best case occurs if the array is already sorted.

23/24
 Analysis of Insertion Sort (cont.)

 Best Case
 If 𝐴 is sorted: 𝑂(𝑛) comparisons

 Worst Case
 If 𝐴 is reversed sorted: 𝑂(𝑛2 ) comparisons

 Average Case
 If A is randomly sorted: 𝑂(𝑛2 ) comparisons
24/24