Advanced DSA

Fee : ₹29,500 + GST  ₹5310, Duration : 5 months, Contact : patkar@rajeshpatkar.com

1. Advanced Data Structures

1. Segment Trees and Fenwick Trees

   • Range queries and updates

   • Lazy propagation

   • Applications in computational problems

2. Persistent Data Structures

   • Concepts and use cases

   • Persistent segment trees and other examples

3. Tries and Suffix Trees

   • Advanced operations

   • Suffix arrays: construction and applications in string matching

4. Self-Balancing Trees

   • Treaps and Splay Trees: concepts and use cases

5. Augmented Data Structures

   • Range minimum query (RMQ)

   • Interval trees and dynamic interval management

6. B-Trees and B+ Trees

   • Disk storage suitability

   • Database indexing

7. Heavy-Light Decomposition

   • Tree decomposition for path queries

   • Applications in advanced graph problems

8. Sparse Table

   • Efficient range queries (RMQ) in static arrays

9. Tree Isomorphism

   • efficient comparison of tree structures

2. Advanced Graph Algorithms

1. Network Flow Algorithms

   • Max flow (Ford-Fulkerson, Edmonds-Karp, Dinic’s)

   • Minimum-cost flow

2. Graph Matching

   • Bipartite matching (Hungarian Algorithm)

   • General graph matching (Blossom Algorithm)

3. Strongly Connected Components (SCC)

   • Tarjan’s Algorithm

   • Kosaraju’s Algorithm

4. Euler Tours and Articulation Points

   • Identifying articulation points and bridges

   • Applications in connectivity problems

5. Advanced Shortest Path Algorithms

   • Johnson’s Algorithm

   • All pairs shortest paths

6. Centroid Decomposition

   • Applications in divide-and-conquer problems on trees

3. Advanced Algorithmic Techniques

1. Dynamic Programming (DP) on Trees

   • Applications in rooted trees

   • Solving subtree problems

2. DP Optimization Techniques

   • Divide and Conquer DP

   • Convex Hull Trick

   • Knuth’s Optimization

3. Bitmask DP

   • State representation for combinatorial problems

4. Greedy Algorithms

   • Advanced greedy approaches

   • Matroid theory applications

5. Backtracking and Branch-and-Bound

   • Solving NP-hard problems

6. Mo's Algorithm

   • Efficient offline query processing

7. Game Theory

   • Nim Game and Grundy Numbers

   • Applications in combinatorial games

4. Computational Geometry

1. Convex Hull Algorithms

   • Graham’s Scan, Andrew’s Monotone Chain

2. Line Intersection and Sweep Line

   • Solving geometric problems efficiently

3. Closest Pair of Points

   • Divide-and-conquer approaches

4. Polygon Algorithms

   • Area calculation

   • Point-in-polygon tests

5. Voronoi Diagrams

   • Construction and applications

5. String Algorithms

1. Advanced Pattern Matching

   • Z-Algorithm

   • Boyer-Moore Algorithm

   • Aho-Corasick Algorithm

2. Suffix Automata

   • Construction and applications

3. Knuth-Morris-Pratt (KMP) Algorithm

   • Efficient pattern matching

4. 2-SAT and Boolean Satisfiability Problems

   • Efficient algorithms for satisfiability

   • Applications in constraint satisfaction

6. Computational Complexity & NP Completeness

1. Complexity Classes

   • P, NP, and NP-hard problems

   • Polynomial reductions

   • Cook-Levin Theorem (overview)

2. Approximation Algorithms

   • Techniques for NP-hard problems

   • Examples: Traveling Salesman Problem (TSP), Vertex Cover

3. Probabilistic Algorithms

   • Monte Carlo and Las Vegas algorithms

   • Applications in randomized algorithms

7. Theory of Computation

1. Finite Automata

   • DFA and NFA equivalence

   • Regular languages and expressions

2. Pushdown Automata

   • Context-free grammars and parsing

3. Turing Machines

   • Concepts and significance

   • Undecidable problems

4. Lambda Calculus

   • Basics and functional programming applications

8. External Memory Algorithms & File Systems

1. I/O Model of Computation

   • Measuring I/O efficiency

2. External Sorting Algorithms

   • External Merge Sort

   • Multi-way Merge Sort

3. External Data Structures

   • External priority queues

   • External graph representations

4. RAID and SSDs

   • Characteristics and implications for algorithm design