Important Types of Problems Searching Problem
Types of Problems in Designing and Analyzing – finding a given value called the “search key”
Algorithms in a given list or set.
● Sorting Problem – Searching Algorithm are necessary for
storing and retrieving information from large
● Searching Problem
databases.
● String Processing Problem
● Linear search – examines a sequence of
● Graph Problem data objects one by one.
● Combinatorial problems
● Geometrical problems
● Numerical problems
Sorting Problem
– rearrange the items of a given list in
ascending order
● Binary search – more sophisticated strategy
and is faster than linear search when searching
a large array.
String Processing Problem
– deals with non-numerical data that intensifies
the interest of researchers and computing
practitioners in string-handling algorithms.
– A string is a sequence of characters from an
alphabet.
● Text strings – comprise letters, numbers,
and special characters.
● Bit strings – comprise zeros and ones.
● Gene sequences – can be modeled by The following graph can be represented as
strings of characters from the four-character G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C),
alphabet {A, C, G, T}. (C, A)})
● Breadth First Search (BFS) – is a
traversing algorithm where one should start
traversing from a selected node (source or
starting node)
● Depth First Search (DFS) – is a recursive
algorithm that uses the idea of backtracking.
The word “backtrack” means that when
one is moving forward, and there are no
more nodes along the current path, s/he
moves back on the same path to find
nodes to traverse.
Graph Problem
– It deals with objects and their connections
like determining whether all of the locations are
connected.
It is also useful for real-life applications:
● Transportation ● Project scheduling
● Communication ● Games
Combinatorial problems
● Social and economic networks – to find a combination of an object such as
permutation, combination, or a subset that
satisfies certain constraints
Basic Graph Algorithms
● Traveling Salesman Problem (TSP)
● Graph-traversal algorithms – It deals with
how one can reach all the points in a network.
– It deals with finding the shortest tour through
𝑛𝑛 cities that visits every city exactly once.
Examples: Route planning, Circuit board, etc.
Analysis of an Algorithm
● Graph-coloring problem
– means to investigate an algorithm’s efficiency
– It deals with assigning the smallest number with respect to resources:
of colors to the vertices of a graph so that no ￮ running time (time efficiency) and memory
two (2) adjacent vertices are the same color. space (space efficiency)
Example: Event scheduling – If the events are ￮ Time being more critical than space
represented by vertices that are connected by
an edge
STEPS:
￮ Implement the algorithm completely.
￮ Determine the time required for each basic
operation.
￮ Identify unknown quantities that can be used
to describe the frequency of execution of the
basic operations.
￮ Develop a realistic model for the input to the
Geometrical problems program.
– It deals with geometric objects such as ￮ Analyze the unknown quantities, assuming
points, lines, and polygons. the modelled input.
Two (2) Classic Problems of Computational ￮ Calculate the total running time by
Geometry multiplying the time by the frequency for each
operation, then adding all the products.
● Closest-pair problem – is self-explanatory;
given 𝑛𝑛 points in the plane, find the closest
pair among them. What is an efficient algorithm?
● Convex-hull problem – asks to find the ￮ Efficiency – signifies a level of performance
smallest convex polygon that would include all that describes using the least amount of input
the points of a given set. to achieve the highest amount of output.
Numerical problems ￮ Efficiency – requires reducing the amount of
– involves mathematical objects of continuous unnecessary resources used to produce a
given output
nature such as solving equations, system
equations, computing definite integrals, ￮ It is a measurable concept that can be
evaluating functions, etc. determined using the ratio of useful output to
total input.
￮ An algorithm is considered efficient if it runs
in a reasonable amount of time on specified
space limits and not overload the memory.
● The space efficiency (aka space
complexity) – defined as the amount of
￮ In performing analysis of an algorithm based
computer space or memory required by an
algorithm on its space complexity, only data space is
considered; the instruction space as well as
● The memory space we consider is the the environmental stack is ignored.
space of primary memory.
How to Calculate the Space Complexity?
Theoretical Analysis: It uses a high-level
description of the algorithm instead of an
implementation. Can be used for analyzing
any algorithm
Framework for Analysis
￮ Instruction space – whether there are
sufficient memory available to run program.
￮ Data space – If the program is to run on multi
user system, it may be required to specify
amount of memory to be allocated to the
program.
￮ Run-time stack space/Environmental
Stack –There may be several possible
solutions with different space requirements.
￮ In performing analysis of an algorithm based
on its time complexity, only input data is
considered; the remaining things are ignored
as they are machine dependent.
￮ To calculate the time complexity of an
algorithm, we need to define a model machine.
It is a Single processor machine
It is a 32 bit Operating System machine
It performs sequential execution
It requires 1 unit of time for Arithmetic
and Logical operations
It requires 1 unit of time for
Assignment and Return value
It requires 1 unit of time for Read and
Write operations
Time Efficiency or Complexity
￮ T(n) – It is the amount of computer time
required by each operation to execute.
￮ Cop – It is the amount of computer time Worst-case, Best-case, Average case
required for a single operation in each line. efficiencies
￮ Algorithm efficiency depends on the input
Comments = 0 step
size n. And for some algorithms efficiency
Assignment statement does not
depends on type of input.
involve any calls to other algorithms = 1
step Best, Worst & Average case efficiencies.
Condition statement = 1 step ￮ Worst-case efficiency: Efficiency (number of
￮ C(n) – It is the amount of computer time times the basic operation will be executed) for
the worst case input of size n.
required by each operation for all its
repetitions. ￮ The algorithm runs the longest among
all possible inputs of size n.
Loop condition for n times = n + 1
steps ￮ Best-case efficiency: Efficiency (number of
Body of loop = n steps times the basic operation will be executed) for
the best case input of size n.
￮ The algorithm runs the fastest among
all possible inputs of size n.
￮ Average-case efficiency: Average time taken
(number of times the basic operation will be
executed) to solve all the possible instances
(random) of the input.
How to Calculate the Time Complexity?
