CSMC 204 REVIEWER

From google classroom such as marketing, finance, and

healthcare.
Introduction to algorithm
What is the need for Algorithms
An algorithm means ” A set of finite rules or
• solving complex problems
instructions to be followed in calculations or
• automate processes
other problem-solving operations ” or ” A
• perform tasks that would be difficult
procedure for solving a mathematical problem
manually
in a finite number of steps that frequently
involves recursive operations”. • optimize processes
• analyze data
• refers to a sequence of finite steps to • make predictions
solve a particular problem
Characteristics of an algorithm

Use of the algorithms

• Computer Science- Algorithms form

the basis of computer programming
and are used to solve problems
ranging from simple sorting and
searching to complex tasks such as
artificial intelligence and machine
learning.
• Mathematics - Algorithms are used to Clear and Ambiguous -The algorithm should
solve mathematical problems, such be unambiguous.
as finding the optimal solution to a
system of linear equations or finding Well-defined inputs - If an algorithm requires
the shortest path in a graph. inputs, they should be well-defined. It may or
Operations Research Artificial may not take input.
Intelligence Data Science
Well-Defined Outputs - The algorithm must
• Operation Research - Algorithms are
clearly define what output will be yielded and
used to optimize and make decisions
it should be well-defined as well002E
in fields such as transportation,
logistics, and resource allocation. Finite-ness - The algorithm must be finite, i.e.
• Artificial Intelligence - Algorithms are it should terminate after a finite time.
the foundation of artificial intelligence
Feasible - The algorithm must be simple,
and machine learning, and are used to
generic, and practical, such that it can be
develop intelligent systems that can
executed with the available resources.
perform tasks such as image
recognition, natural language Language Independent - The Algorithm
processing, and decision-making. designed must be language-independent
• Data Science - Algorithms are used to
Input - An algorithm has zero or more inputs.
analyze, process, and extract insights
from large amounts of data in fields
CSMC 204 REVIEWER

Output - An algorithm produces at least one • Hashing algorithm - Hashing algorithms work
output. similarly to the searching algorithm. But they
contain an index with a key ID. In hashing, a key
Definiteness - All instructions in an algorithm
is assigned to specific data.
must be unambiguous, precise, and easy to
interpret. • Divide and Conquer Algorithm -This
algorithm breaks a problem into sub-
Finiteness - An algorithm must terminate after
problems, solves a single sub-problem, and
a finite number of steps in all test cases.
merges the solutions to get the final solution.
Effectiveness - An algorithm must be It consists of the following steps;
developed by using very basic, simple, and
• Divide
feasible operations so that one can trace it out
• Solve
by using just paper and pencil.
• Conquer
Types of algorithms

• Brute force algorithm - It is the simplest

• Greedy Algorithm - In this type of algorithm,
approach to a problem. A brute force
the solution is built part by part. The solution
algorithm is the first approach that comes to
for the next part is built based on the
finding when we see a problem.
immediate benefit of the next part.
• Recursive algorithm - A recursive algorithm is
• Dynamic Programming Algorithm - This
based on recursion. In this case, a problem is
algorithm uses the concept of using the
broken into several sub-parts and called the
already found solution to avoid repetitive
same function again and again.
calculation of the same part of the problem. It
• Backtracking algorithm - The backtracking divides the problem into smaller overlapping
algorithm builds the solution by searching subproblems and solves them.
among all possible solutions. Using this
• Randomized Algorithm - In the randomized
algorithm, we keep on building the solution
algorithm, we use a random number so it gives
following the criteria. Whenever a solution
immediate benefit. The random number helps
fails, we trace it back to the failure point, build
in deciding the expected outcome.
on the next solution, and continue this
process till we find the solution or all possible
solutions are looked after.
Properties of an algorithm,
• Searching algorithm - Searching algorithms
are the ones that are used for searching • It should terminate after a finite time.
elements or groups of elements from a • It should produce at least one output.
particular data structure.
• It should take zero or more input.
• Sorting algorithms - Sorting is arranging a
group of data in a particular manner according • It should be deterministic means giving the
to the requirement. same output for the same input case.

• Every step in the algorithm must be effective

i.e. every step should do some work.
CSMC 204 REVIEWER

What is algorithm complexity Algorithm design and analysis

• An algorithm is defined as complex
how algorithms are properly
based on the amount of Space and
Time it consumes. designed for a specific problem
• Hence the Complexity of an algorithm
refers to the measure of the time that it
will need to execute and get the
expected output, and the Space it will
need to store all the data (input,
temporary data, and output).

Factors of Algorithm Complexity

• Time Factor: Time is measured by counting

the number of key operations such as
comparisons in the sorting algorithm.

•Space Factor: Space is measured by

counting the maximum memory
spacenrequired by the algorithm to
run/execute.

Space Complexity

The space complexity of an algorithm refers to

the amount of memory required by the
algorithm to store the variables and get the
result. Ascertaining the capabilities of a computer
Time complexity

The time complexity of an algorithm refers to

the amount of time required by the algorithm
to execute and get the result.
1. Understanding the Problem

• Problems are described in non-

technical terms.

• Key responsibility: Identify the root

cause (e.g., duplicate IDs in a
database).

• Solutions:

o Remove duplicates and

transfer unique items to a new
database.
CSMC 204 REVIEWER

o Create a new database with 5. Designing an Algorithm and Data

unique IDs and manually re- Structures
enter data.
• Linked lists are better than arrays for
2. Ascertaining the Capabilities of the dynamic list-oriented problems.
Computer
• Trade-offs: Data structure choice
• Algorithms require memory allocation depends on efficiency and memory
in RAM. constraints.

• The Random Access Machine Model: • Graph representation:

o Reads input and executes o Edge List: Best for small

step-by-step instructions. graphs.

o Uses a counter to track o Adjacency Matrix: Best when

operations based on input space is not an issue.
size.
o Adjacency List: Best for large,
o Follows rules: Simple sparse graphs.
operations take 1 timestep,
6. Methods of Specifying an Algorithm
loops count their iterations,
and memory access is free. • Pseudocode is a common method:
• Only sequential algorithms run on o // for comments
this model.
o = for assignment
3. Choosing Between Exact and
Approximate Problem Solving o == for comparison

• Exact Algorithms: Always produce an o ++ for increment

optimal solution but may be 7. Proving an Algorithm’s Correctness
inefficient.
• Empirical Analysis: Run the algorithm
• Approximation Algorithms: Faster, and check outputs.
but solutions may not be optimal.
• Formal Reasoning: Uses Proof by
4. Algorithm Design Techniques Induction:
• Brute Force: Straightforward but o Show it works for the first case.
inefficient.
o Prove that if it works for one
• Divide and Conquer: Splits a problem case, it works for the next.
into smaller subproblems, solves
them, and combines results. 8. Analyzing an Algorithm

• Greedy Algorithms: Build solutions • Efficiency: Considers time and space

step-by-step by choosing the most complexity.
beneficial option at each step. • Simplicity: Easier to understand =
easier to implement.
CSMC 204 REVIEWER

• Generality: Can the algorithm be used

for different inputs and problems?

9. Coding an Algorithm

• Challenges:

o Implementation errors can

cause inefficiencies.

o Programmer expertise affects

correctness.

• Opportunities:

o Automated testing speeds up

development.
• Time Complexity: O(n²) (Worst, Best,
o Code implementation allows and Average Case)
real-world validation.

ANALYSIS OF ALGORITHMS PART 1: Bubble Sort

BRUTE FORCE AND EXHAUSTIVE
• Compares adjacent elements and
SEARCH swaps if out of order.
Brute Force and Exhaustive Search • Optimized Bubble Sort introduces a
Selection Sort swapped flag to avoid unnecessary
iterations.
• Selects the smallest element from an
unsorted list and places it at the
beginning.

• •
CSMC 204 REVIEWER

• Time Complexity:

o O(n) (Worst and Average Case)

o O(1) (Best Case, if found in first

position)

Brute Force String Matching

• Matches characters one by one and

shifts pattern when mismatched.

• Time Complexity: O(nm) (n = text

length, m = pattern length)

• Time Complexity: O(n²) (Worst and

Average), O(n) (Best Case)

Sequential Search (Linear Search)

• Searches each element one by one

until found.

• Ordered Sequential Search stops

early if an item is greater than the
target.
• Used in DNA pattern matching, text
searching, etc.

Brute Force Algorithm Steps

1. Align pattern at the beginning of the

text.

2. Compare each character until a match

is found or a mismatch occurs.

3. Shift the pattern and repeat until all

possibilities are checked.

Brute Force Closest Pair & Convex-

Hull Problem
Closest-Pair Problem

• Finds two closest points in a set of n

points.

• Applications: Computational
geometry, clustering, database
CSMC 204 REVIEWER

management, and DNA sequence Examples:

analysis.
• 2 points → Line segment
Brute Force Approach
• 3 non-collinear points → Triangle
• Compute the Euclidean distance
• n > 2 points → Convex polygon
between all distinct pairs.
Brute Force Approach
• Identify the pair with the smallest
distance. • A segment pᵢ pⱼ is part of the hull if all
other points are on one side of its
Algorithm (Pseudocode)
defining line.
BruteForceClosestPair(P):
• Compute the equation of the line:
d←∞
o ax + by = c, where:
for i ← 1 to n-1:
▪ a = y₂ − y₁
for j ← i+1 to n:
▪ b = x₁ − x₂
d ← min(d, sqrt((xi − xj )² + (yi − yj )²))
▪ c = x₁y₂ − y₁x₂
return d
• Check the sign of ax + by − c for all
• Optimization: Instead of computing other points.
square roots, compare squared
• If all have the same sign, the segment
distances.
is part of the hull.
• Time Complexity: O(n²)
• Time Complexity: O(n³)

Convex-Hull Problem
Key Takeaways
• Finds the smallest convex polygon
• Closest Pair: Brute-force checks all
enclosing all points in a set.
pairs (O(n²)).
• Applications: Collision detection,
• Convex Hull: Checks all pairs and
path planning, accessibility maps, and
validates the remaining points (O(n³)).
outlier detection.
• These algorithms are inefficient for
Convex Set Definition
large datasets, making optimized
• A set is convex if, for any two points p methods (e.g., divide-and-conquer,
and q, the entire segment pq lies Graham scan) preferable.
within the set.

Convex Hull Definition

• Smallest convex set containing S.

CSMC 204 REVIEWER

Depth-First Search and Breadth- for each neighbor in graph[node]:

First Search if neighbor is not visited:

INTRODUCTION TO GRAPH TRAVERSAL DFS(graph, neighbor, visited)

• Graph Traversal: The process of Algorithm (Iterative DFS using Stack)

visiting all nodes (or vertices) in a
1. Initialize an empty stack.
graph.
2. Push the starting node.
• Two Fundamental Algorithms:
3. While the stack is not empty:
o Depth-First Search (DFS):
Explores as far as possible o Pop a node.
along one branch before
backtracking. o Process it if unvisited.

o Breadth-First Search (BFS): o Push its unvisited neighbors.

Explores all neighbors of a Pseudocode
node before moving to the next
level. DFS(graph, start):

• Applications: Pathfinding, web stack ← [start]

crawling, network analysis, AI, and visited ← set()
scheduling problems.
while stack is not empty:
DEPTH-FIRST SEARCH (DFS)
node ← stack.pop()
Definition
if node is not visited:
• DFS explores a graph by going deep
into one branch before backtracking. Mark node as visited

• It uses a stack (either explicit or for each neighbor in graph[node]:

recursion) to manage traversal.
if neighbor is not visited:
Algorithm (Recursive DFS)
stack.push(neighbor)
1. Start from the source node.
Time Complexity
2. Mark the node as visited.
• Adjacency List Representation:
3. Recur for all unvisited adjacent nodes. O(V+E)O(V + E)

4. Backtrack when there are no more • Adjacency Matrix Representation:

unvisited neighbors. O(V2)O(V^2)

Pseudocode • VV is the number of vertices, EE is the

number of edges.
DFS(graph, node, visited):
Applications of DFS
Mark node as visited
CSMC 204 REVIEWER

• Pathfinding & Maze Solving: DFS Time Complexity

helps in searching paths in a maze.
• Adjacency List Representation:
• Cycle Detection in Graphs: DFS can O(V+E)O(V + E)
identify cycles in a
• Adjacency Matrix Representation:
directed/undirected graph.
O(V2)O(V^2)
• Topological Sorting: Used in
Applications of BFS
scheduling problems.
• Shortest Path in an Unweighted
• Solving Puzzles: Used in solving
Graph: BFS finds the shortest path in
mazes, Sudoku, and word ladders.
an unweighted graph.
BREADTH-FIRST SEARCH (BFS)
• Network Broadcasting: Used in
Definition message spreading in computer
networks.
• BFS explores a graph level by level,
visiting all neighbors before moving to • Finding Connected Components:
the next level. Helps in identifying clusters in graphs.

• It uses a queue to manage traversal. • AI & Game Development: BFS is used

in AI for finding the shortest moves in
Algorithm
puzzles like chess and tic-tac-toe.
1. Start from the source node.
KEY DIFFERENCES BETWEEN DFS & BFS
2. Mark the node as visited.
Depth-First Breadth-First
Feature
3. Enqueue all unvisited adjacent nodes. Search (DFS) Search (BFS)
4. Dequeue and repeat until all nodes are Data Stack (or
visited. Queue
Structure recursion)
Pseudocode
Deep Broad (level-
Approach
BFS(graph, start): (backtracking) wise)

queue ← [start] Pathfinding, Shortest path,

Use Case
Topology, Cycles Networking
visited ← set()

while queue is not empty: O(V+E)O(V +

Time O(V+E)O(V + E)
E) (Adjacency
node ← queue.dequeue() Complexity (Adjacency List)
List)
if node is not visited:
Memory Low (better for High (storing
Mark node as visited Usage deep trees) levels)

for each neighbor in graph[node]:

if neighbor is not visited:

queue.enqueue(neighbor)
CSMC 204 REVIEWER

SUMMARY o Optimization Problems

(Knapsack Problem,
• DFS is useful for exploring deep
Assignment Problem)
paths, detecting cycles, and solving
puzzles. o Combinatorial Problems
(Subset Generation,
• BFS is ideal for shortest paths,
Permutations, Combinations)
network traversal, and connected
components. GRAPH PROBLEMS

• Both algorithms have a time Hamiltonian Circuit Problem

complexity of O(V+E)O(V + E).
• A Hamiltonian Circuit is a cycle that
• Choosing DFS or BFS depends on the passes through every vertex exactly
problem: once.

o Use DFS for backtracking, • In an unweighted graph, finding a

topological sorting, and cycle Hamiltonian Circuit is equivalent to
detection. solving the Traveling Salesman
Problem (TSP) for a weighted graph.
o Use BFS for shortest paths,
level-order traversal, and • Exhaustive Search Approach:
networking.
1. Select a starting vertex.
Exhaustive Search 2. Generate all permutations of
• Definition: Exhaustive search is a the remaining n−1n-1 vertices.
brute-force approach that evaluates 3. Compute the total path length
all possible solutions to find the best for each permutation.
one.
4. Choose the shortest path (if it
• Key Characteristics: exists).
o Generates all potential • Complexity Analysis:
solutions.
o Number of possible paths:
o Evaluates each solution based (n−1)!(n-1)!
on an objective function.
o Cost per path: O(n)O(n)
o Selects the optimal solution
(either minimum or maximum o Total computational cost:
value). O(n!)O(n!)

• Common Applications: o Optimization: Since the

direction can eliminate half
o Graph Problems (Hamiltonian the paths, complexity reduces
Circuit, Traveling Salesman to O(n!/2)O(n!/2).
Problem)
CSMC 204 REVIEWER

Traveling Salesman Problem (TSP) parts (not typically solved

using exhaustive search).
• Problem Statement: Given nn cities
with known distances between each • Exhaustive Search Solution:
pair, find the shortest tour that visits
o Generate all possible subsets
each city exactly once and returns to
of items.
the starting city.
o Check which subsets are
• Exhaustive Search Solution:
feasible.
o Generate all possible tours by
o Compute the value of each
permuting n−1n-1
feasible subset and select the
intermediate cities.
maximum.
o Compute the length of each
• Time Complexity: O(2n)O(2^n), since
tour.
there are 2n2^n possible subsets.
o Select the shortest tour.
• Classification: NP-hard, meaning no
• Time Complexity: O(n!)O(n!) (factorial known polynomial-time solution
growth makes exhaustive search exists.
impractical for large nn).

ASSIGNMENT PROBLEM
OPTIMIZATION PROBLEMS
Problem Definition
Knapsack Problem
• Assign nn workers to nn jobs where:
• Problem Statement: Given nn items
o Each worker has a different
with:
cost for each job (given in a
o Weights: w1,w2,...,wnw_1, cost matrix C[i,j]C[i,j]).
w_2, ..., w_n
o Each worker must be assigned
o Values: v1,v2,...,vnv_1, v_2, ..., exactly one job.
v_n
o The goal is to minimize the
o A knapsack of capacity WW, total assignment cost.
find the most valuable subset
Brute-Force Solution
such that: ∑wj≤W\sum w_j \leq
W • Generate all permutations of n!n!
possible assignments.
• Types of Knapsack Problems:
• Compute the cost for each
o 0/1 Knapsack: Each item can
permutation.
either be taken completely or
not at all. • Select the assignment with the
minimum cost.
o Fractional Knapsack: Items
can be divided into smaller
CSMC 204 REVIEWER

• Time Complexity: O(n!)O(n!) (factorial

growth is impractical for large nn).

Optimized Approach

• Hungarian Method: An algorithm

developed by Kuhn, based on works
by König and Egerváry, which solves
the assignment problem efficiently in
O(n3)O(n^3).

SUMMARY OF EXHAUSTIVE SEARCH

COMPLEXITY

Exhaustive Search
Problem
Complexity

Hamiltonian Circuit O(n!)O(n!)

Traveling Salesman
O(n!)O(n!)
(TSP)

Knapsack Problem O(2n)O(2^n)

Assignment
O(n!)O(n!)
Problem

Takeaways

• Exhaustive search guarantees the

optimal solution but is
computationally expensive.

• It is impractical for large-scale

problems due to exponential or
factorial growth.

• Alternative efficient algorithms exist

for specific problems (e.g., Hungarian
Method for assignment problems,
Dynamic Programming for
knapsack).