CEC223/SWE116 Introduction to

Algorithms and Complexity

Lecture notes for 2023/2024 Academic Year

Course instructors : Nyanga Bernard Y.
College of Technology; University of Buea &
Covenant University Institute (CUINS), Buea
 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.)

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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
CEC223/SWE116 2023_2024 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;

CEC223/SWE116 2023_2024 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?

CEC223/SWE116 2023_2024 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).

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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].
CEC223/SWE116 2023_2024 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).
CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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 ideasCEC223/SWE116
[as algorithms].
2023_2024 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 inCEC223/SWE116
a compiler.2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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 the measuring
CEC223/SWE116 number s in18S from the remaining
2023_2024
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.
CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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;
CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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
CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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
CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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:

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 33
sequence, binary selection,

CEC223/SWE116 2023_2024 34
Multi-way selection

CEC223/SWE116 2023_2024 35
 repetition

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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 CEC223/SWE116 2023_2024 42
 eg

CEC223/SWE116 2023_2024 43
 Algorithm Design Approches
 Top-Down Approach:
 Bottom-Up Approach:

CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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 .

CEC223/SWE116 2023_2024 52
 Classification by Design Method

• Some approaches in the design of Algorithms

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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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
CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 57
Algorithm: for Problem 1

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 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.
CEC223/SWE116 2023_2024 61
Divide and Conquer Applications
• Binary Search
• Merge Sort and Quick Sort
• Median Finding
• Min and Max Finding
• Matrix Multiplication
• Closest Pair problem

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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
CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 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.

CEC223/SWE116 2023_2024 70
 Randomized Algorithms
• A few algorithms make choices randomly.
• For some problems, the fastest solutions must
involve randomness.
• Example: Quick Sort.

CEC223/SWE116 2023_2024 71
Branch and Bound Enumeration and
Backtracking
• These are algorithms used in Artificial
Intelligence and we do not need to explore
these fully.

CEC223/SWE116 2023_2024 72