Chapter 4

• A greedy algorithm is the optimum algorithm for a given problem
  
  • Starts with a simple rule then continues using that rule to solve the rest of the equation.
    
  • In this particular problem the greedy algorithm is the algorithm which produces the fewest conflicts between intervals.
    
• To prove that an algorithm is optimal one must prove that the greedy algorithm always “stays ahead”
  
• These proofs are on pages 120 to 121
  
• Of course there exist certain circumstances presented by outside factors that can affect the optimality of a greedy algorithm
  

• This is a different take on the scheduling algorithm describe above
  
• Instead of a definite start and end time these tasks just have deadlines
  
• The optimal way to schedule this is one in which the tasks are sorted in increasing order of deadlines
  

• This problem involves requests in the form of cache maintenance
  
• Small amount of data can be accessed very quickly while a large amount of data requires more time to access
  
• Caching is a term for the process of storing a small amount of data in a fast memory
  
• Cache maintenance algorithms determine what to keep in the cache and what to take out in exchange for other pieces of memory
  
• A simple rule to create a greedy algorithm for this problem is when a job needs to be brought into the cache, take out the job that will need to be done the furthest into the future
  
  • This is called the Farthest-in-Future Algorithm
    
  • The proof of optimality for this algorithm can be found on pages 135-136
    

• Dijkstra's algorithm - a greedy algorithm to solve the shortest path problem
  
  • The details of this algorithm are explained on pages 137 and 138
    
  • Creates a minimum spanning tree from which you can find the shortest paths between any two points in a graph
    

Yet again this reading assignment did a lot to help refresh my memory of the topics we covered in class. The topic of greedy algorithms, in particular Dijkstra's algorithm, as well as the concept of minimum spanning trees are very easy concepts for me to understand and therefor this assignment was the easiest so far to power through. Readability: 9/10