DSA Unit 3, 4, 5 Flashcards
Define spanning tree
subset of graph G where vertices connected using minimum possible number of edges
Justification of Array|Linked
Space efficiency (array could have many unused indices)
Dynamic size (adding or removing nodes frequently)
Traversal flexibility (without worrying about structure of array )
Advantages and disadvantages of TBT
Efficient traversal
Space utilization
No stack Overhead
Faster Access
complex implementation
increased memory usage for every node
Applications of MST
Image processing
Network design
Game development
Electric circuit
Define Stack
Linear abstract data structure
LIFO principle
Types of stack
Implicit - not implemented by user
Explicit - user implemented
Stack Operations
Push
Pop
Peek
isFull
isEmpty
display
Define Queue
Linear abstract data structure
FIFO principle
Types of Queue
Simple
Circular
Priority Queue (Ascending and Descending)
Define Graph
Non Linear Data structure using vertices (fundamental units) and edges (connections)
Operations on Graph
Insert, Delete, Search, and Traverse
Graph traversal methods
BFS (2 queues: Neighbour and Visited)
DFS (adjacent visits)
Kruskal and Prim time complexity
O( |E|log|E| )
Greedy Algorithm
paradigm that builds a solution by choosing pieces with greed (immediate benefit)
Define Tree
Tree is a hierarchical data sturcture where data arranged in multiple levels
Height and Depth
Depth - Root to node distance
Height - (Longest) Node to Lead distance
Types of Binary Tree
Full (0 or 2 children)
Degenerate (1 child)
Skewed (only lefts or rights)
Complete (all levels filled except last)
Perfect (leaves at same level)
Sequential Tree
Minimum information required to reconstruct a tree (no pointers)
Tree traversal methods
Pre order - root - left - right
In order - left - root - right
Post order - left - right - root
BFS - level wise
Huffmann Tree
according to frequency of nodes (highest - up, lowest - down)
Threaded binary tree
Empty child nodes replaced with threads
What is ADT
An ADT defines the interface or the contract of a data structure, specifying what operations can be performed on it, without specifying how those operations are implemented.
Applications of Stack
Infix to Postfix/Prefix conversions
Reverse a string
Decimal to Binary conversions
Simulate recursion
What is AVL and its time complexity?
AVL (Adelson Velsky and Landis)
self balancing binary tree which balances every time insertion or deletion occurs.
Time complexity : O(log n)