Greedy Algorithms Exercises

   < Previous  Next >
  1. Discuss with your neighbor:
    1. How a greedy algorithm works
    2. How they differ from a dynamic programming algorithms
    3. Give some examples of greedy algorithms
    4. Is earning a Master's degree a step in a greedy algorithm?
  2. Discuss with your neighbor:
    1. What are the conditions so that a greedy algorithm yields the optimal solution
    2. Can we still use a greedy algorithm that doesn't always provide the optimal solution?
  3. What are the steps to developing a greedy algorithm?
  4. What is the activity selection problem and what is a greedy solution to it?
    • What would a dynamic programming solution look like for this problem?
  5. What is the knapsack problem? Does a greedy algorithm provide the optimal solution?
  6. Discuss with your neighbor(s) how Huffman Codes are calculated. Be sure to include in your discussion:
    1. Why they are used
    2. Why the algorithm is greedy?
  7. Here are the most common characters in the King James Version of the Bible (ignoring case):
    Character Count Code Total Bits
    (space)745,903
    e411,755
    t317,486
    h283,478
    a276,021
    o242,007
    n224,235
    i193,035
    s189,502
    Subtotal2,883,422
    What are the codes that produce the minimum total bits (and what is the minimum total bits)? What is the total number of bits by assigning each character a 4-bit code?
  8. Given the following jobs and their required execution times, in what order should they run to minimize the average time to completion?
    What algorithm did you use to schedule the jobs?
      Job     j1     j2     j3     j4  
      Time     7     8     2     1  
  9. Given the following jobs and their required execution times, in what order should they run to minimize the average time to completion if they're allowed to run on 4 cores?
    What algorithm did you use to schedule the jobs?
      Job     j1     j2     j3     j4     j5     j6     j7     j8     j9     j10     j11  
      Time     7     8     2     1     9     8     4     5     1     7     2  
  10. You've been hired by an international web-ordering company, Nile, to design an algorithm to fit their various-sized products into boxes. Lucky for you, there's only box size. What algorithm are you going to use to determine which product goes into which box? Will it produce the optimal (minimum) number of boxes?

Last Modified: