Tutorial Flashcards
What is DS?
- It’s a way of storing and organizing data in a computer so that I can be used efficiently.
- Set of Algorithms which can be used in programming to organise the data in memory
Types of DS?
Types of Data structure
1.Primitive DS
-Primitive Data types such as int,char,double,float
which can hold a single value
2.Non primitive DS
-Two types
a)Linear Data structure
b)Non-Linear Data StructureWhat is Linear and Non-Linear Data structure?
- Linear Data structure
- Arrangement of Data in a sequential order
- Eg: Arrays,Stacks,Queues,etc - Non-Linear Data structure
- Arrangement of Data in a random order
- Eg: Trees and Graphs
Data structures can also be classified as?
Data structures can also be classified as:
- Static data structure
- The size is allocated during the compile time so the size is fixed - Dynamic data structure
- The size is allocated during the run time so the size is flexible
What is ADT?
- Abstract Data type tells us what has to be done which is a blueprint and Data structures provides us how it has be done with the implementation
- Examples: Stack,Queues,Linked List,etc
Advantages of DS?
- Efficiency
- Reusability
- Abstraction
What is an Algorithm?
An algorithm is a process or a set of rules required to perform calculations or some other problem-solving operations especially by a computer.
Characteristics of an Algorithm
Characteristics of an Algorithm is
- Input
- Output
- Unambiguity-Clear and Simple
- Finiteness-Set of instructions must be limited
- Effectiveness-Should be effective
- Program independent-Should work on all platforms
Dataflow of an Algorithm
Problem-Identifying the problem,so that an algo can be created
|
Algorithm-Set of instructions to solve the problem
|
Input- Receiving the input
|
Processing Unit-Place where the algorithms and input work to bring a solution
|
Output- Receiving the output
Why do we need Algorithms?
- Scalability-Large Algorithms can be scaled down to small-small steps
- Performance-These small-small steps makes solving the problem feasible
Importance of Algorithms?
Theoretical importance: When any real-world problem is given to us and we break the problem into small-small modules. To break down the problem, we should know all the theoretical aspects.
Practical importance: As we know that theory cannot be completed without the practical implementation. So, the importance of algorithm can be considered as both theoretical and practical.
Algorithm Analysis
The algorithm can be analyzed in two levels, i.e., first is before creating the algorithm, and second is after creating the algorithm.
- Priori Analysis-the theoretical analysis of an algorithm which is done before implementing the algorithm.
- Posterior Analysis-a practical analysis of an algorithm. The practical analysis is achieved by implementing the algorithm using any programming language. This analysis basically evaluate that how much running time and space taken by the algorithm.
Algorithm Complexity
1.Time complexity : Amount of time required to run an algorithm.Represented by big O notation.
The time complexity is mainly calculated by counting the number of steps to finish the execution.
2.Space complexity: Amount of space required to solve a problem and produce an output.Represented by big O notation.
Space complexity = Auxiliary space( The extra space required by the algorithm) + Input size.
Asymptotic Notations
- Big oh Notation (O)-
a) Worst case scenario
b) Big O notation is an asymptotic notation that measures the performance of an algorithm by simply providing the order of growth of the function.
c) Represents the Upper bound of an Algorithm - Omega Notation (Ω)
a) Best case scenario
b) It measures the best amount of time an algorithm can possibly take to complete.It determines what is the fastest time that an algorithm can run.
c) Represents the Lower bound of an Algorithm - Theta Notation (θ)
a) Average or Realistic case scenario
b) Big theta is mainly used when the value of worst-case and the best-case is same.
c) It is the formal way to express both the upper bound and lower bound of an algorithm running time.
Pointer
-Points the address of the value stored anywhere in the computer
-Obtaining the value stored in the pointer is known as dereferencing the Pointer
Pointer improves the performance for repetitive process such as:
Traversing String
Lookup Tables
Control Tables
Tree Structures
