Analysis of

Algorithms
KHALILAH BURRELL-BATTICK (MRS.)| CIT3003
Contact Information

Email: Office phone:

kburrell@[Link].j 927-1680-8 (ext.
m 3651)

Office hours: Moodle pwd:

Wednesdays 3 – 5 pm AOA-60/40
Course Introduction

 Analysis of algorithms is an important  Lectures: Mon at 10:00 am

part of a broader computational  Tutorials: Weds @ 2pm & Thurs @
complexity theory, which provides 10am
theoretical estimates for the resources  Prerequisites: Data Structures
needed by any algorithm which solves
 Co-requisites: Discrete Mathematics
a given computational problem. These
estimates provide an insight into  Credits: Three (3)
reasonable directions of search for
efficient algorithms. This module seeks
to give an undergraduate an
appreciation for algorithms
Assessment Criteria
Percent of Grade

 001: Group Project

 002: Online Discussions 20
 003: Individual Assignment
 004: Test 1 40
5
 005: Test 2
 205: Final Exam
10

10
15

Project Discussions Assignment

Test 1 Test 2 Final exam
Textbook

Required Recommended Recommended

Week 1: Objectives

 Students should be able to:

 define algorithm
 recall how to use mathematical tools associated with analysis
 provide steps to design and implement algorithm
 classify algorithms based on problem types
 differentiate among the fundamental data structures
 utilize loop invariants in proving algorithm’s correctness
 What is an Algorithm?

A sequence ofunambiguousinstructions
for solving a problem, i.e. for obtaining the
required outputfor anylegitimate input
in a finiteamount of time.
Levitin, p. 3
The notion of the algorithm

PROBLEM

ALGORITHM

INPUT COMPUTER OUTPUT

Mathematical Analysis Tool
A RECOLLECTION
Summations

 When an algorithm contains an iterative control

construct such as a while or for loop, we can express
its running time as the sum of the times spent on each
execution of the body of the loop.

 When we evaluated this summation, we attained a

bound of on the worst-case running time of the
algorithm.
Summations

 Arithmetic series  Sumof squares and

cubes
Summations – Geometric series

For real Infinite and

Bounding Summations

 Sometimes summations cannot be

reduced exactly to a familiar compact
formula, in such cases we may use
approximations by way of bounding

 The most basic way to evaluate a series

is to use mathematical induction.
Arithmetic Series Proof by
Induction
 Base case n=1:

 Inductive Step:
 We make inductive assumption that it holds for some arbitrary value
m

 Then we prove that it holds for m+1

Arithmetic Series Proof by
Induction

 Make m+1 the subject

 Let n = m+1
Matrices

 A matrix is a rectangular array of numbers

 is a matrix , with row and column

 The transpose of a matrix A is the matrix obtained by

exchanging the rows and columns

 A vector is a one-dimensional array of numbers e.g.

Logarithms

 Thelogarithm function is a mathematical tool

that represents a power or an index.
 Let b, a positive real number not equal to 1.
 Ifx is a positive real number, the logarithm to the
base b of x is the exponent to which b must be
raised to obtain x.
 We denote the logarithm to base b of x as .
 Thus if we let y = , the definition states that = x.
Law of Logarithms

 =1 is =0  = -
 =y
 =a =a
note: is equal to one  If a > 0 and a ≠ 1,
we have =

 If x > y > 0, then >

 =
 =x  =
 = +  =
Algorithmic Problem Solving
(ALGORITHM DESIGN AND ANALYSIS PROCESS)
Understand the problem

Decide on:
computational means,
exact vs. approximate solving,
algorithm design technique

Design an algorithm

Prove the Correctness

Analyse the algorithm

Code Algorithm
Problem Types

 There are a few areas that have attracted particular attention

from researchers.
 Interest has been driven either by
 the problem’s practical importance
 specific characteristics
 These two motivating forces reinforce each other in most cases.

 The most important problem types are:

 Sorting, Searching, String processing, Graph problems, Combinatorial
problems, Geometric problems, and Numerical problems.
Fundamental Data Structures

Majority of algorithms we will be

examining operate on data and has
a particular way of organizing data.
These data items can range from
elementary data types (e.g.,
integers or characters) to data
structures.
Linear Data Structures

 Array
 Linked List
 Stack
 Queue

Operations: search, delete, insert

Implementation: static, dynamic
Non-linear Data Structures

 Graphs
 Representation: adjacency lists &
matrix

 Trees: a connected acyclic graph

Rooted trees: placing root at level 0
Ordered tree (e.g. binary tree)
Representation: graphs; binary
Sets, Bags, Dictionaries

 Set: unordered collection of distinct elements

 Operations: membership, union, intersection
 Representation: bit string; linear structure

 Bag: unordered collection, elements may repeated

 Dictionary: a bag with operations search, add, delete

Prove Correctness
LOOP INVARIANT
Prove Correctness of Algorithm

 An algorithm is correct if for any correct input data the algorithm

stops and produces the correct output.
 Correct input data: satisfies precondition
 Correct output data: satisfies postcondition

 Above is easy to prove for simple sequential algorithms

 This can be complicated to prove for repetitive algorithms
 Have to use techniques based on loop invariants and induction
  Solution:
Sum_Arith
Example: Input: N, integer
Repetitive Algorithm Output: S, sum of numbers in range 1-
N
Can you provide a
repetitive algorithm
S=0;
that calculates the
K=1;
sum of the
While (K ≤ N) do
arithmetic series
S=S+K;
with an integer N as
K=K+1;
an input.
done
Using Loop Invariants in Proofs

 A loop invariant is a logical predicate such that: if it is satisfied

before entering any single iteration of the loop then it is also
satisfied after the iteration

 We must show the following 3 things about a loop invariant:

1. Initialization: It is true prior to the first iteration of the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains
true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a
useful property that helps show that the algorithm is correct.
Loop Invariants: Initialization

 Loop Invariant:
Sum_Arith

 Input: N, integer
Initialization: The
hypothesis is true at Output: S, sum of numbers in range
1-N
beginning of the loop

S=0;
 Prior to iteration: S=0
K=1;
 First 0 numbers have a sum 0
While (K ≤ N) do
(There are no numbers)
S=S+K;
K=K+1;

done
Loop Invariants: Maintenance

 Loop Invariant:
Sum_Arith

 Input: N, integer
Maintenance: If hypothesis
is true before iteration then it Output: S, sum of numbers in range
1-N
will be true before step k+1

S=0;
 Prove that after that
executing first loop S hold K=1;
sum of series: S=S+K → While (K ≤ N) do
S=0+1 → S=1 S=S+K;
 K+1 iteration: S=S+K → K=K+1;
S=1+2 → S=3 [proven true]
done
Loop Invariants: Termination

 Loop Invariant:
Sum_Arith

 Input: N, integer
Termination: When iteration
ends the hypothesis implies Output: S, sum of numbers in range
1-N
algorithm’s correctness

S=0;
 If N=5 then
S=1+2+3+4+5=15 K=1;

 Initially S=0 → S=1 → S=3 → While (K ≤ N) do

S=6 → S=10 → S=15 S=S+K;
[postcondition holds] K=K+1;

done
Loop Invariant and Induction

 Proving
loop invariants is similar to
mathematical induction:

 showing that the invariant holds before the first

iteration corresponds to the base case
 showing that the invariant holds from iteration to
iteration corresponds to the inductive step
Related Assessment

Ind.
Research
Assignmen Tests
Project
t
Algorithm Part of Test 1
Question 1
Research only

Except Time
Final exam
& Space Question 2
part of Q1
Analysis
Readings

Chapter 1 Chap 10 & App VIII Chapter 1

The Design & Introduction to Computer
Analysis of Algorithms by Algorithms –
Algorithms by Cormen, Leiserson, Introduction to
Anany Levitin Rivest & Stein Design And
Analysis by Sara
Baase & Allen Van
Gelder
Questions?