Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:wendy:chapter2 [2011/01/26 05:04] – shangw | courses:cs211:winter2011:journals:wendy:chapter2 [2011/01/27 01:09] (current) – [Section 4: A Survey of Common Running Times] shangw | ||
|---|---|---|---|
| Line 14: | Line 14: | ||
| ===== Section 4: A Survey of Common Running Times ===== | ===== Section 4: A Survey of Common Running Times ===== | ||
| - | This section introduces several common running times and provides examples. Linear running time's examples are maximization and merging lists; nlogn time example is mergesort; quadratic example is brute force algorithm for finding closest pair; an example of n^k time is the brute force algorithm for testing if there is an independent graph of size k given n nodes；then it goes on giving examples of algorithms beyond polynomial times; at the end, the section illustrates how binary search to be log n time-smaller than linear time.I found parts of the section very interesting, | + | This section introduces several common running times and provides examples. Linear running time's examples are maximization and merging lists; nlogn time example is mergesort; quadratic example is brute force algorithm for finding closest pair; an example of n^k time is the brute force algorithm for testing if there is an independent graph of size k given n nodes；then it goes on giving examples of algorithms beyond polynomial times; at the end, the section illustrates how binary search to be log n time-smaller than linear time.I found parts of the section very interesting, |
| ===== Section 5: A More Complex Data Structure: Priority Queues ===== | ===== Section 5: A More Complex Data Structure: Priority Queues ===== | ||
| + | This section focuses on implementations of priority queues using heap. The motivation is to achieve the sorting in nlogn time. The book defines what is a heap. Then it illustrates how heapify-up and down work. Next,the running time is analyzed. At the end, there is a summarization as well as an improvement with an additional position array. This section basically recorded in very details of what we talked in class about heaps and priority queues with heap data structure. I can see it being useful when the memory from lecture becomes rusty in the future. But now, it is a little bit lack of color. The readability is 5. | ||
