Session 01 Flashcards
What is Data Structure?
- A way of organizing and storing data in a computer so that it can be accessed and modified efficiently.
- The collection of elements and all the possible operations which are required for those set of elements.
2 types/categories of data structure?
- Primitive DS
- Non-primitive DS
Primitive DS?
- Single values, such as numbers, characters.
Int
Float
Double
Non-primitive DS?
- Allow us to store multiple data type values.
Linear DS:
1. Array
2. Linked list
3. Queue
4. Stack
Non-linear DS:
1. Tree
2. Graphs
Differences between Primitive and Non-primitive data types?
Primitive:
1) Basic data types provided by a programming language.
2) Memory Allocated on the stack.
3) Size is fixed and predefined by the language.
4) Store single values.
5) Limited to basic arithmetic and logical operations.
6) Have default values (such as 0 for int, false for Boolean)
7) Generally, more efficient in terms of memory and performance.
8) It can be access directly through their variable names.
9) Used for representing simple values and performing basic operations.
Non-primitive:
1) Complex data structures that are built using primitive data types.
2) Typically, memory allocated on the heap.
3) Size is dynamic and vary during runtime.
4) Store multiple and complex sets of data.
5) Support a wide range of operations specific to the data structure.
6) Usually, initialize to null or require explicit initialization.
7) It can be less efficient due to additional memory and overhead.
8) It may require special methods or operations to access or manipulate.
9) Used for organizing and managing data in more complex ways.
Difference between linear and nonlinear data structure?
Linear:
- Data elements are arranged in linear order where each elements is attached to its previous and next adjacent.
- Single level is involved.
- Easy implementation
- Data elements can be traversed in a single run only.
- Memory is not utilized in an efficient way.
Non-linear:
- Data elements are attached in hierarchically manner.
- Multiple levels are involved.
- Complex implementation
- Data elements can’t be traversed in a single run only.
- Memory is utilized in an efficient way
What is Abstract Data Structure (ADT)?
A data structure that defines the type of data stored, the operations allowed on it, and the behavior of these operations, without specifying it’s implementation.
Abstraction ?
the process of providing only the essentials and hiding the details.
ADT Operations ?
- Create
- Display
- Insertion
- Deletion
- Modification
What is an algorithms?
Set of rules or instructions to be followed to perform an operation on different data structures.
What is Running time analysis?
Process of determining how processing time(running time) increases as the size of the problem(input size) increases.
Rate of Growth
Asymptotic notation?
Used to describe the growth rate of functions.
Analyze how the performance of an algorithm changes as the size of the input increases.
Types of Asymptotic Notation?
- BIg Oh (O)
- Big Omega
- Big Theta
Big Oh
O(f(n))
Upper bound, Worst case time complexity.
If an algorithm has time complexity of O(n^2), it means the running time growth at most quadratically as the input size n increases.
Definition of BIg O notation?
f(n) = O(g(n))
if f(n) <= c.g(n)
for all values of n where n > n(note) and c and n(note) are constants.
Big Omega
Lower bound, Best case time complexity
Big Omega definition
f(n) = Big Omega(g(n))
iff f(n) >= c.g(n) > 0
for some c > 0 and for all n >= n(note)
c and n(note) are constants.
Big Theta
Upper and Lower bound, Worst case and Best case
Big Thete definition
f(n) = Theta(g(n))
iff c1.g(n) <= f(n) <= c2.g(n)
for all values of n where n >= n(note) and c1, c2 and n(note) are constants.
