Ada Notes
All Topics (8)
- 1. Definition of Algorithm
- 2. Characteristics (Properties) of an Algorithm
- 3. Algorithm and Program Notes
- 4. Definition of Pseudocode
- 5. Comparison: Algorithm vs Pseudocode
- 6. Steps to Design an Algorithm
- 7: Algorithm Design Techniques:
- 8. Analysis Algorithm
6. Steps to Design an Algorithm
Designing an algorithm is a structured process. Here are the key steps:
1. Understand the Problem
-
Carefully read and analyze the problem.
-
Identify inputs, outputs, and the desired result.
-
Make sure the requirements are clear before proceeding.
2. Decide Computation Means & Data Structure
-
Determine how the problem will be solved:
-
Use mathematical formulas, logical operations, or iteration.
-
-
Choose the appropriate data structures: arrays, lists, trees, etc.
3. Select Algorithm Design Technique
Common techniques include:
-
Divide and Conquer
-
Greedy Method
-
Dynamic Programming
-
Brute Force / Iterative Methods
4. Design the Algorithm
-
Write the step-by-step instructions clearly.
-
Ensure clarity, finiteness, effectiveness, and correctness.
5. Prove Correctness
-
Check the algorithm logically or mathematically.
-
Make sure it produces correct output for all possible inputs.
6. Analyze the Algorithm
-
Determine efficiency:
-
Time complexity (how long it takes)
-
Space complexity (how much memory it uses)
-
-
Identify potential bottlenecks or improvements.
7. Code the Algorithm
-
Implement the algorithm in a programming language.
-
Ensure the program matches the algorithm’s logic.
-
Test with multiple inputs for correctness.
Flow Diagram: Algorithm Design Process
↓
Decide Computation Means & Data Structure
↓
Select Algorithm Design Technique
↓
Design as Algorithm
↓
Prove Correctness
↓
Analyze the Algorithm
↓
Code the Algorithm
7: Algorithm Design Techniques:
- Brute Force
- Divide and Conquer
- Greedy Technique
- Dynamic Programming
- Backtracking
- Branch & Bound
- Examples: Selection Sort, Bubble Sort, Sequential Search.
- Examples: Merge Sort, Quick Sort, Binary Search, Find max or min of list, Strassen's matrix multiplication.
- Examples:
- Knapsack problem (Fractional)
- Job sequencing with deadline
- Optimal merge patterns
- Huffman coding
- Minimum Spanning Tree (Prim's & Kruskal's algorithm)
- Single source shortest path (Dijkstra's algorithm)
- Examples:
- 0/1 Knapsack problem
- Multistage graph problem
- Floyd-Warshall algorithm (All pairs shortest path problem)
- Reliability design problem
- Examples:
- N-queen's problem
- Hamiltonian cycle
- Graph coloring problem
- Examples:
- Travelling salesperson problem
- Assignment problem
8. Analysis Algorithm
-----------------------------------
| Problem |
-----------------------------------
| | |
Algorithm1 Algorithm2 Algorithm3
| | |
Program1 program2 Program3
|
-----------------------------------------------------
|
Which Algorithm is best
For a given problem, there are many way to design algorithm for it.
→ Analysis of algorithm helps to determine which algorithm is chosen to solve the problem.
→ Analysis of algorithm or performance analysis refers to the task of determining the efficiency of an algorithm
I.e : how much computing time and storage an algorithm require to run.
To judge an algorithm, two criteria are taken in to consideration or two fundamental parameter
-
Space Complexity
-
Time Complexity
1. Space Complexity
Space complexity of an algorithm is the amount of memory it requires to run until its completion. The space needed by an algorithm has the following components:
-
Instruction Space
-
Data Space
-
Environment Space
Component Details
Instruction Space
This is the space required in a computer to store the compiled instructions of the program. It depends on factors such as:
-
Type of compiler used to compile the program.
-
Computer hardware specifications on which the algorithm runs.
Data Space
Data Space is the space required to store variables and constants. It depends on two factors:
-
Constants: Space needed for constant values (e.g., 0, 1, etc.).
-
Dynamic Objects: Space needed for objects like arrays, structures, and classes.
Stack Space
Stack Space is the space required to store information for partially executed instructions. This includes:
-
Return addresses.
-
Values of local variables.
-
Recursive function calls.
Space Complexity Formula
The total space required for a program P can be expressed as:
S(P) = C + Sp
Key:
-
S(P): Space complexity of an algorithm.
-
C: Constant space (fixed part).
-
Sp: Variable space (dependent on the specific instance/input).
The space complexity or total space needed by program is divided in to two parts.
Fixedpart ( c ) - independent variable or constants.
Variable part (Sp) - dependent variable
Example1 : Algorithm (x,y,z)
{
Return (x*y*z)+(x*y)
}
Here we have 3 independent variables x,y,z
So,
s(p) = C+Sp
= 3 + 0
S (p) = 3 Units.
Or
Each independent variable size = 4B.
So,
S(p) = 3*4
=12B.
Example 2:
Algorithm square(int a)
{
Return a*a
}
s(p) = C + Sp
=1+0
S(p) = 1*4
= 4B
Note: Nowadays space complexity is not big concern because of terminological improvement or because of improved speed and fast availability reduces the difficult of storage main concern is time.
Time Complexity
The time complexity of an algorithm is the time taken or required by an algorithm to run until its completion.
Comparison Table
Feature |
Posteriori Testing |
Priori Analysis |
|
Focus |
Program |
Algorithm |
|
Language Dependency |
Dependent on computer programming language. |
Independent of computer programming language. |
|
Hardware/OS Dependency |
Hardware/OS dependent. |
Independent of hardware and OS. |
|
Measurement |
Provides exact clock time in sec, ms, \(\mu \)s. |
Represented as a time and space function. |
Priori Analysis
In Priori analysis, the time taken by an algorithm is found prior to implementing it in any programming language. Here, time used is not in terms of seconds; instead, it represents the number of operations that are carried out while executing the algorithm.
In Priori analysis, we build an equation that relates the number of operations (steps) that a particular algorithm does to the size of input.
Once the equation of two algorithms is formed, we can then compare the rate at which the equation grows.
Example Comparison
For a given problem, consider two algorithms (A1 and A2):
-
Algorithm 1 (A1):
-
Equation: f(n) = n^2 + 200n + 5)
-
Complexity: O(n^2)
-
Algorithm 2 (A2):
-
Equation: f(n) = n^3 + 5n
-
Complexity: O(n^3)
In above equation we only consider the leading term from both the function highest polynomial will be the time complexity O(n^3).
→ O(F) notation represent the complexity of an algorithm which is also termed as asymptotic notation . here F corresponds to function whose size is same as that of input data.
→ O(F) determine in which order the response such as cpu time , memory etc . are consumed by the algorithm.
The complexity can be found in many term such as constant, logarithmic, linear quadratic, cubic, exponential etc