Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:andrew:chapter4 [2011/02/16 01:48] – bennetta
+++ courses:cs211:winter2011:journals:andrew:chapter4 [2011/02/16 01:59] – bennetta
@@ Line 15: / Line 15: @@
 ===== 4.3: Optimal Caching: A More Complex Exchange Argument =====
-   *
+   * 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\\
+===== 4.4: Shortest Paths in a Graph =====
+   * 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\\
+===== Comments =====
+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