# Introduction To

A Greedy Algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Greedy algorithms are quite successful in some problems, such as Huffman encoding which is used to compress data, or Dijkstra's algorithm, which is used to find the shortest path through a graph.

In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.

In general, greedy algorithms have five components:

1. A candidate set, from which a solution is created

2. A selection function, which chooses the best candidate to be added to the solution

3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution

4. An objective function, which assigns a value to a solution, or a partial solution, and

5. A solution function, which will indicate when we have discovered a complete solution

# Course Structure

## Standard Greedy Algorithms

- Activity Selection Problem | Greedy Algo-1
- Greedy Algorithm for Egyptian Fraction
- Job Sequencing Problem
- Job Sequencing Problem | Set 2 (Using Disjoint Set)
- Job Sequencing Problem – Loss Minimization
- Job Selection Problem – Loss Minimization Strategy | Set 2
- Huffman Coding | Greedy Algo-3
- Efficient Huffman Coding for Sorted Input | Greedy Algo-4
- Huffman Decoding
- Water Connection Problem
- Policemen catch thieves
- Minimum Swaps for Bracket Balancing
- Fitting Shelves Problem
- Assign Mice to Holes

## Greedy Algorithms in Graphs

- Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2
- Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5
- Boruvka’s algorithm | Greedy Algo-9
- Reverse Delete Algorithm for Minimum Spanning Tree
- Problem Solving for Minimum Spanning Trees (Kruskal’s and Prim’s)
- Dijkstra’s shortest path algorithm | Greedy Algo-7
- Dial’s Algorithm (Optimized Dijkstra for small range weights)
- Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8
- Prim’s MST for Adjacency List Representation | Greedy Algo-6
- Correctness of Greedy Algorithms
- Minimum cost to connect all cities
- Max Flow Problem Introduction
- Number of single cycle components in an undirected graph

## Greedy Algorithms in Arrays

- Minimum product subset of an array
- Maximum product subset of an array
- Maximize array sum after K negations | Set 1
- Maximize array sum after K negations | Set 2
- Maximize the sum of arr[i]*i
- Maximum sum of increasing order elements from n arrays
- Maximum sum of absolute difference of an array
- Maximize sum of consecutive differences in a circular array
- Partition into two subarrays of lengths k and (N – k) such that the difference of sums is maximum
- Minimum sum of product of two arrays
- Minimum sum by choosing minimum of pairs from array
- Minimum sum of two numbers formed from digits of an array
- Minimum increment/decrement to make array non-Increasing
- Making elements of two arrays same with minimum increment/decrement
- Sorting array with reverse around middle
- Sum of Areas of Rectangles possible for an array
- Array element moved by k using single moves
- Find if k bookings possible with given arrival and departure times
- Lexicographically smallest array after at-most K consecutive swaps
- Largest lexicographic array with at-most K consecutive swaps

## Greedy Algorithms in Operating Systems

- Program for First Fit algorithm in Memory Management
- Program for Best Fit algorithm in Memory Management
- Program for Worst Fit algorithm in Memory Management
- Operating System | Program for Next Fit algorithm in Memory Management
- Program for Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive)
- Program for Shortest Job First (SJF) scheduling | Set 2 (Preemptive)
- Schedule jobs so that each server gets equal load
- Job Scheduling with two jobs allowed at a time
- Scheduling priority tasks in limited time and minimizing loss
- Program for Optimal Page Replacement Algorithm
- Program for Page Replacement Algorithms | Set 1 ( LRU)
- Program for Page Replacement Algorithms | Set 2 (FIFO)

## Approximate Greedy Algorithms for NP Complete Problems

- Set Cover Problem | Set 1 (Greedy Approximate Algorithm)
- Bin Packing Problem (Minimize number of used Bins)
- Graph Coloring | Set 2 (Greedy Algorithm)
- K Centers Problem | Set 1 (Greedy Approximate Algorithm)
- Shortest Superstring Problem
- Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)
- Travelling Salesman Problem | Set 2 (Approximate using MST)

## Greedy Algorithms for Special Cases of DP problems

## Misc

- Split n into maximum composite numbers
- Maximum trains for which stoppage can be provided
- Buy Maximum Stocks if i stocks can be bought on i-th day
- Find the minimum and maximum amount to buy all N candies
- Find maximum sum possible equal sum of three stacks
- Maximum elements that can be made equal with k updates
- Divide cuboid into cubes such that sum of volumes is maximum
- Maximum number of customers that can be satisfied with given quantity
- Minimum Fibonacci terms with sum equal to K
- Divide 1 to n into two groups with minimum sum difference
- Minimize Cash Flow among a given set of friends who have borrowed money from each other
- Minimum rotations to unlock a circular lock
- Paper Cut into Minimum Number of Squares
- Minimum difference between groups of size two
- Minimum rooms for m events of n batches with given schedule
- Connect n ropes with minimum cost
- Minimum Cost to cut a board into squares
- Minimum cost to process m tasks where switching costs
- Minimum cost to make array size 1 by removing larger of pairs
- Minimum cost for acquiring all coins with k extra coins allowed with every coin
- Find minimum time to finish all jobs with given constraints
- Minimum Number of Platforms Required for a Railway/Bus Station
- Minimize the maximum difference between the heights
- Minimum increment by k operations to make all elements equal
- Minimum edges to reverse to make path from a source to a destination
- Find minimum number of currency notes and values that sum to given amount
- Minimum initial vertices to traverse whole matrix with given conditions
- Check if it is possible to survive on Island
- Largest palindromic number by permuting digits
- Smallest number with sum of digits as N and divisible by 10^N
- Find smallest number with given number of digits and sum of digits
- Rearrange characters in a string such that no two adjacent are same
- Rearrange a string so that all same characters become d distance away
- Print a closest string that does not contain adjacent duplicates
- Smallest subset with sum greater than all other elements
- Lexicographically largest subsequence such that every character occurs at least k times