CS313 Algorithms
Agenda
• Course Objectives
• Concepts of Algorithms
o Algorithm Definition
o Characteristics of Algorithms
o Algorithm Efficiency
o Analysis and Complexity of Algorithms
2
Course Objectives
• By the end of the course, the successful student will
be able to:
o Understand, explain, model, and analyze a given software
problem as an algorithm.
o Investigate whether the algorithm found is the most
efficient.
o Formulate the time order analysis for an algorithm.
o Formulate the space needs for the implementation of an
algorithm.
o Prove the correctness of an algorithm.
3
Textbook
4
Concepts of Algorithms
• The word “Algorithm” derives from the name of the
mathematician, Mohammed ibn Musa al
Khwarizmi, who was part of the royal court in
Baghdad and who lived from about 780 to 850.
5
Concepts of Algorithms
• What is an algorithm?
o A sequence of instructions describing how to solve problem
o Algorithms must be :
• Correct: For each input produce an appropriate output
• Efficient: run as quickly as possible, and use as little memory as
possible
6
Concepts of Algorithms
• What is an algorithm?
o A program is one type of algorithm
• All programs are algorithms
• Not all algorithms are programs!
o Directions to somebody’s house is an algorithm
o A recipe for cooking a cake is an algorithm
o The steps to compute the cosine of 90° is an algorithm
7
Concepts of Algorithms
• Some algorithms are easy
o Finding the largest (or smallest) value in a list
o Finding a specific value in a list
• Some algorithms are a bit harder
o Sorting a list
• Some algorithms are very hard
o Finding the shortest path between Miami and Seattle
• Some algorithms are essentially impossible
8
Algorithm 1:
Maximum element
• Given a list, how do we find the maximum element
in the list?
• To express the algorithm, we’ll use pseudo-code
o Pseudo-code is an informal high-level description of the operating
principle of a computer program or other algorithm.
o It uses the structural conventions of a programming language but is
intended for human reading rather than machine reading.
9
Algorithm 1:
Maximum element
• Algorithm for finding the maximum element in a list:
procedure max (a1, a2, …, an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
{max is the largest element}
10
Algorithm 1:
Maximum element
procedure max (a1, a2, …, an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
max 9
7
4
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
4 1 7 0 5 2 9 3 6 8
i 10
9
8
7
6
5
4
3
2
11
Algorithm 1:
Maximum element
• How long does this take?
• If the list has n elements, it takes n “steps”
12
Algorithm 2: Linear search
• Given a list, find a specific element in the list
o List does NOT have to be sorted!
procedure linear_search (list, x_value)
for ( int i = 1 ; i <= n ; i++ )
if x_value == list (i)
location = i and Enf if
Else location = 0 and Enf if
End for and End procedure
{location is the subscript of the term that equals x,
or it is 0 if x is not found}
13
Algorithm 2: Linear search
procedure linear_search (a_list, x_value)
for ( int i = 1 ; i <= n ; i++ )
if x_value == a_list (i)
location = i and Enf if x 3
Else location = 0 and Enf if
location 8
End for and End procedure
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
4 1 7 0 5 2 9 3 6 8
i 1
8
7
6
5
4
3
2
14
Algorithm 2: Linear search
procedure linear_search (a_list, x_value)
for ( int i = 1 ; i <= n ; i++ )
if x_value == a_list (i)
location = i and Enf if x 11
Else location = 0 and Enf if
location 0
End for and End procedure
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
4 1 7 0 5 2 9 3 6 8
i 90
8
7
6
5
4
3
2
1
11
15
Algorithm 2: Linear search
• How long does this take?
• If the list has n elements, worst case scenario is that
it takes n “steps”
16
Algorithm 3: Binary search
• Given a list, find a specific element in the list
o List MUST be sorted!
• Each time it iterates through, it cuts the list in half
procedure binary_search (x: integer; a1, a2, …, an: increasing integers)
i := 1 { i is left endpoint of search interval }
j := n { j is right endpoint of search interval }
while i < j
begin
m := (i+j)/2 { m is the point in the middle }
if x > am then i := m+1
else j := m
end
if x = ai then location := i
else location := 0
{location is the subscript of the term that equals x, or it is 0 if x is not
found}
17
Algorithm 3: Binary search
procedure binary_search (x: integer; a1, a2, …, an: increasing integers)
i := 1 while i < j if x = ai then location := i
j := n begin else location := 0
m := (i+j)/2
if x > am then i := m+1 x 14
else j := m
end location 7
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
2 4 6 8 10 12 14 16 18 20
i 761 m 5
8
7
6 j 10
8
7
18
Algorithm 3: Binary search
procedure binary_search (x: integer; a1, a2, …, an: increasing integers)
i := 1 while i < j if x = ai then location := Ii
j := n begin else location := 0
m := (i+j)/2
if x > am then i := m+1 x 15
else j := m
end location 0
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
2 4 6 8 10 12 14 16 18 20
i 861 m 5
8
7 j 10
8
19
Algorithm 3: Binary search
• How long does this take (worst case)?
• If the list has 8 elements
o It takes 3 steps
• If the list has 16 elements
o It takes 4 steps
• If the list has 64 elements
o It takes 6 steps
• If the list has n elements
o It takes log2 n steps
20
Characteristics of Algorithms
• Algorithms are well-ordered
• Algorithms have unambiguous operations
• Algorithms have effectively computable operations
• Algorithms produce a result
• Algorithms Stop in a finite amount of time
21
Algorithm Efficiency
• Algorithm has both time and space requirements called
complexity to measure
• Types of complexity
o Space complexity
o Time complexity
22
Algorithm Efficiency
Three algorithms for computing
1 + 2 + … n for an integer n > 0
23
Algorithm Efficiency
The number of operations required by the algorithms
24
Algorithm Efficiency
O(n) algorithm.
25
Algorithm Efficiency
An O(n2) algorithm. 26
Algorithm Efficiency
The number of operations required by the algorithms as a
function of n
27
Algorithm Efficiency
• Measure the time complexity since it is more important.
• Cannot compute actual time for an algorithm.
• Give function of problem size that is directly proportional to
time requirement: growth-rate function.
• Function measures how the time requirement grows as the
problem size grows.
o We usually measure worst-case time
28
Analysis and Complexity of
algorithms
• Call each simple instruction and access to a word of
memory a “primitive operation” or “step.”
• Running time of an algorithm for a given input is
o The number of steps executed by the algorithm on that input.
• Often referred to as the complexity of the algorithm.
29
Analysis and Complexity of
algorithms
• Run time expression should be machine-independent.
o Use a model of computation or “hypothetical” computer.
o Our choice – RAM model (most commonly-used).
• Model should be
o Simple.
o Applicable.
30
Analysis and Complexity of
algorithms
RAM Model:
• Generic single-processor model.
• Supports simple constant-time instructions found in real
computers.
o Arithmetic (+, –, *, /, %, floor, ceiling).
o Data Movement (load, store, copy).
o Control (branch, subroutine call).
• Run time (cost) is uniform (1 time unit) for all simple instructions.
• Memory is unlimited.
• Flat memory model – no hierarchy.
• Access to a word of memory takes 1 time unit.
• Sequential execution – no concurrent operations.
31
Analysis and Complexity of
algorithms
• Complexity of an algorithm generally depends on
o Size of input.
• Input size depends on the problem.
o Examples: No. of items to be sorted.
o No. of vertices and edges in a graph.
o Other characteristics of the input data.
• Are the items already sorted?
• Are there cycles in the graph?
32
Analysis and Complexity of
algorithms
• Worst-case Complexity
o Maximum steps the algorithm takes for any possible input.
o Most tractable measure.
• Average-case Complexity
o Average of the running times of all possible inputs.
o Demands a definition of probability of each input, which is usually difficult to
provide and to analyze.
• Best-case Complexity
o Minimum number of steps for any possible input.
o Not a useful measure. Why?
33
Analysis and Complexity of
algorithms
Big Oh Notation:
• Computer scientists use a notation to represent
an algorithm’s complexity.
• To say "Algorithm A has a worst-case time
requirement proportional to n"
o We say A is O(n)
o Read "Big Oh of n" or “order of at most n”
• For the other two algorithms
o Algorithm B is O(n2)
o Algorithm C is O(1)
34
Analysis and Complexity of
algorithms
Some Common Names for Complexity:
35
Analysis and Complexity of
algorithms
Grows in magnitude from left to right…
Tabulates magnitudes of typical growth-rate functions
evaluated at increasing values of n
When analyzing the time efficiency of an algorithm, consider larger
problems. For small problems, the difference between the execution
time is usually insignificant.
36
Analysis and Complexity of
algorithms
Practical vs. Impractical Complexities:
37
Analysis and Complexity of
algorithms
Growth of Functions:
38
Questions & Answers
