#48 Introduction to Greedy Algorithms | C Programming Tutorial

C Programming Tutorial #48 Introduction to Greedy Algorithms. Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, Fractional Knapsack problem (See this) can be solved using Greedy, but 0-1 Knapsack cannot be solved using Greedy.
This C Programming lecture contains the following topics:
00:30 Illustrative example: Making change with fewest notes
04:40 Optimal substructure and greedy-choice property
08:40 Job scheduling problem: sequence jobs on a machine to minimize average completion time
12:50 Completion time versus job duration
13:42 Sum of completion times
17:23 ptimal schedule: swapping jobs to decrease cost
20:35 Greedy algorithm for job scheduling