CS303: Algorithms, Topic: Unit 7: Greedy Algorithms

Unit 7: Greedy Algorithms
In this unit, we will look into a common computer science algorithm technique called the greedy algorithms. Like the dynamic programming paradigm, greedy algorithms typically apply to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. The idea of greedy algorithm is to make each choice in a locally optimal manner. We will explore some common greedy algorithms in use today as a way of explaining the topic in this unit.

Completing this unit should take you approximately 7 hours.
- Upon successful completion of this unit, the student will be able to:
  
  Describe greedy algorithms and their applications.
- 7.1: Introduction to Greedy Algorithms
  - University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's "Greedy Algorithms" URL
    Read Chapter 5 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
- 7.2: Greedy Algorithms - Part I
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "Greedy Algorithms - I" Page
    Watch this video to learn about greedy algorithms.
- 7.3: Greedy Algorithms - Part II
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "Greedy Algorithms - II" Page
    Watch this video to learn about greedy algorithms.
- 7.4: Greedy Algorithms - Part III
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "Greedy Algorithms - III" Page
    Watch this video to learn about greedy algorithms.
  - Wikipedia: "Recursion" URL
    Read this article to learn about the mathematical concept behind the idea of recursion.
  - Greedy Algorithms Assignment URL
    Complete all questions in this activity. There is one question on the minimum spanning tree problem requiring two implementations using the Kruskal's algorithm and the Prim's algorithm. You can check your answers against the Answer Key.