DEV Community

Jayaprasanna Roddam
Jayaprasanna Roddam

Posted on • Updated on

DSA: Greedy algorithms - questions

1. Basic Greedy Problems
·      Fractional Knapsack Problem: Maximize the value in a knapsack with fractional items.
·      Activity Selection Problem: Select the maximum number of activities that don’t overlap.
·      Job Sequencing Problem: Schedule jobs to maximize profit with deadlines.
·      Huffman Coding: Construct an optimal prefix code for a set of characters.
·      Minimum Number of Coins: Find the minimum number of coins for a given amount.
·      Maximum Subarray Sum (Kadane's Algorithm): Find the maximum sum of a contiguous subarray.
· Change-Making Problem: Compute the minimum number of coins for change.
·      Greedy Coloring of Graphs: Color a graph using the minimum number of colours.
·      Minimum Spanning Tree (Kruskal’s Algorithm): Find the minimum spanning tree of a graph.
·      Minimum Spanning Tree (Prim’s Algorithm): Another method to find the minimum spanning tree.
 
 2. Interval and Scheduling Problems
·      Interval Scheduling Maximization: Find the maximum number of non-overlapping intervals.
·      Job Scheduling with Deadlines: Schedule jobs to maximize profit with deadlines.
·      Weighted Interval Scheduling: Maximize profit with intervals having weights and deadlines.
·      Minimum Number of Platforms: Find the minimum number of platforms required for a train schedule.
·      Event Scheduling: Schedule events to maximize the number of non-overlapping events.
·      Conference Room Scheduling: Find the minimum number of rooms required for a conference.
 
 3. Graph Problems
·      Dijkstra’s Shortest Path Algorithm: Find the shortest path from a source to all nodes.
·      Prim’s Algorithm for MST: Find the minimum spanning tree using a priority queue.
·      Kruskal’s Algorithm for MST: Find the minimum spanning tree using edge sorting and union-find.
·      Shortest Path with a Fixed Number of Edges: Find the shortest path with exactly k edges.
·      Traveling Salesman Problem (TSP) Approximation: Find a near-optimal solution for TSP.
·      Maximum Flow in a Network: Find the maximum flow using algorithms like Ford-Fulkerson.
·      Minimum Cut in a Network: Find the minimum cut in a flow network.
·      Shortest Path in Weighted Graphs (Greedy Approach): Find shortest paths with a modified greedy approach.
 
 4. Partitioning and Selection Problems
·      Greedy Set Cover: Find a minimum number of sets to cover a universe of elements.
·      Kth Largest Element: Find the Kth largest element in an unsorted array.
·      Partition Problem: Determine if a set can be partitioned into subsets with equal sum.
·      Maximum Sum of Non-Adjacent Elements: Find the maximum sum of non-adjacent elements in an array.
·      Weighted Job Scheduling: Schedule jobs with weights to maximize total profit.
·      Greedy Knapsack Problem: Solve the knapsack problem with fractional values.
 
 5. String and Text Processing
·      Greedy String Matching: Find patterns in strings using a greedy approach.
·      Minimum Window Substring: Find the smallest substring containing all characters of another string.
·      Optimal Merge Pattern: Minimize the cost of merging multiple files.
·      Longest Common Subsequence (Greedy Approximation): Find a long common subsequence with greedy methods.
 
·      Network and Flow Problems
·      Maximum Bipartite Matching: Find the maximum matching in a bipartite graph.
·      Minimum Vertex Cover: Find the minimum vertex cover in a bipartite graph.
·      Maximum Independent Set: Find a maximum independent set in a graph.
·      Network Flow (Edmonds-Karp Algorithm): Find maximum flow using a BFS-based approach.
 
 7. Geometry and Spatial Problems
·      Convex Hull: Find the convex hull of a set of points.
·      Closest Pair of Points: Find the closest pair of points using a greedy approach.
·      Line Intersection: Find intersections of lines using greedy algorithms.
 
 8. Miscellaneous Greedy Problems
·      Minimum Cost Path with Obstacles: Find the minimum cost path in a grid with obstacles.
·      Minimum Cost to Merge Stones: Merge stones with minimum cost to form one pile.
·      Water Trapping: Calculate the amount of water trapped between elevations.
·      Greedy Box Packing: Pack boxes in a container with minimum wasted space.
·      Greedy Travel Path: Find an efficient travel path using greedy heuristics.
·      Optimal Resource Allocation: Allocate resources optimally with greedy methods.
·      Greedy Scheduling: Schedule tasks to minimize overall completion time.
·      Greedy Stock Trading: Maximize profit from stock trading with limited transactions.
·      Greedy Tournament Scheduling: Schedule tournaments to maximize efficiency.
 
 9. Approximation Algorithms
·      Greedy TSP Approximation: Approximate solution for the Traveling Salesman Problem.
·      Greedy Vertex Cover: Approximate the minimum vertex cover in a graph.
·      Greedy Knapsack Problem: Approximate solution for the 0/1 knapsack problem.
·      Greedy Graph Coloring: Approximate colouring of graphs with minimum colours.
·      Greedy Set Packing: Approximate solution for the set packing problem.

 10. Scheduling and Allocation
·      Job Shop Scheduling: Allocate jobs to machines with minimum makespan.
·      Resource Allocation: Allocate resources to maximize utilization.
·      Interval Partitioning: Partition intervals into a minimum number of resources.
·      Load Balancing: Distribute tasks to minimize the maximum load.
 
 11. Array and Sequence Optimization
·      Minimum Difference Partition: Partition an array to minimize the difference between sums.
·      Largest Sum of K Contiguous Elements: Find the largest sum of k contiguous elements.
·      Minimum Cost to Cut a Rod: Find the minimum cost of cutting a rod into pieces.
·      Greedy Array Rearrangement: Rearrange an array to maximize a certain metric.
 
 12. Resource Management
·      Greedy Load Balancing: Distribute resources to minimize the maximum load.
·      Greedy Job Scheduling with Deadlines: Schedule jobs to maximize profit by deadlines.
·      Optimal Resource Allocation for Tasks: Allocate resources to tasks optimally.
 
 13. Graph Approximation
·      Greedy Approximation for Steiner Tree: Approximate solution for the Steiner tree problem.
·      Greedy Solution for the Set Cover Problem: Approximate set cover with greedy methods.
·      Greedy Approach for Facility Location: Approximate facility location problems.
 
 14. Financial and Operational Optimization
·      Greedy Investment Strategy: Maximize returns from investments using greedy methods.
·      Greedy Pricing Strategy: Set prices to maximize revenue.
·      Greedy Supply Chain Management: Optimize supply chain operations with greedy algorithms.
 
 15. Network Design
·      Greedy Network Design: Design efficient networks with minimum cost.
·      Greedy Communication Scheduling: Schedule communication to maximize efficiency.
 
 16. Computational Geometry
·      Greedy Point Selection: Select points to cover a region with minimal number of points.
·      Greedy Polygon Triangulation: Triangulate a polygon using greedy methods.
 
 17. Computational Scheduling

·      Greedy Task Scheduling: Schedule tasks to minimize completion time.
·      Greedy Job Allocation: Allocate jobs to minimize total processing time.
 
 18. Multi-Objective Optimization
·      Greedy Multi-Objective Scheduling: Schedule tasks to optimize multiple objectives.
·      Greedy Multi-Objective Resource Allocation: Allocate resources to optimize multiple metrics.
 
 19. Game Theory and Strategic Planning
·      Greedy Game Strategy: Develop strategies for games using greedy algorithms.
·      Greedy Resource Allocation in Games: Allocate resources optimally in-game scenarios.
 
 20. Advanced Greedy Algorithms

·      Greedy Approach for Maximum Independent Set: Approximate solution for the maximum independent set.
·      Greedy Algorithm for Vertex Cover in Non-Bipartite Graphs: Approximate vertex cover in general graphs.
·      Greedy Algorithm for Shortest Path with Constraints: Find the shortest path under constraints.
·      Greedy Algorithm for Network Flow with Multiple Sources: Solve network flow problems with multiple sources.
·      Greedy Algorithm for Weighted Graph Coloring: Approximate graph coloring with weights.
·      Greedy Algorithm for Cutting Stock Problem: Solve cutting stock problems with greedy methods.
·      Greedy Approach for Vehicle Routing Problem: Approximate solution for vehicle routing.
·      Greedy Algorithm for Multi-Dimensional Knapsack Problem: Approximate multi-dimensional knapsack solutions.
·      Greedy Algorithm for Optimal Path Planning: Find optimal path planning using greedy heuristics.
·      Greedy Algorithm for Multiple Knapsack Problem: Solve multiple knapsack problems with greedy methods.
·      Greedy Algorithm for Bandwidth Allocation: Optimize bandwidth allocation with greedy approaches.
·      Greedy Approach for Scheduling with Resource Constraints: Schedule tasks considering resource constraints.
·      Greedy Algorithm for Weighted Job Scheduling: Maximize profit with weighted job scheduling.
·      Greedy Algorithm for Large-Scale Network Optimization: Optimize large-scale networks with greedy methods.
·      Greedy Algorithm for Task Assignment in Parallel Systems: Assign tasks in parallel systems optimally.
·      Greedy Algorithm for Optimal Sequencing: Sequence tasks or events optimally.
·      Greedy Approach for Inventory Management: Optimize inventory levels using greedy algorithms.
·      Greedy Algorithm for Optimal Time Management: Manage time effectively with greedy approaches.
 
 
 

Top comments (0)