Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revisionLast revisionBoth sides next revision | ||
| courses:cs211:winter2011:journals:andrew:chapter4 [2011/02/16 01:45] – created bennetta | courses:cs211:winter2011:journals:andrew:chapter4 [2011/02/16 01:59] – bennetta | ||
|---|---|---|---|
| Line 9: | Line 9: | ||
| * Of course there exist certain circumstances presented by outside factors that can affect the optimality of a greedy algorithm\\ | * Of course there exist certain circumstances presented by outside factors that can affect the optimality of a greedy algorithm\\ | ||
| - | ===== 4.2: Scheduling to Minimize Lateness: An Exchange Argument | + | ===== 4.2: Scheduling to Minimize Lateness: An Exchange Argument |
| * This is a different take on the scheduling algorithm describe above\\ | * This is a different take on the scheduling algorithm describe above\\ | ||
| * Instead of a definite start and end time these tasks just have deadlines\\ | * Instead of a definite start and end time these tasks just have deadlines\\ | ||
| Line 15: | Line 15: | ||
| ===== 4.3: Optimal Caching: A More Complex Exchange Argument ===== | ===== 4.3: Optimal Caching: A More Complex Exchange Argument ===== | ||
| - | | + | |
| + | * 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' | ||
| + | * 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' | ||
