Introduction to Algorithm
Algorithms are step-by-step procedures or formulas for solving a specific problem.
They are fundamental to computer science and form the basis of most software systems.
Algorithm
Definition: An algorithm is a finite sequence of well-defined instructions, typically to solve
a class of problems or perform a computation.
Structures and Properties of Algorithms
1. Input: Algorithms must have specified input(s).
2. Output: Algorithms must have at least one output.
3. Definiteness: Each step of the algorithm must be precisely defined.
4. Finiteness: Algorithms must terminate after a finite number of steps.
5. Effectiveness: Steps must be simple enough to be executed by a person with pen and
paper.
Efficiency of Algorithms
The efficiency of an algorithm is evaluated based on:
1. Time Complexity: How the runtime grows as the input size increases.
2. Space Complexity: The amount of memory required by the algorithm during execution.
Asymptotic Notations
Asymptotic notations are mathematical tools to represent the time complexity of
algorithms. Common notations include:
1. Big O (O): Upper bound of time complexity.
2. Theta (Θ): Tight bound of time complexity.
3. Omega (Ω): Lower bound of time complexity.
Comparison of Asymptotic Notations
Notation Description Focus Example
Big O (O) Upper bound (worst case) Maximum time/space O(n2) for Bubble Sort
Theta (Θ) Tight bound (average case) Average time/space Θ(n) for Linear Search
Omega (Ω) Lower bound (best case) Minimum time/space Ω((n log n) for Merge Sort
Data Structure
Definition: A data structure is a particular way of organizing and storing data in a
computer so that it can be accessed and modified efficiently.
Classification of Data Structures
1. Linear Data Structures: Data is arranged in a sequential manner. Examples: Arrays,
Linked Lists, Stacks, Queues.
2. Non-Linear Data Structures: Data is arranged in a hierarchical manner. Examples: Trees,
Graphs.
3. Static Data Structures: Memory allocation is fixed. Example: Arrays.
4. Dynamic Data Structures: Memory allocation is dynamic. Example: Linked Lists.
Array
Definition: An array is a collection of items stored at contiguous memory locations.
Representation: Arrays are represented by specifying the size and type of elements.
Operations: Common operations include insertion, deletion, traversal, searching, and
updating.
Applications: Sparse Matrices
Sparse Matrices: These are matrices in which most of the elements are zero.
Applications:
1. Representing connectivity in graphs.
2. Image processing.
3. Efficient storage and manipulation of large datasets with many zero elements.
