Data Structures
- A data structure is a logical method of representing data in memory.
- Data structure is strictly described as an instance of an Abstract Data Type (ADT).
- An Abstract Data Type is defined as a mathematical model of a user-defined type along with the operations performed on that model.
| Data Structure | Strengths | Weaknesses |
| Array | Fast access if index is known | Slow search, fixed size |
| Stack | Features last in – first out access | Slow access to other elements |
| Queue | Features first in – first out access | Slow access to other elements |
| Linked list | Quick insertion and deletion | Slow search |
| Binary tree | Quick insertion, deletion and search when tree is balanced | Deletion procedure is complex |
| Hash table | Fast insertion and access if key is known | Inefficient memory usage, slow access if key is not known |
| Heap | Fast insertion, deletion and access to largest element | Slow access to other elements |
| Graph | Simulates real world problems | Some algorithms are slow and complex |
Algorithm
An algorithm can be described as sequence of steps or instructions required to solve a given problem.
It is a finite set of instructions written to accomplish a particular task.
When designing an algorithm, one must ensure that the
algorithm adheres to the following criteria:
Input: Some input data (can be empty in some cases) externally supplied to the algorithm
Output: At least one output is produced
Finiteness: The algorithm must terminate after finite number of steps
Definiteness: The instructions must be clear and unambiguous
Effectiveness: Every instruction must be basic enough to be carried out on paper
Following are certain points to be considered
while writing an algorithm :
Representing an algorithm.
Designing an algorithm.
Analyzing an algorithm.
Algorithm Analysis
Algorithm Analysis involves comparing different algorithms written for a specific problem. All the algorithms are compared for their space and time complexities.
Space complexity: It refers to the amount of storage the algorithm consumes.
Time complexity: It is the time required by the algorithm for execution.
Following are the different types of time complexities:
Best-case time complexity: It is the measure of minimum time required for an algorithm to execute for a known input size.
Average case time complexity: Average time complexity is the measure of time an algorithm will require to execute, for a typical input data size. This method requires statistical calculations.
Worst-case time complexity: It is the measure of maximum time required for an algorithm to execute for a known input size.
