Algorithms and Problem
Solving
Lecture 01 – Introduction to
Algorithms
AL-Zaiem AL-Azhari University
Faculty of Computer Sciences and Information
Technology
Mohammed Mahmoud
Overview
• Computer Algorithm: ‘’ a set of steps to
accomplish or complete a task that is described
precisely enough that a computer can run it’’.
• Described precisely: very difficult for a machine
to know how much water, milk to be added etc. in
the above tea making algorithm. These algorithms
run on computers or computational devices.
• For example, GPS in our smartphones, Google
hangouts. GPS uses shortest path algorithm.
• Online shopping uses cryptography which uses RSA
algorithm.
What is algorithms ?
• Algorithm is a set of steps to complete a
task. For example, Task: to make a cup of
tea.
• Algorithm:
• add water and milk to the kettle,
• Boil it, add tea leaves,
• Add sugar, and then serve it in cup.
• An algorithm is a sequence of unambiguous
instructions for solving a problem, i.e., for
obtaining a required output for any
legitimate input in a finite amount of time.
What is algorithms ?
problem
algorithm
input “computer” output
History
• The word algorithm comes from the name of a Persian
mathematician Abu Ja’far Mohammed ibn-i Musa al
Khowarizmi - 9th century mathematician.
• Euclid’s algorithm for finding the greatest common divisor
• www.lib.virginia.edu/science/parshall/khwariz.html
• In computer science, this word refers to a special method
useable by a computer for solution of a problem.
• For example, sorting a given sequence of numbers into
nondecreasing order provides fertile ground for
introducing many standard design techniques and
analysis tools.
Algorithms’ Characteristics
• Algorithm is recipe, process, method,
technique, procedure, routine, with the
following characteristics:
• Clearly Specified Input - Must take an input.
• Clearly specified/expected Output - Must
give some output (yes/no, value etc.)
• Definiteness (Unambiguity/clearness) - each
instruction is clear and unambiguous.
• Finiteness –algorithm terminates after a
finite number of steps.
• Effectiveness - every instruction must be
basic i.e. simple instruction.
Some Well-known
Computational Problems
• Common Computational Problems
• Sorting
• Searching
• Shortest paths in a graph
• Minimum spanning tree
• Primality testing
• Traveling salesman problem
• Knapsack problem
• Chess
• Towers of Hanoi
• Program termination
• Some of these problems don’t have efficient
algorithms, or algorithms at all!
Fundamental data
structures
• List
• array
• linked list
• string
• stack
• queue, priority queue/heap
• graph
• tree and binary tree
• set and dictionary
Example of computational
problem: sorting
• Statement of problem:
• Input: A sequence of n numbers <a1, a2, …, an>
• Output: A reordering of the input sequence <a´1, a´2, …, a
n> so that a i ≤ a j whenever i < j
´ ´ ´
• Instance: The sequence <5, 3, 2, 8, 3>
• Algorithms:
• Selection sort
• Insertion sort
• Merge sort
• (many others)
Selection Sort
• Input: array a[1],…,a[n]
• Output: array a sorted in non-decreasing order
• Algorithm:
for i=1 to n
swap a[i] with smallest of a[i],…,a[n]
Basic Issues Related to
Algorithms
• How to design algorithms
• How to express algorithms
• Proving correctness
• Efficiency (or complexity) analysis
• Theoretical analysis
• Empirical analysis
• Optimality
Algorithm design
strategies
• Brute force • Greedy approach
• Divide and conquer • Dynamic
programming
• Decrease and
conquer • Backtracking and
branch-and-bound
• Transform and
conquer • Space and time
tradeoffs
Good Algorithm
• How good is the algorithm?
• Correctness
• Time efficiency
• Space efficiency
• Does there exist a better algorithm?
• Lower bounds
• Optimality
Euclid’s Algorithm
• Problem: Find gcd(m,n), the greatest common
divisor of two nonnegative, not both zero integers
m and n
• Examples:
• gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?
• Euclid’s algorithm is based on repeated application
of equality
• gcd(m,n) = gcd(n, m mod n)
• until the second number becomes 0, which makes
the problem trivial.
• Example:
• gcd(60,24) = gcd(24,12) = gcd(12,0) = 12
Two descriptions of Euclid’s
algorithm
Two Method to express algorithm
• Algorithm Description
• 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
• Step 3 Assign the value of n to m and the value of r to n.
Go to Step 1.
• Pseudo code:
while n ≠ 0 do
r ← m mod n
m← n
n ← r
return m
Other methods for
computing gcd(m,n)
• Consecutive integer checking algorithm
• Step 1 Assign the value of min{m,n} to t
• Step 2 Divide m by t. If the remainder is 0,
go to Step 3; otherwise, go to Step 4
• Step 3 Divide n by t. If the remainder is 0,
return t and stop; otherwise, go to Step 4
• Step 4 Decrease t by 1 and go to Step 2
• Is this slower than Euclid’s algorithm?
How much slower?
Other methods for
computing gcd(m,n)
• Middle-school procedure
• Step 1 Find the prime factorization of m
• Step 2 Find the prime factorization of n
• Step 3 Find all the common prime factors
• Step 4 Compute the product of all the
common prime factors and return it as
gcd(m,n)
• Is this an algorithm? How efficient is it?
Sieve of Eratosthenes
Input: Integer n ≥ 2
Output: List of primes less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to n do
if A[p] ≠ 0
//p hasn’t been previously eliminated from
the list
j ← p* p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
Example: j←j+p
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
END!
