Faculty of Computer Applications &

Information Technology

Integrated MSc(IT)

221601705
Design and Analysis of Algorithm
Unit 1 : Basic Concepts of Analysis and
Design of Algorithms

Faculty of Computer Applications & IT

 What is an Algorithm?
●
An algorithm is a step-by-step procedure or a well-defined set of instructions
designed to perform a specific task or solve a particular problem.

Key Characteristics of an Algorithm:

●
Finiteness: The algorithm must terminate after a finite number of steps.
●
Definiteness: Each step of the algorithm must be clear and unambiguous.
●
Input: It may have zero or more inputs.
●
Output: It must produce at least one output.
●
Effectiveness: Each operation must be simple enough to be carried out in a finite
amount of time.

Faculty of Computer Applications & IT

 Examples of Algorithms:

●
Cooking Recipe: Step-by-step instructions to prepare a
dish.

●
Search Algorithm: Finding a value in a list (e.g., Linear
Search, Binary Search).

●
Sorting Algorithm: Arranging items in order (e.g., Bubble
Sort, Merge Sort).
Faculty of Computer Applications & IT
 Fundamentals of Algorithmic
Problem Solving
●
Understand the problem
●
Analyze the problem
●
Design an algorithm
●
Prove its correctness
●
Analyze time and space complexity
●
Implement the algorithm
●
Test and debug the solution
Faculty of Computer Applications & IT
 Cont.

1. Understand the Problem:

Clearly define the input and desired output.
Identify constraints and edge cases.

2. Analyze the Problem:

Determine if the problem is solvable with the known methods.
Consider time and space requirements.

3. Design an Algorithm:
Choose an appropriate strategy (brute-force, divide and conquer, greedy, dynamic
programming, etc.).
Define the steps clearly and logically.
Faculty of Computer Applications & IT
 Cont.

4. Prove the Correctness:

Ensure the algorithm gives correct results for all valid inputs.
Use mathematical proofs or rigorous testing.

5. Analyze the Algorithm:

Measure efficiency in terms of time and space complexity.
Use asymptotic notation (Big O, Omega, Theta).

6. Implement the Algorithm:

Translate the logic into a programming language.
Follow best coding practices for readability and efficiency.
Faculty of Computer Applications & IT
 Cont.

7. Test and Debug:

Use a variety of test cases (normal, boundary, and edge cases).
Identify and fix bugs or inefficiencies.

Faculty of Computer Applications & IT

 Important Problem Types

●
When designing algorithms, it's essential to
recognize the type of problem you're solving, as
different problems require different strategies.
Below are the most common and important
problem types encountered in algorithmic
problem solving:

Faculty of Computer Applications & IT

 Cont.

1. Sorting Problems
●
Objective: Arrange elements in a particular order (ascending or descending).
●
Examples: Bubble Sort, Merge Sort, Quick Sort.
●
Use Cases: Organizing data, optimizing searches, ranking systems.

2. Searching Problems
●
Objective: Find an element in a data structure.
●
Examples: Linear Search, Binary Search.
●
Use Cases: Database lookups, finding items in lists.

●
3. Graph Problems
●
Objective: Deal with relationships and connections.
●
Examples: Shortest path (Dijkstra's), Minimum spanning tree (Kruskal’s, Prim’s), DFS, BFS.
●
Use Cases: Network routing, social network analysis, maps.
Faculty of Computer Applications & IT
 Cont.

4. Dynamic Programming Problems

●
Objective: Solve problems by breaking them into overlapping subproblems and storing
results.
●
Examples: Fibonacci sequence, Knapsack problem, Longest Common Subsequence.
●
Use Cases: Optimization problems, sequence analysis.

5. Greedy Problems
●
Objective: Make the locally optimal choice at each step.
●
Examples: Activity selection, Huffman coding.
●
Use Cases: Resource allocation, compression algorithms.

6. Divide and Conquer Problems

●
Objective: Break the problem into smaller parts, solve them, and combine the results.
●
Examples: Merge Sort, Quick Sort, Binary Search.
●
Use Cases: Sorting, searching, mathematical
Faculty of Computer problems.
Applications & IT
 Cont.

7. Backtracking Problems
●
Objective: Build a solution incrementally and backtrack if needed.
●
Examples: N-Queens, Sudoku solver.
●
Use Cases: Constraint satisfaction, puzzles.

8. String Processing Problems

●
Objective: Perform operations on strings.
●
Examples: Pattern matching (KMP, Rabin-Karp), string reversal.
●
Use Cases: Text editors, search engines, bioinformatics.

Faculty of Computer Applications & IT

 Fundamental Data Structures

●
A data structure is a specialized format for
organizing, processing, and storing data so that
it can be accessed and modified efficiently.
Choosing the right data structure is critical to
designing efficient algorithms.

Faculty of Computer Applications & IT

Faculty of Computer Applications & IT
 1. Primitive Data Structures
●
Examples: Integer, Float, Character, Boolean
●
Use: Basic building blocks for more complex structures.

2. Non-Primitive Data Structures

A. Linear Data Structures

Array: Collection of elements stored in contiguous memory.

●
Fixed size, fast access by index.
●
Used in matrices, buffers.

Faculty of Computer Applications & IT

 Linked List: Elements (nodes) connected by pointers.
●
Dynamic size, easier insertion/deletion.
●
Types: Singly, Doubly, Circular.

Stack: Follows LIFO (Last-In-First-Out).

●
Operations: push, pop, peek.
●
Used in function calls, undo operations.

Faculty of Computer Applications & IT

 Queue: Follows FIFO (First-In-First-Out).
●
Types: Simple Queue, Circular Queue, Deque, Priority Queue.
●
Used in task scheduling, printers.

Faculty of Computer Applications & IT

 B. Non-Linear Data Structures
Tree: Hierarchical structure with nodes.
●
Types: Binary Tree, Binary Search Tree, AVL Tree, B-Tree.
●
Used in file systems, databases, parsing expressions.

Faculty of Computer Applications & IT

 Graph: Set of nodes (vertices) connected by edges.
●
Types: Directed/Undirected, Weighted/Unweighted.
●
Used in social networks, routing algorithms.

Faculty of Computer Applications & IT

 C. Hashing
●
Hash Table / Hash Map: Maps keys to values using a hash
function.
●
Fast access, insertion, and deletion.
●
Used in dictionaries, databases, caching.

Faculty of Computer Applications & IT

 Fundamentals of the Analysis of
Algorithm Efficiency

●
The analysis of algorithm efficiency is about evaluating how well an
algorithm performs in terms of time and space when solving a
problem. This is crucial for selecting or designing algorithms that run
faster and use fewer resources.

Faculty of Computer Applications & IT

 Types of Efficiency:

1. Time Efficiency (Time Complexity)

●
Indicates the amount of time an algorithm takes to run as a function of input size n.
●
Analyzed by counting basic operations (comparisons, assignments, etc.).
●
Expressed using asymptotic notation (e.g., O(n), O(n²)).

2. Space Efficiency (Space Complexity)

●
Refers to the amount of memory used by the algorithm.
●
Includes space for input, variables, and auxiliary structures.

Faculty of Computer Applications & IT

 Example

for i in range(n):
print(i)

●
This loop runs n times → Time Complexity: O(n)
●
Uses constant memory → Space Complexity: O(1)

Faculty of Computer Applications & IT

The Analysis Framework

Faculty of Computer Applications & IT

 1. Measuring the Input Size
●
The input size (n) is a critical factor affecting an algorithm's
performance.
●
It depends on the type of problem:
●
Sorting → number of elements
●
Matrix operations → number of rows/columns
●
Graphs → number of vertices/edges
●
Strings → length of the string

Faculty of Computer Applications & IT

 2. Units for Measuring Running Time
●
Instead of actual time (in seconds), we use:
●
Number of basic operations (comparisons, assignments, etc.)
●
This makes analysis hardware-independent

Example:
for i in range(n):
print(i)
●
Basic operation (print) runs n times → O(n)

Faculty of Computer Applications & IT

 3. Orders of Growth
●
This describes how the running time increases as input size grows:

eg.
●
O(1) - Constant time - Accessing array element
●
O(log n) - Logarithmic time - Binary search
●
O(n) - Linear time - Linear search
●
O(n log n) - Log-linear time - Merge Sort, Heap Sort
●
O(n²) - Quadratic time - Bubble Sort, Selection Sort
●
O(2ⁿ) - Exponential time - Recursive Fibonacci

These asymptotic notations help describe performance at scale.

Faculty of Computer Applications & IT
 4. Best, Worst, and Average Case Analysis

Best Case
●
Input that causes minimum running time.
●
E.g., In linear search, if the target is the first element → O(1)

Worst Case
●
Input that causes maximum running time.
●
E.g., In linear search, if the target is the last element or not present → O(n)

Average Case
●
Expected running time over all possible inputs.
●
Requires mathematical modeling or probability analysis.
●
Often close to the worst case for most problems
Faculty of Computer Applications & IT
 Asymptotic Notations
Big-O Notation (O)
●
Represents the worst-case upper bound of an algorithm.
●
Describes the maximum time an algorithm can take.
●
Ensures that the algorithm won’t take longer than this time for large inputs.

Example:
●
Linear Search: O(n)
●
Bubble Sort: O(n²)

Faculty of Computer Applications & IT

 Omega Notation (Ω)
●
Represents the best-case lower bound.
●
Describes the minimum time an algorithm takes for the most
favorable input.

Example:
●
Linear Search: Ω(1) (if the target is at the beginning)

Faculty of Computer Applications & IT

 Theta Notation (Θ)
●
Represents the tight bound (both upper and lower).
●
Indicates that the algorithm always takes approximately this
time.

Example:
●
Merge Sort: Θ(n log n)

Faculty of Computer Applications & IT

Basic Efficiency Classes

Faculty of Computer Applications & IT

Mathematical Analysis of Non-Recursive
Algorithms

The mathematical analysis of non-recursive algorithms

focuses on determining the time complexity by
counting the number of times the basic operations are
executed. These algorithms follow a sequential, loop-
based structure without calling themselves.

Faculty of Computer Applications & IT

 General Steps in the Analysis:

Identify the Input Size (n):

●
Depends on the problem (array size, number of elements, etc.).

Identify the Basic Operation:

●
The most frequently executed or most time-consuming operation (e.g., comparisons,
assignments).

Count the Number of Times the Basic Operation Executes:

●
Analyze loops and nested loops.
●
Use summation formulas to compute total counts.

Express Time Complexity T(n):

●
Use functions and simplify using asymptotic notation (Big-O, Θ, etc.)
Faculty of Computer Applications & IT
 Common Loop Analysis Patterns
1. Single Loop Example

for i in range(n):
print(i)

●
Runs n times
●
T(n) = n ⇒ O(n)
Faculty of Computer Applications & IT
 2. Nested Loop Example

for i in range(n):
for j in range(n):
print(i, j)

●
Inner loop runs n times for each outer iteration (n × n)
●
T(n) = n² ⇒ O(n²)
Faculty of Computer Applications & IT
 3. Uneven Nested Loop

for i in range(n):
for j in range(i):
print(i, j)

●
Inner loop runs i times for each i
●
Total operations:
●
T(n) = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2
●
⇒ T(n) = O(n²)
Faculty of Computer Applications & IT
 4. Logarithmic Growth

i=1
while i < n:
print(i)
I *= 2

●
i doubles each time ⇒ runs log₂n times
●
T(n) = O(log n)

Faculty of Computer Applications & IT

 Empirical Analysis of Algorithms
●
Empirical analysis involves evaluating the performance of
an algorithm by implementing and executing it on real
inputs and recording the actual running time and resource
usage. Unlike mathematical analysis, which is theoretical,
empirical analysis is experimental and data-driven.

Faculty of Computer Applications & IT

 Key points
●
Measure the actual performance of algorithms in practice.
●
Compare algorithms beyond theoretical complexity.
●
Validate or challenge theoretical predictions.
●
Analyze the impact of constants, hidden terms, or practical
input sizes.

Faculty of Computer Applications & IT

 Steps in Empirical Analysis:
1. Implement the Algorithm
●
Code the algorithm in a programming language (Python, Java, C++, etc.).
●
Ensure correct and optimized implementation.

2. Prepare Test Cases

●
Use varied input sizes (e.g., 100, 1,000, 10,000).
●
Include different input types:
– Best-case
– Worst-case
– Average/random-case

Faculty of Computer Applications & IT

 3. Measure Performance
●
Use tools like:
– time module in Python
– System.nanoTime() in Java
– Profilers (e.g., cProfile, valgrind, IDE profilers)
●
Measure:
Execution time
Memory usage
CPU usage

4. Analyze and Plot Results

●
Plot input size (x-axis) vs. execution time (y-axis).
●
Compare the growth rate with theoretical Big-O predictions.
●
Tools: Excel, Python (matplotlib), Google Sheets, etc.
Faculty of Computer Applications & IT
 5. Draw Conclusions
●
Identify crossover points where one algorithm becomes better than
another.
●
Observe real-world limitations (cache usage, recursion depth, IO
bottlenecks).
●
Decide which algorithm is better in practice, not just theory.

Faculty of Computer Applications & IT

 Example

Faculty of Computer Applications & IT

 Algorithm Visualization
●
Algorithm visualization refers to the graphical
representation of an algorithm’s steps, operations, or
data structures in action. It helps in understanding,
teaching, debugging, and analyzing algorithms
effectively.

Faculty of Computer Applications & IT

 Key Points
●
Improves understanding of how an algorithm works step-by-
step
●
Aids teaching and learning in classrooms or tutorials
●
Helps debugging by showing real-time operations
●
Reveals performance characteristics like comparisons and
swaps
●
Clarifies dynamic behavior (like recursion, memory use, etc.)

Faculty of Computer Applications & IT

 Types of Algorithm Visualizations:
1. Data Structure Visualization
●
Shows dynamic changes in arrays, stacks, queues, linked lists, trees, graphs, etc.
●
Example: Insertion into a binary search tree (BST), traversals.
●
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
●
https://visualgo.net/en/list
●
https://algorithm-visualizer.org/

2. Control Flow Visualization

●
Highlights the path of execution: loops, conditionals, recursive calls.
●
https://pythontutor.com/
Faculty of Computer Applications & IT
 3. Sorting Algorithm Visualization
●
Common in education:
●
Bubble Sort: Show adjacent swaps
●
Merge Sort: Show divide and merge steps
●
Quick Sort: Show pivoting and partitioning
●
https://visualgo.net/en/sorting
●
https://algorithm-visualizer.org/

Faculty of Computer Applications & IT

 4. Graph Algorithm Visualization

What it shows:
●
Step-by-step execution of graph algorithms, including visited nodes, queue/stack usage,
and path tracing.
Examples:
●
BFS / DFS
●
Dijkstra’s Algorithm
●
Kruskal’s and Prim’s MST
●
A* pathfinding
●
https://graphonline.top/en/
●
https://qiao.github.io/PathFinding.js/visual/
●
https://visualgo.net/en/graphds
Faculty of Computer Applications & IT
Thank You

Faculty of Computer Applications & IT