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)
Time complexity for heap sort
O(n log n)
Heap creation O(n)
Heapify O(nlogn)
Time complexity for deleting a record from index sequential file
Best-case time complexity: O(log n) when the index is highly efficient and the record is located near the beginning of the file.
Average-case time complexity: O(n) due to the sequential search and shifting of records.
Worst-case time complexity: O(n) when the record is located at the end of the file and all records need to be shifted.
Time complexities of priority queue operations
LL
Insertion/Deletion =
O(1), O(n)
Peek =
O(1)
Array
Insertion/Deletion =
O(n)
Peek =
O(1)
Applications of infix to postfix
Make it easier for the computer to understand
Computer cannot easily differenciate between parethesis and operators
Applications of Queue
Print Line Documents
Analysis of Traffic
Telephone Operators
Operating system task scheduling
Time complexity for insertion and deletion in BST
Insertion:
Tree is empty O(1)
Tree is balanced O(logn)
Tree is skewed O(n)
O(logn)-O(n)
Deletion:
Node has no children O(1)
Tree is balanced O(logn)
Tree is skewed O(n)
Hash Function methods
Dividing (divide by prime)
Mid Square (Square the key, mid digits)
Folding (divide into equal parts, sum, then modulo)
Perfect hashing (no two hash values are same)
Collision resolution
Seperate chaining (Open Hashing)
Open Addressing (Closed hashing)
- Linear probing
- Quadratic probing
- Double Hashing
Applications of Topological Sort
Job Scheduling: Topological sorting schedules jobs based on dependencies.
Shortest Paths: Topological sorting finds shortest paths. (Network Analysis)
Process Scheduling: Topological sorting schedules processes. (OS)
Risk Analysis: Topological sorting analyzes risks.
Applications of Heap
Job Scheduling: Heaps are used to schedule jobs based on priority. (PQ)
Heap Sort: Heapsort is a comparison-based sorting algorithm using heaps
Dijkstra’s Algorithm: Heaps are used to find the shortest path in a graph.
Memory Allocation: Heaps manage memory allocation, ensuring efficient use.
Characteristics of a good Hash Function
Deterministic - Given a specific input, the hash function always returns the same output.
Low Collision Rate - The hash function should minimize collisions
Non-Injective - Multiple input values can produce the same output hash value.
Fixed Output Size - The output of the hash function is always of a fixed size.
