Differences

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

--- courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/24 22:51] – [Section 3: Implementing the Stable Matching Algorithm] lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/25 01:53] (current) – [Section 5: Priority Queues] lovellv
@@ Line 59: / Line 59: @@
 Here are some common running times and examples of algorithms with these running times.
-  * Linear O(n) time: Running time is a constant factor times the size of the input. Computing the maximum and merging two sorted lists are O(n) algorithms (p 48).
+  * **Linear O(n) time**: Running time is a constant factor times the size of the input. Computing the maximum and merging two sorted lists are O(n) algorithms (p 48).
-  * O(nlogn) time: This is the running time of an algorithm that splits its input in half, recurses over them and combines the solutions in linear time.  Mergesort is an O(nlogn) algorithm (p 50).
+  * **O(nlogn) time**: This is the running time of an algorithm that splits its input in half, recurses over them and combines the solutions in linear time.  Mergesort is an O(nlogn) algorithm (p 50).
-  * Quadratic O(n^2) time: This is the running time of an algorithm with two nested loops, such as finding the pair of points that are closest together in the plane (p 51).
+  * **Quadratic O(n^2) time**: This is the running time of an algorithm with two nested loops, such as finding the pair of points that are closest together in the plane (p 51).
-  * Cubic O(n^3) time: This is the running time of an algorithm with three nested loops, such as finding the pairs of disjoint sets when given n sets (p 52).
+  * **Cubic O(n^3) time**: This is the running time of an algorithm with three nested loops, such as finding the pairs of disjoint sets when given n sets (p 52).
-  * O(n^k) time: This is the running time of searching over all subsets of size k of a set of size n.  The Independent Set problem has O(n^k) running time (p 53).
+  * **O(n^k) time**: This is the running time of searching over all subsets of size k of a set of size n.  The Independent Set problem has O(n^k) running time (p 53).
-  * O(2^n) time: 2^n is the total number of subsets of an n-element set.  Finding a independent set of maximum size is an O(2^n) algorithm (p 54).
+  * **O(2^n) time**: 2^n is the total number of subsets of an n-element set.  Finding a independent set of maximum size is an O(2^n) algorithm (p 54).
-  * O(n!) time: O(n!)>O(2^n). n! is the number of ways to match up n items with n other items. It is also the number of ways to arrange n items in order.  This running time emerges in the Traveling Salesman Problem (p 56).
+  * **O(n!) time**: O(n!)>O(2^n). n! is the number of ways to match up n items with n other items. It is also the number of ways to arrange n items in order.  This running time emerges in the Traveling Salesman Problem (p 56).
-  * Sublinear time: Binary search has O(logn) running time since it discards a fraction of the input on each iteration.
+  * **Sublinear time**: Binary search has O(logn) running time since it discards a fraction of the input on each iteration.
 Readability: 6
 ===== Section 5: Priority Queues =====
+This section explains how to implement priority queue, a data structure that supports addition, deletion, and selection of the highest priority element.  Priority queues are useful for many things, including sorting a set of n numbers.
+We can implement each queue operation in O(logn) time using a heap.  A heap combines the benefits of a sorted array and a list.  A heap can be thought of as a balanced binary tree where the key of a parent is always <= the keys of its children.  Finding the highest priority element in a heap is O(1) since the element with the smallest key is the root.  Adding and removing from a heap is O(logn) if we use Heapify-Up and Heapify-Down.
+Thus, if we implement a priority queue with a heap, we get O(n) time to start the queue, O(logn) time to insert, O(1) time to find the minimum key, O(logn) time to delete and O(logn) to extract the value with minimum key.
+Readability: 7