Section outline

  • LESSON OBJECTIVE

    • To teach the basic methodology of greedy algorithm and the examples/ problems those are typically solved by this methodology and the complexity analysis of those problems

    LEARNING OUTCOMES

    • Appreciate the importance of solving certain problems using greedy algorithm strategy
    • Explain scenarios where greedy algorithm fails and need other strategies to solve
    • Solve the Coin Change Problem based on Greedy Method
    • Solve the Knapsack Problem based on Greedy Method
    • Solve the Huffman coding based on Greedy Method
    • Solve the  Bin packing Problem based on Greedy Method
    • Exercise the Sorting Algorithm with some additional problems in the Lab

    TOPICS

    • Properties of greedy algorithm
    • Coin change problem
    • Discussion on Bin packing Problem
    • Discussion on Knapsack Problem
    • Discussion on Huffman coding

    CONTENTS