Scribd
Upload
21 views2 pages

Unit V Algorithm Notes

The document covers advanced tree and graph algorithms, including AVL and Red-Black trees, as well as topological sorting and strongly connected components. It discusses NP-Hard and NP-Complete problems, approximation algorithms for NP-Hard issues, and data stream algorithms for handling massive data. Additionally, it highlights parallel algorithms aimed at improving efficiency through multiple processors.

Uploaded by

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

Unit V Algorithm Notes

The document covers advanced tree and graph algorithms, including AVL and Red-Black trees, as well as topological sorting and strongly connected components. It discusses NP-Hard and NP-Complete problems, approximation algorithms for NP-Hard issues, and data stream algorithms for handling massive data. Additionally, it highlights parallel algorithms aimed at improving efficiency through multiple processors.

Uploaded by

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

Unit V: Advanced Tree & Graph Algorithms, NP Problems, Approximation, etc.

1. Advanced Tree Algorithms

AVL Tree:

- Self-balancing BST. Balance Factor: -1, 0, 1.

- Uses rotations to maintain balance.

- O(log n) operations.

Red-Black Tree:

- BST with Red/Black colors.

- Rules to maintain balance.

- O(log n) operations.

2. Advanced Graph Algorithms

Topological Sort:

- Linear ordering of DAG.

- O(V + E).

SCC:

- All nodes mutually reachable.

- Kosaraju/Tarjan algorithms.

Articulation Point & Bridges:

- Nodes/edges whose removal increases components.

3. NP-Hard and NP-Complete

P: Solvable in polynomial time.

NP: Verifiable in polynomial time.

NP-Hard: As hard as NP problems.

NP-Complete: Both NP & NP-Hard.


Unit V: Advanced Tree & Graph Algorithms, NP Problems, Approximation, etc.

Examples: SAT, TSP, Knapsack, Graph Coloring.

4. Approximation Algorithms

Used for NP-Hard problems.

- Approximation ratio = approx/optimal.

Examples:

- Vertex Cover: Ratio <= 2

- TSP (metric): Ratio <= 2

- Knapsack: FPTAS available.

5. Data Stream Algorithms

Used for massive data with limited memory.

- Count-Min Sketch: frequency approximation.

- Bloom Filter: membership testing.

- Reservoir Sampling: random sampling.

Applications: Logs, networks, sensors.

6. Parallel Algorithms

Goal: faster solutions using multiple processors.

Models: PRAM (EREW, CREW, CRCW).

Efficiency = speedup / processors.

Examples: Parallel Prefix Sum in O(log n) time.

Techniques: divide-conquer, pipelining.

You might also like