Differences

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

--- courses:cs211:winter2011:journals:charles:chapter2 [2011/01/27 07:57] – gouldc
+++ courses:cs211:winter2011:journals:charles:chapter2 [2011/01/27 08:20] (current) – gouldc
@@ Line 27: / Line 27: @@
   * Sublinear time
-I am not great at determining the better bounds when you get into factorials and n^ks (confusing!). I was wondering: Say one algorithm (A) is super effective for n<100 but awful for n>=100. Another algorithm (B) is average: it is worse than A for n<100 but it's better for n>=100. Can you do a check at the beginning, and do algorithm A for n<100, algorithm B for n>=100? Is this ever the case?
+I am not great at determining the better bounds when you get into factorials and n^ks (confusing!). I was wondering: Say one algorithm (A) is super effective for n<100 but awful for n>=100. Another algorithm (B) is average: it is worse than A for n<100 but it's better than A for n>=100. Can you check the sample size at the beginning, and do algorithm A for n<100, algorithm B for n>=100? Is this ever the case? (My guess would be that sometimes you can't know the sample size, so assuming it will be large is appropriate.)
 ===== 2.5 A More Complex Data Structure: Priority Queues =====
-A priority queue is a data structure designed to store elements with priority values. It can add, delete, and select elements. When a priority queue is asked to "select" an element, it returns the element with the highest priority. This characteristic of priority queues is applicable to problems such as the scheduling of processes on a computer. (Weighted interval scheduling comes to mind; see 1.2)
+Priority queues store elements with priority values. Removing from a priority queue returns the element with highest priority. Priority queues can be useful tools for scheduling problems, like the processes on a computer. Proposition 2.11 says a priority queue can sort n numbers in O(n) time. This is because it takes n steps to insert the numbers and n steps to remove the numbers (this is 2n in total, or O(n)). The section then explains the processes "heapify-up" and "heapify-down" which we received handouts for. The underlying heap structure of priority queues allows for insertion and deletion to occur in O(log n) time.