CSC 320: Algorithm

and Complexity

DR. VICTOR ODUMUYIWA

General Information
Instructors
◦ Dr. Victor Odumuyiwa,
◦ Room 112 (Computer Science building),
◦ vodumuyiwa@unilag.edu.ng,
◦ Office hours: Tuesday 2-3pm
◦ Dr. Lucky Ikuvwerha

Lecture: Tuesday 12:00 -14:00 (E303)

Expectations
◦ Your attendance in the lectures and recitations (tutorials) is very important. I expect that
every student should be in class before the lecturer enters. Late coming causes distractions so
your punctuality will be highly appreciated.
Why algorithm?
 20th century science was dominated by mathematics, physics and chemistry
 21st century will focus majorly on the science of algorithm
 Algorithm is everywhere
 In our DNA
 In ant colony
 In swarm behaviour
 In self-driving cars
 In drones
 The efficiency and effectiveness of hardware and software depend largely on the
underlying algorithms
 Unfortunately, computers are limited in time (processing) and space (memory)
 What do we do?
Learning Outcomes
At the end of this course, you should be able to:
 Demonstrate a good understanding of the role of algorithms in
computing
 Design appropriate algorithmic solutions for problem solving
using different paradigms
 Prove that your algorithms are correct
 Analyse algorithms to determine their efficiency
 Perform asymptotic and empirical analysis of some popular
algorithms
Course Content
 Roles of Algorithms in Computing
 Some Representative Problems
 Analysis of Algorithm
 Design of Algorithms
 Divide-and-Conquer
 Dynamic Programming
 Greedy Algorithms
 Graph Algorithms
 Computational Complexity
Course Schedule
WEEK TOPICS COURSE INSTRUCTORS

Week1 Introduction Dr. V. T. Odumuyiwa

(Course Coordinator)
Week2 Sorting Algorithm: Insertion Sort Dr. V. T. Odumuyiwa

Week3 Algorithm Design and Paradigms Dr. V. T. Odumuyiwa

Week4 Sorting Algorithm: Dr. V. T. Odumuyiwa

Mergesort

Week5 Sorting Algorithm: Dr. V. T. Odumuyiwa

Heapsort, Quicksort

Week6 Searching Algorithm: Dr. V. T. Odumuyiwa

Linear-time Sorts, binary search
Course Schedule
WEEK TOPICS COURSE INSTRUCTORS

Week7 Dynamic Programming Dr. L. Ikuvwehra

Week8 MID-SEMESTER TEST

Week9 Graph algorithms: the basics Dr. L. Ikuvwehra

Week10 Graph algorithms: BFS Dr. L. Ikuvwehra

Week11 Graph algorithms: DFS Dr. L. Ikuvwehra

Week12 NP-Completeness Dr. L. Ikuvwehra

Week13 Approximation Algorithms Dr. L. Ikuvwehra

Textbooks
 Cormen T.H., Leiserson C.E., Rivest R.L., & Stein C. (2009), Introduction to
Algorithms, MIT press.
 Steven S S. Skiena (2011) The Algorithm Design Manual, 4th Edition,
Pearson – Adisson Wesley
 Jon Kleinberg & Éva Tardos (2005) Algorithm Design, Pearson-Adisson
Wesley
 Liang D.Y. (2015) Introduction to Java Programming, Comprehensive
Version, 10th Edition, Pearson Education Inc.
Collaboration Policy
 The problem sets are to be solved independently. You may collaborate with
other students on your problem sets to come up with implementation
ideas but the codes you are submitting must have be written by you and
should be unique.
 Copying code or solutions from the Internet or any source whatsoever is
not allowed. Any violation will be penalized (zero mark).
 Specific collaboration policy will be given for each assignment and project
Lecture1: The Role of
Algorithms in Computing
DR. VICTOR ODUMUYIWA
Learning Outcomes
At the end of this class, you should be able to:
 describe the characteristics of an algorithm,
 write a simple algorithm.
Readings
Chapter 1
◦ Cormen T.H., Leiserson C.E., Rivest R.L., & Stein C. (2009), Introduction to Algorithms, MIT press.

Chapter 1
◦ Jon Kleinberg & Éva Tardos (2005) Algorithm Design, Pearson-Adisson Wesley

Chapter 1
◦ Steven S S. Skiena (2011) The Algorithm Design Manual, 4th Edition, Pearson – Adisson Wesley
What is an Algorithm
A set of steps for performing a task
Example:
 Algorithm to make a cup of tea
 Algorithm to prepare a lecture note
 Algorithm to move a car from point A to point B
 Algorithm to prepare for an exam
 Algorithm to sew a piece of cloth
What is Computer Algorithm?
“A set of steps to accomplish or complete a task that is described
precisely enough that a computer can run it”
Definition
 A sequence of computational steps that transforms the input
into the output
 A tool for solving well specified computational problem
 Problem statement – specifies the desired input/output relationship
 Algorithm – elicitation of a specific computational procedure for
achieving the input/output relationship
Definition contd.
Input: A sequence of n numbers ‹a1, a2, …, an›

Output: A permutation (reordering) ‹a'1, a'2, …, a'n› of the

input sequence such that a'1 ≤ a'2 ≤ … ≤ a'n
For the input/output relationship stated above, a sorting algorithm is needed
‹10, 8, 21, 67, 48, 89› ---- An input sequence (an instance of the problem)
‹8, 10, 21, 48, 67, 89› ---- An output sequence
Theory of Algorithms
"As soon as an Analytic Engine exists, it will necessarily
guide the future course of the science. Whenever any
result is sought by its aid, the question will arise - By what
course of calculation can these results be arrived at by the
machine in the shortest time? - Charles Babbage

Source: Kevin Wayne’s lecture note (Princeton University, Spring 2005) 17

Characteristics of an Algorithm
 Takes input
 A finite input
 Produces output
 At least an output
 Definite (no ambiguity)
 Each instruction must be precisely defined
 Finite
 Terminates in finite number of steps
 Each step must be executed in finite number of time
 Effective (every instruction must be basic)
 Basic enough that it can be done manually (using pencil and paper) in a finite length of time
Correctness of an Algorithm
 An input that satisfies the constraints imposed on a problem
statement is considered as an instance of the problem
 “An algorithm is said to be correct if, for every input instance, it
halts with the correct output”
Diverse Application Areas
 Caching  Signal processing
 Compilers  Computer graphics
 Databases  Scientific computing
 Scheduling  Operations research
 Networking  Artificial intelligence
 Data analysis  Computational biology
Applications
“We are given a road map on which the distance between each
pair of adjacent intersections is marked, and we wish to
determine the shortest route from one intersection to another.
The number of possible routes can be huge, even if we disallow
routes that cross over themselves. How do we choose which of all
the possible route is the shortest?”
Problem 1
Come up with a real-world problem in which only the best
solution will do. Then come up with one in which a solution that
is “approximately” the best is good enough.
Algorithm as a Technology (1/3)
 Algorithm versus hardware
 “total system performance depends on choosing efficient algorithms as
much as on choosing fast hardware”
 Computer A runs 10 billion instructions per second
 Computer B runs 10 million instructions per second
 Two sorting algorithms
 Insertion sort (c.n2)
 Merge sort (c.nlg n)
Algorithm as a Technology (2/3)
 Good implementation of insertion sort on A using machine
language requires 2n2 instructions to sort n numbers
 A bad implementation of merge sort on B using a high level
language requires 50n lg n instructions
 To sort 10 million numbers
 A takes 20,000 seconds (over 51/2 hrs)
 B takes ~1163 seconds (less than 20 minutes)
Algorithm as a Technology (3/3)
To sort 10 million numbers

2 𝑥 107 2 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠
A takes = 20,000 seconds
1010 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠/𝑠𝑒𝑐𝑜𝑛𝑑

50 𝑥 107 lg 107 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠

B takes ~ 1163 seconds (less than 20
107 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠/𝑠𝑒𝑐𝑜𝑛𝑑
minutes)
CADR – The LISP Machine
“The LISP machine was the first hardware
implementation of the AI programming
language LISP. Researchers had long been
frustrated by the constraints of running
LISP programs on large mainframes. They
developed LISP machines as stand-alone,
single-user high-performance computers
that could run LISP programs faster and
with more efficiency” (MIT Museum).
Problem 2
 For each function f(n) and time t in the following table, determine the largest
size n of a problem that can be solved in time t, assuming that the algorithm
to solve the problem takes f(n) microseconds.
1 second 1 minute 1 hour 1 day 1 month 1 year 1 century
lg n
√n
n
n lgn
n2
n3
2n
n!
Hint
1 second 1 minute 1 hour 1 day 1 month 1 year 1 century
6
lg n 210

√n 1012
n 106 6⋅107
n lgn
n2
n3
2n
n!
Lecture2: Analysis of
Algorithm
DR VICTOR ODUMUYIWA
Learning Outcome
At the end of this class, you should be able to:

 Determine the running time of an algorithm.

Readings
Chapter 2 and 3
◦ Cormen T.H., Leiserson C.E., Rivest R.L., & Stein C. (2009), Introduction to
Algorithms, MIT press.
Chapter 2
◦ Jon Kleinberg & Éva Tardos (2005) Algorithm Design, Pearson-Adisson
Wesley
Understanding Algorithm

Program Algorithm
Model of
computation
Programming
Pseudocode describes what your
language
computer can do in
Model of
Computer
computation constant time.

Analysis is performed with respect to a computational model

Computational Tractability
"As soon as an Analytic Engine exists, it will necessarily guide the future
course of the science. Whenever any result is sought by its aid, the
question will arise - By what course of calculation can these results be
arrived at by the machine in the shortest time? - Charles Babbage

34 Source: Kevin Wayne’s lecture note (Princeton University, Spring

Model of Computation
Specifies:

 The operations that an algorithm is allowed to

perform.

 The cost of each operation.

Computational Models
 Logic Circuit
 Finite State Machine (FSM)
 Random Access Machine (RAM)
 Pushdown Automaton
 Turing Machine
 Pointer Machine
 Any modern computer programming language
Random Access Machine
 Executes operations sequentially
 Performs set of primitive operations:
 arithmetic, logical, comparisons, function calls
 In constant time, O(1), can:
 load O(1) words,
 do O(1) computations,
 store O(1) words
 Simplifying assumption: all ops cost 1 unit
 Eliminates dependence on the speed of our computer,
otherwise impossible to verify and to compare
Two Stages of Analysis
Analysis of the efficiency of an algorithm can be:
 A priori analysis
◦ Theoretical analysis
◦ “Efficiency of an algorithm is measured by assuming that all other factors
e.g. processor speed, are constant and have no effect on implementation”.

 A posteriori analysis
 Empirical analysis
 Algorithm is implemented using programming language.
 The implementation is executed on target computer machine.
 Actual statistics like running time and space required, are collected.
A Priori Analysis
 Focus here is on a priori algorithm analysis

 “Algorithm analysis deals with the execution or running

time of various operations involved”.

 “Running time of an operation can be defined as no. of

computer instructions executed per operation”.
Algorithm Complexity
 Time complexity
 how many operations are performed?
 Space complexity
 What is the maximum memory space required by the algorithm?
 “The complexity of an algorithm f(n) gives the running time
and / or storage space required by the algorithm in terms of n
as the size of input data”.
Kinds of analyses
Worst-case: (usually)
• T(n) = maximum time of algorithm on any input of size n.
Average-case: (sometimes)
• T(n) = expected time of algorithm over all inputs of size n.
• Need assumption of statistical distribution of inputs.
• Need domain knowledge
Best-case: (we don’t rely on this)
Space Complexity (1/2)
 A fixed part that is a space required to store certain data and
variables, that are independent of the size of the problem. For example
simple variables & constant used, program size etc.
 A variable part is a space required by variables, whose size depends
on the size of the problem. For example dynamic memory allocation,
recursion stack space etc.
 Space complexity S(P) of any algorithm P is S(P) = C + SP(I) Where C is
the fixed part and SP(I) is the variable part of the algorithm which
depends on instance characteristic I.
Space Complexity (2/2)
Algorithm: Product(X, Y)
Step 1 - START
Step 2 - Z ← X * Y + 5
Step 3 - Stop
 Three variables X, Y and Z and one constant.
 Hence S(P) = 1+3.
 Now space depends on data types of given variables and constant types and
it will be multiplied accordingly.
The Sorting Problem
Input: A sequence of n numbers ‹a1, a2, …, an›

Output: A permutation (reordering) ‹a'1, a'2, …, a'n› of the

input sequence such that a'1 ≤ a'2 ≤ … ≤ a'n
For the input/output relationship stated above, a sorting algorithm is needed
‹10, 8, 21, 67, 48, 89› ---- An input sequence (an instance of the problem)
‹8, 10, 21, 48, 67, 89› ---- An output sequence
Insertion-Sort(A)
1. for j = 2 to A.length
2. key = A[j]
3. //insert A[j] into the sorted sequence A[1…j-1]
4. i = j-1
5. while i > 0 and A[i] > key
6. A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key
 Insertion-Sort(A) Cost Times
1 for j = 2 to A.length c1 n
2 key = A[j] c2 n-1
3 //insert A[j] into the sorted sequence A[1…j-1] c3 = 0 n-1
4 i = j-1 c4 n-1
𝑛
5 while i > 0 and A[i] > key c5
෍ 𝑡𝑗
𝑗=2

6 A[i+1] = A[i] c6 σ𝑛𝑗=2(𝑡𝑗 −1)

7 i = i-1 c7 σ𝑛𝑗=2(𝑡𝑗 −1)

8 A[i+1] = key c8 n-1

Analysis of Insertion-Sort(A)
T(n) will be computed by summing the products of the cost and times columns.

𝒏 𝒏 𝒏

𝑻 𝒏 = 𝒄𝟏𝒏 + 𝒄𝟐 𝒏 − 𝟏 + 𝒄𝟒 𝒏 − 𝟏 + 𝒄𝟓 ෍ 𝒕𝒋 + 𝒄𝟔 ෍(𝒕𝒋 − 𝟏) + 𝒄𝟕 ෍(𝒕𝒋 − 𝟏) + 𝒄𝟖 𝒏 − 𝟏

𝒋=𝟐 𝒋=𝟐 𝒋=𝟐
Best-case Analysis of Insertion-Sort(A)
 Occurs if the array is already sorted.
 For each j = 2, 3, … ,n, we find A[i] ≤ key in line 5.
 𝑡𝑗 = 1 for j = 2, 3, … ,n.
𝑛 𝑛

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 𝑛 − 1 + 𝑐6 ෍(1 − 1) + 𝑐7 ෍(1 − 1) + 𝑐8 𝑛 − 1

𝑗=2 𝑗=2

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 𝑛 − 1 + 𝑐8 𝑛 − 1

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2𝑛 − 𝑐2 + 𝑐4𝑛 − 𝑐4 +

𝑐5𝑛 − 𝑐5 + 𝑐8𝑛 − 𝑐8
Best-case Analysis of Insertion-Sort(A)
Contd.
𝑇 𝑛 = 𝑐1𝑛 + 𝑐2𝑛 + 𝑐4𝑛 + 𝑐5𝑛 + 𝑐8𝑛 − 𝑐2 − 𝑐4 − 𝑐5 − 𝑐8

𝑇 𝑛 = 𝑐1 + 𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 𝑛 − (𝑐2 + 𝑐4 + 𝑐5 + 𝑐8)

𝑇 𝑛 = 𝑎𝑛 + 𝑏

𝑇 𝑛 𝑖𝑠 𝑎 𝑙𝑖𝑛𝑒𝑎𝑟 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑛
Worst-case Analysis of Insertion-Sort(A)
(1/4)
 Occurs if the array is in reverse sorted order i.e. in decreasing order.
 For each j = 2, 3, … ,n, we compare each element A[j] with each
element in the entire sorted subarray A[1 .. j-1].
 𝑡𝑗 = j for j = 2, 3, … ,n

𝑛 𝑛 𝑛

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 ෍ 𝑡𝑗 + 𝑐6 ෍(𝑡𝑗 − 1) + 𝑐7 ෍(𝑡𝑗 − 1) + 𝑐8 𝑛 − 1

𝑗=2 𝑗=2 𝑗=2
Worst-case Analysis of Insertion-Sort(A) (2/4)
𝑛 𝑛 𝑛

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 ෍ 𝑗 + 𝑐6 ෍(𝑗 − 1) + 𝑐7 ෍(𝑗 − 1) + 𝑐8 𝑛 − 1

𝑗=2 𝑗=2 𝑗=2

𝑛 𝑛
𝑛 𝑛+1 𝑛 𝑛−1
෍𝑗 = −1 ෍(𝑗 − 1) =
𝑗=2
2 𝑗=2
2

𝑛 𝑛+1 𝑛 𝑛−1 𝑛 𝑛−1

𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 − 1 + 𝑐6 + 𝑐7 + 𝑐8 𝑛 − 1
2 2 2
Worst-case Analysis of Insertion-Sort(A)
(3/4)
𝑛2 + 𝑛 𝑛2 − 𝑛 𝑛2 − 𝑛
𝑇 𝑛 = 𝑐1𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 − 1 + 𝑐6 + 𝑐7 + 𝑐8 𝑛 − 1
2 2 2

𝑛2 𝑛 𝑛2 𝑛 𝑛2 𝑛
𝑇 𝑛 = 𝑐1𝑛 + 𝑐2𝑛 − 𝑐2 + 𝑐4𝑛 − 𝑐4 + 𝑐5 + 𝑐5 − 𝑐5 + 𝑐6 − 𝑐7 + 𝑐7 − 𝑐6 + 𝑐8𝑛 − 𝑐8
2 2 2 2 2 2

𝑛2 𝑛2 𝑛2 𝑛 𝑛 𝑛
𝑇 𝑛 = 𝑐5 + 𝑐6 + 𝑐7 + 𝑐1𝑛 + 𝑐2𝑛 + 𝑐4𝑛 + 𝑐5 − 𝑐7 − 𝑐6 + 𝑐8𝑛 − 𝑐2 − 𝑐4 − 𝑐5 − 𝑐8
2 2 2 2 2 2

𝑐5 𝑐6 𝑐7 2 𝑐5 𝑐6 𝑐7
𝑇 𝑛 = + + 𝑛 + 𝑐1 + 𝑐2 + 𝑐4 + − − 𝑛 + (𝑐2 − 𝑐4 − 𝑐5 − 𝑐8)
2 2 2 2 2 2
Worst-case Analysis of Insertion-Sort(A)
(4/4)
𝑐5 𝑐6 𝑐7 2 𝑐5 𝑐6 𝑐7
𝑇 𝑛 = + + 𝑛 + 𝑐1 + 𝑐2 + 𝑐4 + − − 𝑛 + (𝑐2 − 𝑐4 − 𝑐5 − 𝑐8)
2 2 2 2 2 2

𝑇 𝑛 = 𝑎𝑛2 + 𝑏𝑛 + 𝑐

𝑇 𝑛 𝑖𝑠 𝑎 𝑞𝑢𝑎𝑑𝑟𝑎𝑡𝑖𝑐 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑛