Algorithms (Cont.)

Greedy Algorithm
This algorithm builds up the solution one piece at a time and chooses the next piece which gives the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global solutions are best fit for Greedy. For example, consider the Fractional Knapsack Problem:
Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity N to get the maximum total profit in the knapsack.
The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item.


Recursion ⇐ Next class starting at (04/02/2025)
Recursion is one of the most important algorithms which uses the concept of code reusability and repeated usage of the same piece of code.


Review: Computer Algorithms
    Which computer algorithm builds up the solution one piece at a time and chooses the next piece which gives the most obvious and immediate benefit?

      Backtracking
      Divide and Conquer
      Dynamic programming
      Greedy algorithm
Result:        




      The only thing worse than being talked about    
      is not being talked about.    
      — Oscar Wilde