Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/24 23:14] – [2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays] 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 45: / Line 45: @@
 Array    Add element O(1)   Delete element O(N)   Find element O(N)
 List     Add element O(1)   Delete element O(1)   Find element O(N)
+It takes O(N) to convert from an array to a list and the same the other way around.
+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 =====
+Summary
+When trying to analyze a new algorithm, it helps to have a rough sense of
+the "landscape" of different running times.
+So this section covers some of the common types of running times that we are going to keep refering back to later.
+**Linear time: O(N)**
+An example would be iterating through a collection and perform some constant operation on each elment of that collection.
+Examples:
+  * Computing the max of a list.
+  * Merging the two sorted list. Only have to go through the two lists once to get it done.
+**O(NlogN) Time**
+Examples
+  * Mergesort --- divide into logN pieces of small problems and for each one perform the merge which takes N.
+  * Time stamp problem
+**Quadratic Time O(N²)**
+Exaples:
+  * Matching problem.
+  * calculating distances between any given points.
+**Cubic Time O(N³**)
+For each set Si ,For each other set Sj, For each element p of Si, Determine whether p also belongs to Sj.
+**O(N^k) Time**
+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