Scribd
Upload
3 views8 pages

DAA Algorithms

The document outlines various data structures and algorithms, detailing their uses, applications, and drawbacks. It covers search algorithms like Linear and Binary Search, sorting algorithms such as Bubble and Merge Sort, and graph algorithms including DFS and Dijkstra. Additionally, it discusses optimization techniques like Dynamic Programming and Greedy Algorithms, highlighting their complexities and specific scenarios where they are applicable.

Uploaded by

dojha9900
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views8 pages

DAA Algorithms

The document outlines various data structures and algorithms, detailing their uses, applications, and drawbacks. It covers search algorithms like Linear and Binary Search, sorting algorithms such as Bubble and Merge Sort, and graph algorithms including DFS and Dijkstra. Additionally, it discusses optimization techniques like Dynamic Programming and Greedy Algorithms, highlighting their complexities and specific scenarios where they are applicable.

Uploaded by

dojha9900
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DAA Algorithms — Uses, Applications & Drawbacks

1️⃣ Linear Search


Use
 Searches element one by one.
Applications
 Small datasets
 Unsorted arrays
Drawbacks
 Slow for large data
 Worst case:O(n)

2️⃣ Binary Search


Use
 Searches in sorted array.
Applications
 Searching in databases
 Dictionary searching
Drawbacks
 Array must be sorted
 Cannot work efficiently on linked list
Complexity:O(log ⁡n)

3️⃣ Bubble Sort


Use
 Repeatedly swaps adjacent elements.
Applications
 Educational purpose
 Small datasets
Drawbacks
 Very slow
 Not suitable for large data

Complexity:O(n 2)
4️⃣ Selection Sort
Use
 Finds minimum element repeatedly.
Applications
 Small arrays
 Memory-constrained systems
Drawbacks
 Slow
 Performs unnecessary comparisons

Complexity:O(n 2)

5️⃣ Insertion Sort


Use
 Inserts element at correct position.
Applications
 Nearly sorted arrays
 Small datasets
Drawbacks
 Slow for large datasets

Complexity:O(n 2)

6️⃣ Merge Sort


Use
 Divide and Conquer sorting.
Applications
 External sorting
 Large datasets
 Linked lists
Drawbacks
 Requires extra memory
Complexity:O(n log ⁡n)
7️⃣ Quick Sort
Use
 Pivot-based sorting.
Applications
 Fast internal sorting
 Real-world libraries
Drawbacks
 Worst case is poor
 Recursive overhead
Average:O(n log ⁡n)

Worst:O(n 2)

8️⃣ DFS (Depth First Search)


Use
 Traverses graph deeply.
Applications
 Cycle detection
 Maze solving
 Topological sorting
Drawbacks
 May not find shortest path
 Can get trapped deep
Complexity:O(V + E)

9️⃣ BFS (Breadth First Search)


Use
 Traverses graph level by level.
Applications
 Shortest path in unweighted graph
 Social networks
 Web crawling
Drawbacks
 Requires more memory
 Slow on huge graphs
Complexity:O(V + E)

🔟 Dijkstra Algorithm
Use
 Finds shortest path.
Applications
 GPS navigation
 Network routing
Drawbacks
 Cannot handle negative weights

1️⃣1️⃣ Floyd Warshall Algorithm


Use
 Finds shortest paths between all pairs.
Applications
 Network analysis
 Routing tables
Drawbacks
 High complexity
 Uses large memory

Complexity:O(n 3)

1️⃣2️⃣ Prim’s Algorithm


Use
 Finds Minimum Spanning Tree.
Applications
 Cable network design
 Road network
Drawbacks
 Not efficient for disconnected graphs

1️⃣3️⃣ Kruskal’s Algorithm


Use
 Finds MST using edges.
Applications
 Communication networks
 Electrical wiring
Drawbacks
 Sorting edges increases overhead

1️⃣4️⃣ Topological Sorting


Use
 Orders tasks in dependency order.
Applications
 Scheduling
 Compiler design
Drawbacks
 Works only on DAG

1️⃣5️⃣ Knapsack Algorithms

Fractional Knapsack
Use
 Maximum profit with divisible items.
Applications
 Resource allocation
Drawbacks
 Not applicable when items indivisible
Uses:
 Greedy

0/1 Knapsack
Use
 Item fully selected or rejected.
Applications
 Budget planning
 Cargo loading
Drawbacks
 High memory usage
Uses:
 Dynamic Programming

1️⃣6️⃣ Backtracking
Use
 Tries all possible solutions with pruning.
Applications
 N Queen
 Sudoku
 Maze problems
Drawbacks
 Slow for large problems
 High recursion

1️⃣7️⃣ Branch and Bound


Use
 Optimization problems.
Applications
 TSP
 Job scheduling
Drawbacks
 Complexity can still be high

1️⃣8️⃣ Dynamic Programming


Use
 Solves overlapping subproblems.
Applications
 Fibonacci
 Knapsack
 Matrix Chain Multiplication
Drawbacks
 Requires extra memory
 Difficult to design

1️⃣9️⃣ Greedy Algorithm


Use
 Makes locally optimal choices.
Applications
 Huffman coding
 Dijkstra
 MST
Drawbacks
 May not give optimal solution always

2️⃣0️⃣ Divide and Conquer


Use
 Divides problem into smaller parts.
Applications
 Merge Sort
 Quick Sort
 Binary Search
Drawbacks
 Recursive overhead
 Extra memory sometimes

2️⃣1️⃣ Randomized Algorithms


Use
 Uses random numbers.
Applications
 Randomized Quick Sort
 Cryptography
Drawbacks
 Output/time may vary

2️⃣2️⃣ Approximation Algorithms


Use
 Near optimal solutions for NP-hard problems.
Applications
 TSP
 Scheduling
Drawbacks
 Solution may not be exact

You might also like