Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:emily:entryfive [2014/02/26 04:50] – [Chapter 4.5] hardye | courses:cs211:winter2014:journals:emily:entryfive [2014/02/26 04:51] (current) – [Chapter 4.2] hardye | ||
|---|---|---|---|
| Line 51: | Line 51: | ||
| **(4.10) The schedule A produced by the greedy algorithm has optimal maximum lateness L.** | **(4.10) The schedule A produced by the greedy algorithm has optimal maximum lateness L.** | ||
| + | The exchange argument is still pretty confusing to me I'd like to see a detailed outline of it. The book confused me after the lecture we had in class. | ||
| + | |||
| + | Readability 8/10 | ||
| ====== Chapter 4.4 ====== | ====== Chapter 4.4 ====== | ||
| **Shortest Paths in a Graph** | **Shortest Paths in a Graph** | ||
| Line 91: | Line 94: | ||
| The runtime of this algorithm is O(m*n). The while loop is executed n-1 times. To compute the edge with the minimum weight for m edges takes O(m) time so the overall runtime is O(mn). | The runtime of this algorithm is O(m*n). The while loop is executed n-1 times. To compute the edge with the minimum weight for m edges takes O(m) time so the overall runtime is O(mn). | ||
| If we keep the minimum values for each node in a priority queue we improve our runtime. We add the nodes into the PQ and extract the minimum to add to the set of the shortest path nodes. When we do this our runtime is improved to O(m log n) time. | If we keep the minimum values for each node in a priority queue we improve our runtime. We add the nodes into the PQ and extract the minimum to add to the set of the shortest path nodes. When we do this our runtime is improved to O(m log n) time. | ||
| + | |||
| + | Readability 8/10 | ||
| ====== Chapter 4.5 ====== | ====== Chapter 4.5 ====== | ||
| **The Minimum Spanning Tree Problem** | **The Minimum Spanning Tree Problem** | ||
