CSC207 Introduction to

Algorithms

Lecture notes for 2023/2024 Academic Year

Course instructors : Drs. Nyanga B., Achenkeng P. and
Fotsing C.
 What is an Algorithm?
• An algorithm consists of a set of explicit and unambiguous
finite steps which, when carried out for a given set of initial
conditions, produce the corresponding output and terminate in
finite time. Source(How to Solve it by Computer, RG Dromey,
Prentice Hall UK, 1982) Output:
• An algorithm is a finite, definite, effective procedure, with some
output. (source: Computer Science, D Woodhouse et al,
Jacaranda Wiley, 1984 )
• The series of steps that you develop to solve a problem is
known as a solution algorithm. There are many different
algorithms for almost any problem. (source:Understanding
Information Technology, K Behan and D Holmes,Prentice Hall
Australia, 1986. Reprinted with the permission of Prentice Hall
Australia Pty Ltd.)

CSC207 2024_2025 2
 Properties from definition
An algorithm is a finite set of steps required to solve a problem.
An algorithm must have following properties:
1. Input: An algorithm must have zero or more quantities as input whcih are
externally supplied.
2. Output: An algorithm must produce one or more output after processing set of
statements.
3. Definiteness: Each instruction must be clear and ditinct.
4. Finiteness: The algorithm must terminate after a finite number of steps.
5. Effectiveness: Each operations must be definite also it should be feasible

CSC207 2024_2025 3
 What is an algorithm?
• An algorithm is ―a finite set of precise instructions for
performing a computation or for solving a problem‖
– A program is one type of algorithm
• All programs are algorithms
• Not all algorithms are programs!
– Directions to somebody‘s house is an algorithm
– A recipe for cooking a cake is an algorithm
– The steps to compute the cosine of 90° is an algorithm

CSC207 2024_2025 4
 Some algorithms are harder than
others
• Some algorithms are easy
– Finding the largest (or smallest) value in a list
– Finding a specific value in a list
• Some algorithms are a bit harder
– Sorting a list
• Some algorithms are very hard
– Finding the shortest path between Miami and Seattle
• Some algorithms are essentially impossible
– Factoring large composite numbers
• We‘ll see later in the course how to rate how ―hard‖
algorithms are
CSC207 2024_2025 5
Example of an algorithm

1. Start 7. If (i<=n) go to step 6

2. Accept size for an array : (Read size) 8. If(flag=1) then

3. Accept array elements values from user i.e. Print found and Return i as position
Array elements.
Else
4. Accept element to be searched from user i.e.
Print not found
Read Value
9. Stop.
5. Set i=0,flag=0

6. Compare A[i] with value

If(A[i] is a value)

Set flag=1 go to step 8

Else

Move to next data element

i= i+1;

CSC207 2024_2025 6
 Homework:
• Q1) Suppose you are told to give the result of x squared where x is a (any) non-
negative integer.
• (i) State the computational problem in terms of prose descriptions that clearly
state:
• (a) in general terms what the computational problem is (including any
constraints);
• (b) its input (which must satisfy any constraints expressed in the problem
statement); and
• (c) its output (which must reflect the type of results expected).
• (ii) Give possible algorithms that describe the problem in (i) in terms of: (a)
multiplication of x; (b) addition of x.
• (iii) Which of the solutions in (ii) is more efficient? Explain.
• (iv) Is each algorithm correct? And does each terminate? Why or why not?

CSC207 2024_2025 7
 [Hint: (1) Try executing your
• algorithms for sample inputs and check the results obtained. (2) Consider executing
your algorithms
• using sample inputs with properties that are special to integers (e.g., positive, 0)
and to multiplication
• (in a) and addition (in b), such as 0 and 1. (3) Then, try to generalise that the result
would be correct
• and terminate for all valid inputs.]
• The homework is only illustrative, and exercises the concepts introduced in this
section. However, note
• that in the study of algorithms, a ―computational problem‖ typically describes a
general class of
• problems (e.g., sorting problem or search problem—see later) and algorithms are
developed to solve
• [variants] of this class (e.g., comparison-based sorting) or specific instances of them
(e.g., selection sort).

CSC207 2024_2025 8
 Data and Data Constructs
• Algorithms manipulate objects—i.e., data or values
which are taken (input), or manipulated to give
results (output).
• This data must be constructed (organised) in a
fashion suitable for use.
• Strictly, dataconstructs permit us to create different
kinds of data, and/or encode (represent) them for
algorithm manipulation.

CSC207 2024_2025 9
 Data and Data constructs
• Correspond to mathematical constructions such as
Cartesian product, disjoint union and [mathematical]
functions. In practical terms, such constructs define
data structures (relationships among data values).
• Data (or values) are stored somewhere (at a
location or address) which, for convenience, is
usually named.
• An assignment operation is the basic operation
normally used to store the data [in its location or
address].
CSC207 2024_2025 10
 Variables and Data Types
• Consider the equation x2 + 2y-2=1,
• equation has names (x and y), which hold values (data)
[Link] (x and y) are placeholders for representing
data. Data is also associated with the notion of types.
• A [data] type is essentially a set of values (objects)
together with a set of permissible operations on them;
that is, they determine what actions can be applied to
the data values.
• Thus, for example, numbers (integers) allow for
standard arithmetic operations on them; eggs allow for
whisking (by a baker).
CSC207 2024_2025 11
 Data Types
• A data type reduces the coding effort. At the top
level, there are two types of data types:
• System-defined data types (also called Primitive
data types)
– Primitive data types provided by some programming
languages are: int, float, char, double, bool, etc.
• User-defined data types

CSC207 2024_2025 12
 Data structures
• It is a particular way of storing and organizing
data in a computer so that it can be used
efficiently.
• Data structure types include arrays, files, linked
lists, stacks, queues, trees, graphs and so on.
• We will look at the basic definitions later in the
course

CSC207 2024_2025 13
 Algorithms vs Programs vs
Programming Language
• An algorithm is the step-by-step unambiguous
instructions to solve a given problem.
• A program is an algorithm executable on a
computer.
• A programming language is a collection of
primitives (basic actions and control and data
constructs), the rules governing how the
primitives are combined and the meanings
attributed to them (i.e., to the primitives and
their combinations) in order to express more
complex ideasCSC207
[as algorithms].
2024_2025 14
 Algorithms vs Programs vs
Programming Language
• Syntax refers to the symbols representing primitives and how
they can be combined; the rules constitute the grammar of
the language.
• emantics refers to the concept represented or the meaning
of the primitives.
• More precisely, it refers to the meaning associated with
entities (actions, constructs, objects, etc.).
• For aprogram, the basic actions (primitives) are the
instructions recognised by the computer (or processor).
• [Programming language] pragmas (short for pragmatics)
refers to options and techniques that permit one to efficiently
use or implement a language. e.g., how best to implement
variable bindings inCSC207 2024_2025
a compiler. 15
 What is Programming?
– Programming is the total creative process that
involves these stages:
• clearly define the problem
• analyse the problem
• design a solution
• implement the solution
• test the solution
• document the solution.
– In the appropriate circumstances we should also:
• compare alternative solutions

CSC207 2024_2025 16
 Illustrative examples: Euclid's
algorithm
• Euclidean algorithm or Euclid's algorithm, is an
efficient method for computing the greatest
common divisor (GCD) of two integers (numbers),
the largest number that divides them both without
a remainder.
• One of the oldest algorithms in common use.
• Used to reduce farctions to their simplest form,
and is a part of many other number-theoretic and
cryptographic calculations.

CSC207 2024_2025 17
 Euclid's algorithm
1 INPUT L, S [Into two locations L and S put the numbers l and s that represent the
two lengths]
2 R ← L : [Initialize R: make the remaining length r equal to the starting/initial/input
length l]
E0: [Ensure r ≥ s.]
3 IF R > S THEN GOTO step 7: [Ensure the smaller of the two numbers is in S and
the larger in R]: the contents of L is the larger number so skip over the exchange-
steps 4, 5 and 6:
ELSE: swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5R←S
6S←L
• E1: [Find remainder]: Until the remaining length r in R is less than the shorter
length s in S, repeatedly subtract
CSC207the measuring number s in18S from the remaining
2024_2025
length r in R.
 Euclid's algorithm
7 IF S > R THEN done measuring so GOTO 10 ELSE measure again,
8R←R−S
9 [Remainder-loop]: GOTO 7.
E2: [Is the remainder zero?]: EITHER (i) the last measure was exact, the remainder in R is
zero, and the program can halt, OR (ii) the algorithm must continue: the last measure left a
remainder in R less than measuring number in S.
10 IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11, E3: [Interchange s
and r]: The nut of Euclid's algorithm. Use remainder r to measure what was previously
smaller number s; L serves as a temporary location.
11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]: GOTO 7
OUTPUT:
15 PRINT S DONE: [Done. S contains the greatest common divisor ]:
16 HALT, END, STOP.
CSC207 2024_2025 19
 Comprised Euclid's algorithm
LET [] = [] is the assignment instruction symbolized by ←.
• 5 REM Euclid's algorithm for greatest common divisor
• 6 PRINT "Type two integers greater than 0"
• 10 INPUT A,B
• 20 IF B=0 THEN GOTO 80
• 30 IF A > B THEN GOTO 60
• 40 LET B=B-A
• 50 GOTO 20
• 60 LET A=A-B
• 70 GOTO 20
• 80 PRINT A
• 90 END

CSC207 2024_2025 20
 Euclid's C code
// Euclid's algorithm for greatest common
divisor
int euclidAlgorithm (int A, int B) {
A = abs(A);
B = abs(B);
while (B != 0)
{ while (A > B)
{ A = A-B; }
B = B-A; }
return A;
CSC207 2024_2025 21
}
 Representations for Algorithm
Development
• the same algorithm can be represented in
assorted notations.
• When discovering or developing algorithms,
one needs suitable representations [for partial
or as-yet-ill-formed ideas].
• common representations include: pseudocode,
flowcharts and dataflow diagrams.

CSC207 2024_2025 22
 Pseudocode
• Here, representation is a cross between statements
(basic actions, etc.) expressed in natural language
(e.g., English) and a programming language(s).
• makes it easier to think in a natural language, but
increasingly structure primitives in terms of a target
programming language (PL).
• is a mix of language constructs and natural
language used to express an algorithm, usually (not
always) in an algorithm development process.
• Pseudocode essentially is English with some
defined rules of structure and some keywords that
make it appear a bit like program code.
CSC207 2024_2025 23
 Some guidelines for writing pseudocode.
• The keywords used for pseudocode in this document are:
• for start and finish
• BEGIN MAINPROGRAM, END MAINPROGRAM
• for initialisation
• INITIALISATION, END INITIALISATION
• for subprogram
• BEGIN SUBPROGRAM, END SUBPROGRAM
• for selection
• IF, THEN, ELSE, ENDIF
• for multi-way selection
• CASEWHERE, OTHERWISE, ENDCASE
• for pre-test repetition
CSC207 2024_2025 24
 Guidelines for writing pseudocode cont.
• WHILE, ENDWHILE
• for post-test repetition
• REPEAT, UNTIL
• Keywords are written in capitals.
• Structural elements come in pairs, eg for every BEGIN there is an
END, for every IF there is an ENDIF, etc.
• Indenting is used to show structure in the algorithm.
• The names of subprograms are underlined. This means that when
refining the solution to a problem, a word in an algorithm can be
underlined and a subprogram developed.
• This feature is to assist the use of the ‗topdown‘ development
concept.

CSC207 2024_2025 25
Algorithm for the Program Factorial of a
Given Number.

• Step 1: start
• Step 2: initialize fact = 1
• Step 3: input from the user value n
• Step 4: for i=1 to i <= n repeat the process
• Step 5: fact = fact * i
• Step 6: i++ [increament i by one]
• Step 7: print fact value
• Step 8: stop
CSC207 2024_2025 26
 Now let‘s implement pseudo-code from
the above algorithm.
• Start program
• Declare fact and n
• Enter number for n
• for i=1 to i <=n
• Perform fact = fact * i
• Display fact
• End program
• By referring to the above pseudo-code, create a
program for factorial of a given number using for
loop.
CSC207 2024_2025 27
 C program
• #include <stdio.h>
• void main() {
• int n, fact=1,i;
• printf("enter value for n");
• scanf("%d",&n);
• for(i=1; i<=n; i++) {
• fact=fact*i; }
• printf("\n factorial of %d is %d", n, fact);
• }
• Output:

CSC207 2024_2025 28
 Advantages of Pseudo-Code

• It is easy to understand even a complex program

• It does not follow programming language syntax
• Programs can be easily generated by pseudo-code
• It allows us to understand the logic of a program
very quickly
• Pseudo-code can be modified easily

CSC207 2024_2025 29
 Disadvantages of Pseudo-Code
• Unlike the programs written in a particular
programming language, a pseudo-code cannot
be compiled or interpreted from which errors
cannot be identified
• As pseudo-code can be written in any order, so
it becomes difficult to understand the flow of a
program

CSC207 2024_2025 30
 Flow chart
• Flowcharts are a diagrammatic method of
representing algorithms.
• They use an intuitive scheme of showing
operations in boxes connected by lines and
arrows that graphically show the flow of control in
an algorithm.
• Standards for flowcharting indicate that the main
direction of flow is accepted as being top to
bottom and left to right.

CSC207 2024_2025 31
 Flowchart Elements
• Flowcharts are made up of the following box
types connected by lines with arrowheads
indicating the flow.

Continuation Decision Process

Subprogram Start or End

CSC207 2024_2025 32
 Programming Structures
• programming structures include
• sequence,
• selection,
• repetition
• and subprograms.
• A description of each of these structures,
together with examples of their use, follows.

CSC207 2024_2025 33
sequence, binary selection,

CSC207 2024_2025 34
Multi-way selection

CSC207 2024_2025 35
 repetition

CSC207 2024_2025 36
 [Link]
• note there is only one entry point to all the
structure and one exit point as indicated by the
dashed boxes.
• Since each structure can be thought of as a
process (as shown by the dashed boxes
containing the structure),
• more complex algorithms can be constructed
by replacing any single process by one or other
of the structures.

CSC207 2024_2025 37
 An Example Using Sequence
• Problem: Write a set of
instructions that describe how to
make a pot of tea.

Pseudocode
• BEGIN
• fill a kettle with water
• boil the water in the kettle
• put the tea leaves in the pot
• pour boiling water in the pot
• END

CSC207 2024_2025 38
 Binary selection
• Problem 2: Write a set of
instructions to follow when
approaching a set of traffic
control lights.
• Pseudocode
• IF the signal is green THEN
• proceed through the intersection
• ELSE
• stop the vehicle
• ENDIF

CSC207 2024_2025 39
 Multi-way Selection
• Problem: Write a set of instructions
that describes how to respond to all
possible signals at a set of traffic control
lights.

• Pseudocode
• CASEWHERE signal is
• red : stop the vehicle
• amber : stop the vehicle
• green : proceed through the intersection
• OTHERWISE : proceed with caution
• ENDCASE

CSC207 2024_2025 40
 Toll Gate Problem
• Problem: When operational a toll gate operates by
having a boom gate obstructing the road, and a sensor
detecting when a vehicle is present. After coins to the
value of $1.00 have been deposited in the basket, the
boom gate opens and stays open until a vehicle has gone
through.
• Amounts greater than $1.00 are accepted but no change
is given. Individual coins less than 10 cents are ignored.
• Write an algorithm to describe the control of the toll gate.

CSC207 2024_2025 41
 Pseudocode
BEGIN MAINPROGRAM • BEGIN SUBPROGRAM get the money

REPEAT • INITIALISATION

REPEAT • money collected is set to 0

wait • END INITIALISATION

• WHILE money collected is less than $1
UNTIL car has arrived
• receive coin
get the money
• IF coin is less than 10 cents THEN
open boom gate
• ignore coin
REPEAT
• ELSE
wait
• add the value of the coin to the money collected
UNTIL car has passed
• ENDIF
close boom gate • ENDWHILE
UNTIL toll gate is not operational • END SUBPROGRAM get the money
END MAINPROGRAM CSC207 2024_2025 42
 eg

CSC207 2024_2025 43
 Algorithm Design Approches
 Top-Down Approach:
 Bottom-Up Approach:

CSC207 2024_2025 44
 Top-Down Approach:
 A top-down approach starts with identifying major
components of system or program decomposing
them into their lower level components & iterating
until desired level of module complexity is achieved .
 In this we start with topmost module & incrementally
add modules that is calls.
 It takes the form of step wise procedure.
 In this solution is divided into sub task and each sub
task further divided into smallest subtask.
 The sub task are then combined into single solution.
CSC207 2024_2025 45
 Bottom-Up Approach:

 It is inverse of top down method.

 A bottom-up approach starts with designing
most basic or primitive component & proceeds
to higher level components.
 Starting from very bottom , operations that
provide layer of abstraction are implemented.
 The programmer may write code to perform
basic operations then combined those to make
a modules ,whcih are finally combined to form
overall system structure.
CSC207 2024_2025 46
 Classification of Algorithms
• There are many ways of classifying algorithms
and a few of them are shown below:
• Implementation Method
• Design Method
• Research Area
• Complexity

CSC207 2024_2025 47
 Classification by Implementation
Method
• Recursion or Iteration
• A recursive algorithm is one that calls itself
repeatedly until a base condition is satisfied.
– It is a common method used in functional programming
languages like C,C + +, etc.
• Iterative algorithms use constructs like loops and
sometimes other data structures like stacks and queues
to solve the problems.
• Some problems are suited for recursive and others are
suited for iterative.

CSC207 2024_2025 48
 Procedural or Declarative (non-
Procedural)
• In declarative programming languages, we say
what we want without having to say how to do it.
• With procedural programming, we have to specify
the exact steps to get the result.
• For example,SQL is more declarative than
procedural, because the queries don‘t specify the
steps to produce the result.
• Examples of procedural languages include: C,
PHP, and PERL.

CSC207 2024_2025 49
 Serial or Parallel or Distributed
• In general, while discussing the algorithms we assume
that computers execute one instruction at a time. These
are called serial algorithms.
• Parallel algorithms take advantage of computer
architectures to process several instructions at a time.
– They divide the problem into subproblems and serve them to
several processors or threads.
– Iterative algorithms are generally parallelizable.
• If the parallel algorithms are distributed on to different
machines then we call such algorithms distributed
algorithms.
CSC207 2024_2025 50
 Deterministic or Non-
Deterministic
• Deterministic algorithms solve the problem with
a predefined process,
• non –deterministic algorithms guess the best
solution at each step through the use of
heuristics.

CSC207 2024_2025 51
 Exact or Approximate
• As we have seen, for many problems we are
not able to find the optimal solutions.
– i.e, the algorithms for which we are able to find the
optimal solutions are called exact algorithms.
• In computer science, if we do not have the
optimal solution, we give approximation
algorithms.
• Approximation algorithms are generally
associated with NP-hard problems .

CSC207 2024_2025 52
 Classification by Design Method

• Some approaches in the design of Algorithms

include
• greedy,
• dynamic programming,
• divide and conquer, and
• branch and bound

CSC207 2024_2025 53
 Greedy algorithm
• Greedy algorithms work in stages.
• In each stage, a decision is made that is good
at that point, without bothering about the future
consequences.
• Generally, this means that some local best is
chosen.
• It assumes that the local best selection also
makes for the global optimal solution.

CSC207 2024_2025 54
 Advantages and Disadvantages
of Greedy Method
• The main advantage of the Greedy method is that
it is straightforward, easy to understand and easy
to code.
– once we make a decision, we do not have to spend
time reexamining the already computed values.
• disadvantage is that for many problems there is no
greedy algorithm.
– i.e, in many cases there is no guarantee that making
locally optimal improvements in a locally optimal
solution gives the optimal global solution.
CSC207 2024_2025 55
 Greedy Applications
• Sorting: Selection sort, Topological sort
• Priority Queues: Heap sort
• Huffman coding compression algorithm
• Prim‘s and Kruskal‘s algorithms
• Shortest path in Weighted Graph [Dijkstra‘s]
• Coin change problem
• Fractional Knapsack problem
• Disjoint sets-UNION by size and UNION by height (or rank)
• Job scheduling algorithm
• Greedy techniques can be used as an approximation algorithm
for complex problems
CSC207 2024_2025 56
 Problem-1
• Interval Scheduling Algorithm: Given a set
of n intervals S = {(starti, endj)|1 ≤ I ≤ n}. Let
us assume that we want to find a maximum
subset S′ of S such that no pair of intervals in
S′ overlaps. Check whether the following
algorithm works or not.

CSC207 2024_2025 57
Algorithm: for Problem 1

CSC207 2024_2025 58
 divide and conquer
• The D & C strategy solves a problem by:
– 1) Divide: Breaking the problem into sub problems that
are themselves smaller instances of the same type of
problem.
– 2) Recursion: Recursively solving these sub problems.
– 3) Conquer: Appropriately combining their answers.
• Examples: merge sort and binary search
algorithms.

CSC207 2024_2025 59
 Advantages of Divide and
Conquer
• Solving difficult problems: D & C is a powerful method
for solving difficult problems.
– E.g consider the Tower of Hanoi problem.
• Parallelism: Since D & C allows us to solve the
subproblems independently,
– allows for execution in multiprocessor machines, especially
shared-memory systems where the communication of data
between processors does not need to be planned in advance,
because different subproblems can be executed on different
processors.
• Memory access: D & C algorithms naturally tend to
make efficient use of memory caches.
CSC207 2024_2025 60
 Disadvantages of D & C
• One disadvantage of the D & C approach is that recursion
is slow.
– overhead of the repeated subproblem calls.
• D & C approach needs stack for storing the calls (the state
at each point in the recursion).
– depends upon the implementation style. With large enough
recursive base cases, the overhead of recursion can become
negligible for many problems.
• for some problems, it may be more complicated than an
iterative approach.
– E.g to add n numbers, a simple loop to add them up in sequence
is much easier than a D & C approach that breaks the set of
numbers into two halves, adds them recursively, and then adds
the sums.
CSC207 2024_2025 61
Divide and Conquer Applications
• Binary Search
• Merge Sort and Quick Sort
• Median Finding
• Min and Max Finding
• Matrix Multiplication
• Closest Pair problem

CSC207 2024_2025 62
 Dynamic programming (DP)
• DP and memoization work together.
• The difference between DP and divide and conquer is that
in the case of the latter there is no dependency among the
sub problems,
• whereas in DP there will be an overlap of sub-problems.
• By using memoization [maintaining a table for already
solved sub problems], DP reduces the exponential
complexity to polynomial complexity (O(n2), O(n3), etc.)
for many problems.

CSC207 2024_2025 63
 DP cont.
• The difference between dynamic programming and
recursion is in the memoization of recursive calls.
• When sub problems are independent and if there is
no repetition, memoization does not help, hence
dynamic programming is not a solution for all
problems.
• Dynamic Programming = Recursion + Memoization

CSC207 2024_2025 64
 DP Approaches
• Basically there are two approaches for solving DP
problems:
• Bottom-up dynamic programming
– we evaluate the function starting with the smallest possible
input argument value and then we step through possible
values, slowly increasing the input argument value.
• Top-down dynamic programming
– the recursive structure of the original code is preserved, but
unnecessary recalculation is avoided. The problem is broken
into sub problems, these sub problems are solved and the
solutions remembered, in case they need to be solved again.

CSC207 2024_2025 65
 Examples of DP Algorithms
• Many string algorithms including longest common
subsequence, longest increasing subsequence,
longest common substring, edit distance.
• Algorithms on graphs can be solved efficiently:
Bellman-Ford algorithm for finding the shortest
distance in a graph, Floyd‘s All-Pairs shortest
path algorithm, etc.
• Chain matrix multiplication
• Subset Sum
• 0/1 Knapsack
• Travelling salesman problem, and many more
CSC207 2024_2025 66
 Linear Programming
• In linear programming, there are inequalities in
terms of inputs and maximizing (or minimizing)
some linear function of the inputs.
• Many problems (example: maximum flow for
directed graphs) can be discussed using linear
programming.

CSC207 2024_2025 67
 Reduction [Transform and
Conquer]
• In this method we solve a difficult problem by
transforming it into a known problem for which we have
asymptotically optimal algorithms.
• The goal is to find a reducing algorithm whose complexity
is not dominated by the resulting reduced algorithms.
• For example, the selection algorithm for finding the
median in a list involves first sorting the list and then
finding out the middle element in the sorted list.
– These techniques are also called transform and conquer.

CSC207 2024_2025 68
 Classification by Research Area
• In computer science each field has its own
problems and needs efficient algorithms.
• Examples: search algorithms, sorting
algorithms, merge algorithms, numerical
algorithms, graph algorithms, string algorithms,
geometric algorithms, combinatorial algorithms,
machine learning, cryptography, parallel
algorithms, data compression algorithms,
parsing techniques, and more.

CSC207 2024_2025 69
 Classification by Complexity
• In this classification, algorithms are classified
by the time they take to find a solution based
on their input size.
• Some algorithms take linear time complexity
(O(n)) and others take exponential time, and
some never halt.
• Note that some problems may have multiple
algorithms with different complexities.

CSC207 2024_2025 70
 Randomized Algorithms
• A few algorithms make choices randomly.
• For some problems, the fastest solutions must
involve randomness.
• Example: Quick Sort.

CSC207 2024_2025 71
Branch and Bound Enumeration and
Backtracking
• These are algorithms used in Artificial
Intelligence and we do not need to explore
these fully.

CSC207 2024_2025 72
 Time complexity

 Time complexity of program / algorithm is the amount

of computer time that it needs to run to completion.
 While calculating time complexity, we develop
frequency count for all key statements which are
important.

CSC207 2024_2025 73
 eg
 Consider three algorithms given below:-
 Algorithm A:- a=a+1
 Algorithm B:- for x=1 to n step
 a=a+1
 Loop
 Algorithm C:- for x=1 to n step 1
 for y=1 to n step 2
 a=a+1
 loop
CSC207 2024_2025 74
 eg
 Frequency count for algorithm A is 1 as a=a+1
statement will execute only once.
 Frequency count for algorithm B is n as a=a+1 is a
key statement executes “n‟ times as loop runs
―n‟ times.
 Frequency count for algorithm C is n2 as a=a+1 is a
key statement executes n2 times as the inner
loop runs n times, each time the outer loop runs and
the outer loop also runs for n times.

CSC207 2024_2025 75
 Space complexity
 Space complexity of a program / algorithm is the amount of memory that
it needs to run to completion.
 The space needed by the program is the sum of the following components.
 Fixed space requirements:-
 Fixed space is not dependent on the characteristics of the input
and outputs.
 Fixed space consists of space for simple variable, fixed size
variables, etc.
 Variable space requirements:-
 Variable space includes space needed by variables whose size
depends upon the particular problem being solved, referenced
variables and the stack space required for recursion on
particular instance of variables.
 e.g. Additional space required where function uses recursion.

CSC207 2024_2025 76
 Algorithm analysis:

 There are different ways of solving problem & there

are different algorithms which can be designed to
solve a problem.
 There is difference between problem & algorithm.
 A problem has single problem statement that
describes it in general terms.
 However there are different ways to solve a problem
& some solutions may be more
efficient than others.

CSC207 2024_2025 77
 There are different types of time complexities
which can be analyzed for an algorithm:
– Best Case Time Complexity:
– Worst Case Time Complexity:
– Average Case Time Complexity:

CSC207 2024_2025 78
 Best Case Time Complexity:

 It is measure of minimum time that algorithm will

require for input of size ―n‟.
 Running time of many algorithms varies not only for
inputs of different sizes but also input of same size.
 For example in running time of some sorting
algorithms, sorting will depend on ordering of input
data. Therefore if input data of ―n‟ items is presented
in sorted order, operations performed by algorithm
will take least time.

CSC207 2024_2025 79
 Worst Case Time Complexity:

 It is measure of maximum time that algorithm will

require for input of size ―n‟.
 Therefore if various algorithms for sorting are taken
into account & say ―n‟ input data items are supplied
in reverse order for any sorting algorithm, then
algorithm will require n2 operations to perform sort
which will correspond to worst case time complexity
of algorithm.

CSC207 2024_2025 80
 Average Case Time Complexity:

 The time that an algorithm will require to execute

typical input data of size ―n‟ is known as average
case time complexity.
 We can say that value that is obtained by averaging
running time of an algorithm for all possible inputs of
size ―n‟ can determine average case time
complexity.

CSC207 2024_2025 81
 Big O notation

• Big O notation is used in Computer Science to

describe the performance or complexity of an
algorithm.
• Big O specifically describes the worst-case
scenario, and can be used to describe the execution
time required or the space used (e.g. in memory or
on disk) by an algorithm.

CSC207 2024_2025 82
• O(1)
– O(1) describes an algorithm that will always execute in the same time (or space)
regardless of the size of the input data set.
• E.g Push and POP operation for a stack
• O(N)
– O(N) describes an algorithm whose performance will grow linearly and in
direct proportion to the size of the input data set.
– Big O notation will always assume the upper limit.
• E.g. Linear search with unsorted data.
• O(N2)
– O(N2) represents an algorithm whose performance is directly proportional to the
square of the size of the input data set.
– This is common with algorithms that involve nested iterations over the data set.
• E.g. Comparing two dimensional arrays of size n.

CSC207 2024_2025 83
O(log N). Logarithmic Time
The iterative halving of data sets described in the binary search example
produces a growth curve that peaks at the beginning and slowly flattens
out as the size of the data sets increase
E.g. Binary search:
an input data set containing 10 items takes one second to
complete, a data set containing 100 items takes two seconds,
and a data set containing 1000 items will take three seconds.

O(N log N). Logarithmic Time

– E.G. More advanced sorting algorithms: quick sort,merge sort.

CSC207 2024_2025 84
CSC207 2024_2025 85
For more detail contact us