ALGORITHMS

INTRODUCTION

A. G. M. Zaman
Assistant Professor, Department of Computer Science, AIUB
[email protected]
 Vision & Mission of AIUB
VISION
AMERICAN INTERNATIONAL UNIVERSITY-BANGLADESH (AIUB) envisions
promoting professionals and excellent leadership catering to the technological progress
and development needs of the country.

MISSION
AMERICAN INTERNATIONAL UNIVERSITY-BANGLADESH (AIUB) is committed to
provide quality and excellent computer-based academic programs responsive to the
emerging challenges of the time. It is dedicated to nurture and produce competent
world class professional imbued with strong sense of ethical values ready to face the
competitive world of arts, business, science, social science and technology.
 Goals of AIUB
• Sustain development and progress of the university
• Continue to upgrade educational services and facilities responsive of the
demands for change and needs of the society
• Inculcate professional culture among management, faculty and personnel in the
attainment of the institution's vision, mission and goals
• Enhance research consciousness in discovering new dimensions for curriculum
development and enrichment
• Implement meaningful and relevant community outreach programs reflective of
the available resources and expertise of the university
• Establish strong networking of programs, sharing of resources and expertise
with local and international educational institutions and organizations
• Accelerate the participation of alumni, students and professionals in the
implementation of educational programs and development of projects designed
to expand and improve global academic standards
 Vision & Mission of Computer Science
Department
VISION
Provides leadership in the pursuit of quality and excellent computer education
and produce highly skilled and globally competitive IT professionals.

MISSION
Committed to educate students to think analytically and communicate
effectively; train them to acquire technological, industry and research-oriented
accepted skills; keep them abreast of the new trends and progress in the world
of information communication technology; and inculcate in them the value of
professional ethics.
 Goals of Computer Science Department
• Enrich the computer education curriculum to suit the needs of the
industry- wide standards for both domestic and international markets
• Equip the faculty and staff with professional, modern technological and
research skills
• Upgrade continuously computer hardware's, facilities and instructional
materials to cope with the challenges of the information technology age
• Initiate and conduct relevant research, software development and
outreach services.
• Establish linkage with industry and other IT-based
organizations/institutions for sharing of resources and expertise, and
better job opportunities for students
 Course Objectives
• The objective of this course is
 How we can compare algorithms
 Complexity analysis of algorithms
 How effective data structures could be used to solve different problems
 And implementation of different algorithms with the practical examples

• The purpose of the course is

 To raise your level of sophistication in thinking about the design and analysis of
algorithms
 Learn some of the classic algorithms and recent improvements
 Exercise your creativity in designing algorithms.
 Course Prerequisites
• Programming
 Data types, operations
 Conditional statements
 Loops
 Procedures and functions
 C/ C++/ Java
• Discrete Mathematics (proof theorems)
• Data Structures (array, structure, pointer, linked list, file, etc...)

If you lack of any of the above please refine yourselves.

 Importance of the course
• This course is a continuation of the courses Programming
Language 1 & 2, and Data Structure.
• Algorithm is required for all areas of computer science –
especially for developing problem solving ability.
• This course will give the basic for the understanding of the
courses – Artificial Intelligence, Theory of Computation, etc.
• This course will give the basic for the understanding of the
concepts – Design and Analysis of Algorithm.
 Course Contents
• Introduction to Algorithms
• Analysis of Algorithms
• RAM model, Basic notation
• Recurrences & Master Method
• Dynamic Programming
• Greedy strategy
• Graphs Algorithms
• Greedy Graph Algorithm
• Shortest Path Algorithms
• Basic idea of NP – Completeness
• Basic idea of Elementary Geometric Methods & Review
 Resources & References
• Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charle E.
Leiserson, Ronald L. Rivest, Clifford Stein (CLRS).

• Fundamental of Computer Algorithms, Ellis Horowitz, Sartaj Sahni,

Sanguthevar Rajasekaran (HSR)

• Helpful link for Problem Solving : http://acm.uva.es/problemset/

• Lectures and Laboratory works will be provided online at the course website
weekly.
 Course Evaluation
Midterm Quiz (Best Two) 20%
Laboratory Performance/Assignment/Exam 20%
Class Attendance/Performance 10%
Midterm Written Exam 50%
Midterm Total 100% 40%
Final term Quiz (Best Two) 20%
Laboratory Performance/Assignment/Exam 20%
Class Attendance/Performance 10%
Final term Written Exam 50%
Final Term Total 100% 60%
Grand Total Grand Final of the Course 100
 Classroom Policies
• Must be present inside the class in due time.
• Class Break: I would prefer to start the class in due time and leave the class in 10/15 minutes
early for theory/Laboratory class respectively, instead of giving a break.
• Every class will start with a question-answer session about the last lecture. So students must be
prepared with the contents and exercises from the last lecture.
• Students are suggested to ask questions during or after the lecture.
• Additional/bonus marks may be given to any good performances during the class/lab.
• Late in Class:
 Student coming after 10 minutes of due time is considered late.
 3 late attendances are considered as one absent.
 Late during quiz/presentation are not given additional time.
 Students who are regularly late might have additional deduction of marks.
 A late student will be allowed to enter the class. Don’t ask permission to enter the class, just get in
slowly and silently. Same policy implies if a student wants to go out of the class for emergency reasons.
 Course Policies
• Attendance
• Laboratory Policies
• Makeup Evaluation (quiz, assignment, etc.)
• Grading Policies
• Dropping a Course
 Attendance
• At least 75% presence is required by the student. Absent classes
must be defended by the student through application and proper
documentation to the course teacher.
• Single absences or absences within 25% range will be judged by the
course teacher.
• Long absences/irregular presence/absences out of 25% range must
go through application procedures via department Head (+ probation
office, if student is in probation) to attend the following classes.
• Acceptance of an application for absence only gives permission to
attend the following classes. This might still result in deduction of
marks (for attendance) which will be judged by the course teacher.
 Laboratory Policies
 LABORATORY CLASSES:
♦ First 0.5 – 1 hour will be spent explaining the problems/task/experiment to be performed.
♦ Next 1 – 1.5 hour(s) will be spent by the students to complete the experiment.
♦ Next 0.5 – 1 hour will be spent in checking, marking, and discussing the solution.
♦ Students are allowed to discuss with each other (unless instructed not to) in solving problems.
♦ But the checking (executing/viva) & marking will be with individual students only.
 LABORATORY EXAM:
♦ Laboratory exam is scheduled in the week before the major exams, during normal laboratory hours.
♦ Generally students are given one/more problems to be solved of which at least one part is solved
using computers.
♦ One hour is given to the students to solve the problem. And half hour to submit and viva. Generally 20
students in the first 1.5 hours and the other 20 students in the rest 1.5 hours.
♦ Students may be given choices to select the problem. At most 3 selection can be given to a student
with 0, 2, and 4 marks deduction as a penalty for each selection respectively.
♦ Only in case of unavoidable circumstances, the laboratory exams may be taken in the off days or
week after the major exams.
 Makeup Evaluation
• There will be no makeup quiz as long as a student have appeared in 2 quizzes.
• Makeup for missing evaluations like quizzes/assignment submission
date/presentation date/viva date/etc., must go through valid application procedure
with supporting document within the deadline of the actual evaluation date.
• Makeup for missing Midterm/Final term must go through Set B form along with the
supporting document within the 1st working day after exam week. The set B exam
is generally scheduled from the 2nd working day after the exam week. Must get
signature and exam date from the course teacher and get it approved by the
department Head (monetary penalty might be imposed).
• Students unable to attend the set B exam may apply for set C exam within the
same time limit as set B. Such applications must be supported by very strong
reason and documentation, as they are generally rejected.
• The course teacher will be the judge of accepting/rejecting the request for makeup.
 Grading Policies
• All the evaluation categories & marks will be uploaded to the VUES within one
week of the evaluation process except the attendance & performance, which will
be uploaded along with the major (mid/final term) written exam marks.
• Letter grades ‘A+’ through ‘F’ is counted as grades. Other grades ‘I’ and ‘UW’ are
considered as temporary grades which are counted/calculated as ‘F’ grade in the
CGPA. These grades must/will be converted to the actual grades, i.e. ‘A+’ to ‘F’.
• ‘I: INCOMPLETE’ is given to students who have missed at most 30% of evaluation
categories (quiz/assignment/etc.). Students must contact the course teacher for
makeup, through valid application procedures immediately after grade release.
• ‘UW: UNOFFICIAL WITHDRAW’ is given when the missing evaluation categories
are too high (more than 30%) to makeup. A student getting ‘UW’ has no option but
to drop the course immediately after grade release
 Grading Policies…
• Once a student’s gets ‘I’ or ‘UW’ and unable to fulfill the requirements with the
course teacher for makeup, must drop the course within officially mentioned time
period from the registration department.

• Students in probation or falls into the probation due to ‘I’/’UW’ grade are not
allowed to drop the course.
• Unable to do so will result in the automatic conversion of the grades ‘I’/’UW’ to ‘F’
grade after the 4th week of the following semester.

• Any problem with the mark/grade must be consulted with the course teacher
within one week of the release of grades.
 Dropping a Course
• Must fill up the drop form and get it signed by the course teacher, write an
application to the vice chancellor and get it signed by the department Head,
and finally submit the form & application to the registration department.
• The course teacher must write down the grades (if any) obtained in midterm,
final, and grand total on the drop form.
• No drop is accepted during the following periods:
 One week before midterm exam – grade release date of midterm exam.
 One week before final term exam – grade release date of final grade.
• Student with ‘F’ grades in midterm, final term, or grand total cannot drop.
• Probation student are not allowed to drop any course.
 Contacts

• Contact information (email, office phone extension, office location,

consulting hours, etc.) of the course teacher must be stored by the students.
• It is mandatory to contact/notify (preferably consulting hour/email) the
course teacher for/of any problems/difficulties at the earliest possible. Late
notification might not be considered.
• Update & correct your email address & phone number at VUES, as the
teacher will contact/notify you of anything regarding the course through
these information in VUES.
 Finally
• For any problems that could not be solved/understood during the lecture, students are
advised to contact during the consultation hours and solve the problem.
• For any missing evaluation (quiz, assignment, etc.), classes, deadlines, etc. must
contact/inform/notify the teacher immediately after missing in the consulting hour, via email, or
in unavoidable circumstances – through the guardian or friend.
• Probation students must meet the course teacher once a week. So schedule your time with
the teacher.
• Any kind of dishonesty, plagiarism, misbehavior, misconduct, etc. will not be tolerated. Might
result in deduction of marks, ‘F’ grade, or reported to the AIUB Disciplinary Committee for
drastic punishment.
• Always check/visit the AIUB home page for notices, rules & regulations of academic/university
policies and important announcement for deadlines (Course drop, Exam permit, Exam
Schedule, etc.).
Welcome to the
course
Algorithms
What will we learn
in this course?
 The Goals of this Course

• To think algorithmically
• To understand and learn the idea behind algorithm
design techniques
• To get to know a toolbox of classical algorithms.
• To reason (in a precise and formal way) about the
efficiency and the correctness of algorithms.
 I would request all of you to...
• Be simple and precise in understanding the problem
• Solve the problem first on the paper, and then implement it
in computer.
• During lectures:
 Interaction is welcome, ask questions
 Additional explanations and examples if desired
 Speed up/slow down the progress
 What is an Algorithm?

A set of steps to accomplish a task

 ILP NNA Metric TSP
Total Distance 4059 5189 Km. 5096 Km.
Time complexity Exponential (43 min) Polynomial Polynomial

Approximation Ration Optimum - 2 approximations

Difference 1130 Km. 1037 Km.

 Informally
takes some value produces some
or set of values Algorithm: any well-defined value or set of
computational procedure values, as
as input output

• An algorithm is thus a sequence of computational steps that transform the

input into the output.
• Solving a given problem:
 Data structure: Organization of data to solve the problem at hand.
 Algorithm: Outline, the essence of a computational procedure, step-by-step instructions.
 Program: Implementation of an algorithm in some programming language.
 Kinds of Problem to be solved
• Sorting and Searching are the basic and most common computational
problem.
• Clever algorithms are employed for the Internet
 To manage large volume of data transfer
 Finding good routes on which the data will travel
 Search engine to quickly find requested pages
 Etc…

• Numerical algorithms and number theory are employed in electronic

commerce to keep and secure information such as credit card numbers,
passwords, and bank statements.
 Kinds of Problem to be solved
• Allocating scarce resources in the most beneficial way
 An oil company may wish to know where to place its wells in order to maximize its expected
profit.
 A candidate may want to determine where to spend money buying campaign advertising in
order to maximize the chances of winning at election.
 An airline may wish to assign crews to flight in the least expensive way possible, making sure
that each flight is covered and that government policy regarding crew policies are met.
 Etc…
 Algorithmic problem

Specification of
Specification of Algorithm
output as a
input function of
input

• Finite number of input instances satisfying the specification.

For example:
 A sorted, non-decreasing sequence of natural numbers. The sequence is of non-
zero, finite length:
♦ 1, 20, 908, 909, 100000, 1000000000.
♦ 3.
 Algorithmic Solution
Input instance, Output related to
adhering to the the input as
Algorithm
specification required

• Algorithm describes actions on the input instance.

• There may be many correct algorithms for the same algorithmic
problem.
 Definition of an Algorithm
• 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.
Properties of Algorithms
Problems vs Algorithms vs Programs
Expressing Algorithms
Common Elements of Algorithms
Testing Correctness
Proving Correctness
 Overall Picture
Using a computer to help solve Data Structure and Algorithm Design
problems. Goals
Correctness Efficiency
• Precisely specify the problem.
• Designing programs
 Architecture  data structure
 Technique  algorithms Implementation Goals
Adaptability Reusability
• Writing programs
• Verifying (testing) programs

Robustness
 How to Develop an Algorithm?
• Precisely define the problem.
 Precisely specify the input and output.
 Consider all cases.
• Come up with a simple plan to solve the problem at hand.
 The plan is language independent.
 The precise problem specification influences the plan.
• Turn the plan into an implementation
 The problem representation (data structure) influences the implementation.
Suppose computers were infinitely fast and
computer memory was free.

Would you have any reason to study

algorithms?
Algorithm Analysis
 Analysis of Algorithms
• An algorithm is a finite set of precise instructions for
performing a computation or for solving a problem.
• What is the goal of analysis of algorithms?
 To compare algorithms mainly in terms of running time but also
in terms of other factors (e.g., memory requirements,
programmer's effort etc.)
• What do we mean by running time analysis?
 Determine how running time increases as the size of the
problem increases.
 Input Size
• Input size (number of elements in the input)
 size of an array
 polynomial degree
 # of elements in a matrix
 # of bits in the binary representation of the input
 vertices and edges in a graph
 Types of Analysis
• Worst case
 Provides an upper bound on running time
 An absolute guarantee that the algorithm would not run longer, no matter what the inputs are
• Best case
 Provides a lower bound on running time
 Input is the one for which the algorithm runs the fastest

Lower Bound Running Time Upper Bound

• Average case
 Provides a prediction about the running time
 Assumes that the input is random
 …Best/ Worst/ Average Case
 For inputs of all sizes:

worst-case

6n average-case
Running time

5n
best-case
4n

3n

2n

1n

1 2 3 4 5 6 7 8 9 10 11 12 …..
Input instance size
 How do we compare algorithms?
• We need to define a number of objective measures.

(1) Compare execution times?

Not good: times are specific to a particular computer !!

(2) Count the number of statements executed?

Not good: number of statements vary with the programming
language as well as the style of the individual programmer.
 Ideal Solution
• Express running time as a function of the input
size n (i.e., f(n)).
• Compare different functions corresponding to
running times.
• Such an analysis is independent of machine time,
programming style, etc.
 The RAM model
• Machine-independent algorithm design depends upon a hypothetical computer
called the Random Access Machine or RAM.
• In computer science, random-access machine (RAM) is an abstract machine
• The RAM model:
 Each “simple” operation (+, *, -, =, if, call) takes exactly 1 time step
 Loops and subroutines are not considered simple operations. Instead, they are the
composition of many single-step operations. It makes no sense for “sort” to be a single-step
operation, since sorting 1,000,000 items will take much longer than sorting 10 items. The
time it takes to run through a loop or execute a subprogram depends upon the number of
loop iterations or the specific nature of the subprogram.
 Each memory access takes exactly one time step, and we have as much memory as we
need. The RAM model takes no notice of whether an item is in cache or on the disk, which
simplifies the analysis.
 Example
• Associate a "cost" with each statement.
• Find the "total cost“ by finding the total number of times each statement is
executed.
Algorithm 1 Algorithm 2

Cost Cost
arr[0] = 0; c1 for(i=0; i<N; i++) c2
arr[1] = 0; c1 arr[i] = 0; c1
arr[2] = 0; c1
... ...
arr[N-1] = 0; c1
----------- -------------
c1+c1+...+c1 = c1 x N (N+1) x c2 + N x c1 = (c2 + c1) x N + c2
 Another Example
• Algorithm 3 Cost
sum = 0; c1
for(i=0; i<N; i++) c2
for(j=0; j<N; j++) c2
sum += arr[i][j]; c3
------------
c1 + c2 x (N+1) + c2 x N x (N+1) + c3 x N2
 Asymptotic Analysis
• To compare two algorithms with running times f(n) and
g(n), we need a rough measure that characterizes how
fast each function grows.
• Hint: use rate of growth
• Compare functions in the limit, that is, asymptotically!
(i.e., for large values of n)
 Rate of Growth
• Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
• The low order terms in a function are relatively insignificant
for large n
n4 + 100n2 + 10n + 50 ~ n4

i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the same

rate of growth
 Asymptotic Notation
• The “big-Oh” O-Notation
 asymptotic upper bound
 f(n) = O(g(n)), if there exists constants c>0 and n0>0, s.t. f(n) £ c g(n) for n ³ n0
 f(n) and g(n) are functions
over non- negative integers c g ( n )
f (n )
• Used for worst-case analysis

Running Time
• g(n) is an asymptotic upper bound for f(n)

n0 Input Size
 ...Asymptotic Notation
• The “big-Omega” W-Notation
 asymptotic lower bound

 f(n) = W(g(n)) if there exists constants c>0 and n0>0, s.t. c g(n) £ f(n) for n ³ n0

• Used to describe best-case running times or lower bounds of algorithmic problems.

• g(n) is an asymptotic lower bound for f(n)

f (n )

Running Time
c g ( n )

n0 Input Size
 ...Asymptotic Notation
• The “big-Theta” Q-Notation
 asymptoticly tight bound

 f(n) = Q(g(n)) if there exists constants c1>0, c2>0, and n0>0, s.t. for n ³ n0

c1 g(n) £ f(n) £ c2 g(n)

 g(n) is an asymptotic tight bound for f(n) c 2 g (n )

f (n )

Running Time
c1 g (n )

n0 Input Size
 Big-O Notation

• We say fA(n)=30n+8 is order n, or O (n)

It is, at most, roughly proportional to n.
• fB(n)=n2+1 is order n2, or O(n2). It is, at most, roughly
proportional to n2.
• In general, any O(n2) function is faster- growing than any
O(n) function.
 Visualizing Orders of Growth
• On a graph, as
you go to the
right, a faster
growing

Value of function 
fA(n)=30n+8
function
eventually
becomes fB(n)=n2+1
larger...
Increasing n 
 More Examples …

• n4 + 100n2 + 10n + 50 is O(n4)

• 10n3 + 2n2 is O(n3)
• n3 - n2 is O(n3)
• constants
 10 is O(1)
 1273 is O(1)
 Back to Our Example
Algorithm 1 Algorithm 2
Cost Cost
arr[0] = 0; c1 for(i=0; i<N; i++) c2
arr[1] = 0; c1 arr[i] = 0; c1
arr[2] = 0; c1
...
arr[N-1] = 0; c1
----------- -------------
c1+c1+...+c1 = c1 x N (N+1) x c2 + N x c1 =
(c2 + c1) x N + c2

• Both algorithms are of the same order: O(N)

 Example (cont’d)

Algorithm 3 Cost
sum = 0; c1
for(i=0; i<N; i++) c2
for(j=0; j<N; j++) c2
sum += arr[i][j]; c3
------------
c1 + c2 x (N+1) + c2 x N x (N+1) + c3 x N2 = O(N2)
Big-O Visualization

O(g(n)) is the set of

functions with smaller or
same order of growth as g(n)
 More Examples

• Show that 30n+8 is O(n).

 Show c,n0: 30n+8  cn, n>n0 .
♦ Let c=31, n0=8. Assume n>n0=8. Then
cn = 31n = 30n + n > 30n+8, so 30n+8 < cn.
 Big-O example, graphically
• Note 30n+8 isn’t
less than n
anywhere (n>0).
• It isn’t even cn =
less than 31n 31n 30n+8

Value of function 
everywhere.
• But it is less than
31n everywhere to 30n+8
n
the right of n=8. O(n)
n>n0=8 
Increasing n 
 No Uniqueness
• There is no unique set of values for n0 and c in proving the asymptotic bounds

• Prove that 100n + 5 = O(n2)

 100n + 5 ≤ 100n + n = 101n ≤ 101n2

for all n ≥ 5

n0 = 5 and c = 101 is a solution

 100n + 5 ≤ 100n + 5n = 105n ≤ 105n2

for all n ≥ 1

n0 = 1 and c = 105 is also a solution

Must find SOME constants c and n0 that satisfy the asymptotic notation relation
 Relations Between Different Sets
• Subset relations between order-of-growth sets.

RR
O( f ) ( f )
•f
( f )
• Practice exercise from CLRS book
Insertion Sort
 Analysis of Insertion Sort
• Time to compute the running time as a function of the input size
(exact analysis).

cost times
for j := 2 to n do c1 n
key := A[j] c2 n-1
// Insert A[j] into A[1..j-1] 0 n-1
i := j-1 c3 n-1

n
while i>0 and A[i]>key do j 2
tj
c4

n
A[i+1]:=A[i] j 2
(t j  1)
c5

n
i-- j 2
(t j  1)
A[i+1]:=key c6 n-1
c7
 …Analysis of Insertion Sort
• The running time of an algorithm is the sum of the running times
of each statement.
• A statement with cost c that is executed n times contributes c*n
to the running time.
• The total running time T(n) of insertion sort is

n
 
n n
T(n)= c1*n + c2(n-1) + c3(n-1) + c4 j 2
tj+ c (t j  1)+ c6 j 2
(t j  1)
5 j 2

+ c7 (n-1)
 …Analysis of Insertion Sort

• Often the performance depends on the details of the

input (not only the length n).
• This is modeled by tj.

• In the case of insertion sort the time tj depends on the

original sorting of the input array.
 Performance Analysis
• Performance often draws the line between what is feasible and what is impossible.
• Often it is sufficient to count the number of iterations of the core (innermost) part.
 No distinction between comparisons, assignments, etc (that means roughly the same cost for all of
them).
 Gives precise enough results.

• In some cases the cost of selected operations dominates all other costs.
 Disk I/O versus RAM operations.
 Database systems.
 Best/ Worst/ Average Case
• Best case: works fast on some input.
• Worst case: (usually) maximum time of algorithm on any input of size.
• Average case: (sometimes) expected time of algorithm over all inputs of size. Need
assumption of statistical distribution of inputs.

• Analyzing insertion sort’s

 Best case: elements already sorted, tj=1, running time » (n-1), i.e., linear time.
 Worst case: elements are sorted in inverse order, tj = j-1, running time » (n2-n)/2 , i.e.,
quadratic time.
 Average case: tj = j / 2, running time » (n2+n-2)/4 , i.e., quadratic time.
 …Best/ Worst/ Average Case
• Worst case is usually used:
 It is an upper-bound.
 In certain application domains (e.g., air traffic control, surgery) knowing the
worst-case time complexity is of crucial importance.
 For some algorithms worst case occurs fairly often
 The average case is often as bad as the worst case.
 Finding the average case can be very difficult.
 Asymptotic Analysis
• Goal: to simplify the analysis of the running time by getting rid of details,
which are affected by specific implementation and hardware
 rounding of numbers: 1,000,001 » 1,000,000
 rounding of functions: 3n2 » n2
• Capturing the essence: how the running time of an algorithm increases
with the size of the input in the limit.
 Asymptotically more efficient algorithms are best for all but small inputs
 ...Asymptotic Analysis
• Simple Rule: Drop lower order terms and constant factors.
 50 n log n is O(n log n)
 7n - 3 is O(n)
 8n2 log n + 5n2 + n is O(n2 log n)
• Note: Although (50 n log n) is O(n5), it is expected that an
approximation is of the smallest possible order.
Common orders of magnitude
Growth Rates and Dominance Relations
 Loop invariants
and the correctness of insertion sort

• Initialization: It is true prior to the first iteration of the loop.

• Maintenance: If it is true before an iteration of the loop, it remains true

before the next iteration.

• Termination: When the loop terminates, the invariant gives us a useful

property that helps show that the algorithm is correct.
 Correctness of Algorithms
• An algorithm is correct if for any legal input it terminates and
produces the desired output.
• Automatic proof of correctness is not possible (so far).
• There are practical techniques and rigorous formalisms that help
to reason about the correctness of (parts of) algorithms.
 Partial and Total Correctness
 Partial correctness if a solution is returned, it will be correct

IF this point is reached, THEN this is the desired output

Any legal input Algorithm Output

 Total correctness Algorithm always returns at least one correct solution

INDEED this point is reached, AND this is the desired output

Any legal input Algorithm Output

 Assertions
• To prove partial correctness we associate a number of assertions (statements about

the state of the execution) with specific checkpoints in the algorithm.

 E.g., A[1], …, A[ j ] form an increasing sequence

• Preconditions – assertions that must be valid before the execution of an algorithm or

a subroutine (INPUT).

• Postconditions – assertions that must be valid after the execution of an algorithm or

a subroutine (OUTPUT).
 Pre/post-conditions
• Example:
 Write a pseudocode algorithm to find the two smallest numbers in a sequence of
numbers (given as an array).

• INPUT: an array of integers A[1..n], n > 0

• OUTPUT: (m1, m2) such that
 m1<m2 and for each iÎ[1..n]: m1 £ A[i] and, if A[i] ¹ m1, then m2 £ A[i].
 m2 = m1 = A[1] if "j,iÎ[1..n]: A[i]=A[j]
 Loop Invariants
• Invariants: assertions that are valid any time they are reached (many times during

the execution of an algorithm, e.g., in loops)

• We must show three things about loop invariants:
 Initialization: it is true prior to the first iteration.

 Maintenance: if it is true before an iteration, then it is true after the iteration.

 Termination: when a loop terminates the invariant gives a useful property to show the

correctness of the algorithm

 Example: Binary Search
ll :=
:= 11
rr :=
:= nn
 We want to show that q is not in A if do
do
:= ë(l+r)/2û
mm := ë(l+r)/2û
NIL is returned. if
if A[m] == qq then
A[m] then return
return mm
else
else ifif A[m]
A[m] >> qq then
then rr :=
:= m-1
m-1
 Invariant: else
else ll :=:= m+1
m+1
"iÎ[1..l-1]: A[i]<q (Ia) while
while ll <= <= rr
return
return NILNIL
"iÎ[r+1..n]: A[i]>q (Ib)
• Initialization: l = 1, r = n the invariant holds because there are no elements to the
left of l or to the right of r.
• l=1 yields "j,i Î[1..0]: A[i]<q
this holds because [1..0] is empty
• r=n yields "j,i Î[n+1..n]: A[i]>q
this holds because [n+1..n] is empty
 …Example: Binary Search
ll :=
:= 11
rr :=
:= nn
 Invariant: do
do
"iÎ[1..l-1]: A[i]<q (Ia) := ë(l+r)/2û
mm := ë(l+r)/2û
"iÎ[r+1..n]: A[i]>q (Ib) if
if A[m] == qq then
A[m] then return
return mm
else
else ifif A[m]
A[m] >> qq then
then rr :=
:= m-1
m-1
else
else ll :=:= m+1
m+1
while l <=
while l <= r r
return
return NILNIL

• Maintenance: l, r, m = ë(l+r)/2û
• A[m]!=q & A[m]>q, r=m-1, A sorted implies
"kÎ[r+1..n]: A[k]>q (Ib)
• A[m]!=q & A[m]<q, l=m+1, A sorted implies
"kÎ[1..l-1]: A[k]<q (Ia)
 …Example: Binary Search
ll :=
:= 11
 Invariant: rr :=
:= nn
"iÎ[1..l-1]: A[i]<q (Ia) do
do
"iÎ[r+1..n]: A[i]>q (Ib) := ë(l+r)/2û
mm := ë(l+r)/2û
if
if A[m] == qq then
A[m] then return
return mm
else
else ifif A[m]
A[m] >> qq then
then rr :=
:= m-1
m-1
else l :=
else l := m+1m+1
while
while ll <= <= rr
return
return NILNIL
• Termination: l, r, l<=r
• Two cases:
 l:=m+1 we get ë(l+r)/2û +1 > l
 r:=m-1 we get ë(l+r)/2û -1 < r
• The range gets smaller during each iteration and the loop will
terminate when l<=r no longer holds.
 Mathematical Induction
• A powerful, rigorous technique for proving that a statement
S(n) is true for every natural number n, no matter how large.

• Proof:

 Basis step: prove that the statement is true for n = 1

 Inductive step: assume that S(n) is true and prove that S(n+1)

is true for all n ≥ 1

• Find case n “within” case n+1

 Proof by Induction
• We want to show that property P is true for all integers n ³ n0.
• Basis: prove that P is true for n0.
• Inductive step: prove that if P is true for all k such that n0 £ k £ n – 1
then P is also true for n.
• Example

• Basis n
n( n  1)
S ( n)  i  for n 1
i 0 2
1
1(1  1)
S (1)  i 
i 0 2
 ...Proof by Induction
• Inductive Step
k
k ( k  1)
S ( k )  i  for 1 k n  1
i 0 2
n n 1
S ( n)  i  i  n S ( n  1)  n 
i 0 i 0

( n  1  1) ( n 2  n  2n)
( n  1) n  
2 2
n( n  1)

2
 Example
• Prove that: 2n + 1 ≤ 2n for all n ≥ 3
• Basis step:
 n = 3: 2  3 + 1 ≤ 23  7 ≤ 8 TRUE
• Inductive step:
 Assume inequality is true for n, and prove it for (n+1):
2n + 1 ≤ 2n must prove: 2(n + 1) + 1 ≤ 2n+1
2(n + 1) + 1 = (2n + 1 ) + 2 ≤ 2n + 2 ≤
 2n + 2n = 2n+1, since 2 ≤ 2n for n ≥ 1
Exercise
Binary Search
Step 1: Hypothesize a Loop Invariant
Step 2: Construct Loop Invariant
Step 3: Prove that loop invariant is inductive
Step 4: Prove correctness property using loop invariant
 Sorting
• Sorting is a classical and important algorithmic problem.
• We look at sorting arrays (in contrast to files, which restrict random
access).
• A key constraint is the efficient management of the space
 In-place sorting algorithms
• The efficiency comparison is based on the number of comparisons (C)
and the number of movements (M).
 Sorting
• Simple sorting methods use roughly n * n comparisons
 Insertion sort
 Selection sort
 Bubble sort
• Fast sorting methods use roughly n * log n comparisons.
 Merge sort
 Heap sort
 Quicksort
 References & Readings
• CLRS
 Chapters: 1, 2 (2.1, 2.2), 3
 Exercises: 1.2-2, 1.2-3, 2.1-3, 2.1-4, 2.2-1, 2.2-3, 3.1-1, 3.1-4, 3.1-6, 3.1
 Problems: 1-1, 3-3
• HSR
 Chapters: 1 (1.1-1.3)
 Examples: 1.4-1.6, 1.11-1.13, 1.17-1.18
 Exercises: 1.3 (1-4, 8, 9)
• Review for laboratory
 HSR
♦ Chapters: 2, 3.2 - 3.5
 CLRS
♦ Chapters: 6, 7, 10, 12
Common orders of magnitude
 Logarithms and properties
• In algorithm analysis we often use the notation “log n” without specifying the
base

Binary logarithm lg n log 2 n log x y  y log x

Natural logarithm ln n log e n log xy  log x  log y
x
lg k n (lg n ) k log  log x  log y
y
lg lg n lg(lg n ) log a
a logb x  x b

log b x  log a x
log a b
 More Examples
• For each of the following pairs of functions, either f(n) is O(g(n)), f(n) is
Ω(g(n)), or f(n) = Θ(g(n)). Determine which relationship is correct.
 f(n) = log n2; g(n) = log n + 5
f(n) =  (g(n))
 f(n) = n; g(n) = log n2
f(n) = (g(n))
 f(n) = log log n; g(n) = log n
f(n) = O(g(n))
 f(n) = n; g(n) = log2 n f(n) = (g(n))
 f(n) = n log n + n; g(n) = log n f(n) = (g(n))
 f(n) = 10; g(n) = log 10 f(n) = (g(n))
 f(n) = 2n; g(n) = 10n2 f(n) = (g(n))
 f(n) = 2n; g(n) = 3n f(n) = O(g(n))
 Properties
• Theorem:
f(n) = (g(n))  f = O(g(n)) and f = (g(n))
• Transitivity:
 f(n) = (g(n)) and g(n) = (h(n))  f(n) = (h(n))
 Same for O and 
• Reflexivity:
 f(n) = (f(n))
 Same for O and 
• Symmetry:
 f(n) = (g(n)) if and only if g(n) = (f(n))
• Transpose symmetry:
 f(n) = O(g(n)) if and only if g(n) = (f(n))
 Asymptotic Notations in Equations
• On the right-hand side
 (n2) stands for some anonymous function in (n2)
2n2 + 3n + 1 = 2n2 + (n) means:
There exists a function f(n)  (n) such that
2n2 + 3n + 1 = 2n2 + f(n)
• On the left-hand side
2n2 + (n) = (n2)
No matter how the anonymous function is chosen on the left-hand side,
there is a way to choose the anonymous function on the right-hand
side to make the equation valid.
 Common Summations
n
n ( n  1)
• Arithmetic series:  k 1  2  ...  n 
k 1 2
n
x n 1  1
• Geometric series:  k 2
x 1  x  x  ...  x n
x 1
k 0 x 1

1
 Special case: |x| < 1: x
k 0
k

1 x
n
1 1 1
• Harmonic series:  1   ...  ln n
k 1 k 2 n
n
• Other important formulas:  lg k n lg n
k 1

n
1
 k p 1p  2 p  ...  n p 
k 1 p 1
n p 1