Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/25 01:38] – [2.4 A Survey of Common Running Times] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/25 01:52] (current) – [2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays] zhongc
@@ Line 51: / Line 51: @@
 Refer back to the 1/17 slide for the breakdown of the running time of O(N²) of the the total running time.
+Interesting/Readability: 8  5
 ===== 2.4 A Survey of Common Running Times =====
@@ Line 83: / Line 86: @@
 Independent set of size k. Given a graph,are there k nodes such that no two are joined by an edge?
+Note: Summary of running times. P20 slide 1/19
+Interesting/Readability: 8  5
+===== 2.5 A More Complex Data Structure:Priority Queues =====
+Motivation:
+**After overcoming higher-level obstacles,
+lower-level implementation details
+can improve runtime.**
+Summary
+Priority Queue revisited:
+Maintains a set of elements S
+• Each element v ∈ S has a key(v) for its priority
+ Smaller keys represent higher priorities
+ Supported operations
+• Add, delete elements
+• Select element with smallest key
+Implementing data structures: for sorting
+If we use unsorted lists: N² -why?
+If we use array: logn*N²
+If we use heaps: NlogN
+Implementation of Heaps:
+Know the implementation of the **Heapify-up** and **Heapify-down** with an array based implementation.
+Interesting/Readability: 7  7