Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:haley:chapter2 [2014/01/22 01:34] – archermcclellanh | courses:cs211:winter2014:journals:haley:chapter2 [2014/01/22 02:13] (current) – archermcclellanh | ||
|---|---|---|---|
| Line 39: | Line 39: | ||
| * I mostly skimmed this section because it wasn't that interesting and it was significantly more captivating as a class discussion. 5/10. | * I mostly skimmed this section because it wasn't that interesting and it was significantly more captivating as a class discussion. 5/10. | ||
| - | ===== 2.5: A Survey of Common Running Times ===== | + | ===== 2.4: A Survey of Common Running Times ===== |
| * This section discusses what algorithms tend to take specific running times | * This section discusses what algorithms tend to take specific running times | ||
| Line 49: | Line 49: | ||
| * Quadratic | * Quadratic | ||
| * Anything with two nested loops | * Anything with two nested loops | ||
| + | * Cubic | ||
| + | * Determining whether sets are disjoint | ||
| + | * Polynomial - O(n^k) | ||
| + | * Brute-force searching over all subsets of size k | ||
| + | * Exponential | ||
| + | * Search algorithm over all subsets of size n | ||
| + | * Factorial | ||
| + | * Travelling salesman-like problems | ||
| + | * Sublinear - O(log(n)) | ||
| + | * Binary search | ||
| + | * This section was informative and didn't try too hard. 7/10. | ||
| - | | + | ===== 2.5: Priority Queues ===== |
| + | |||
| + | | ||
| + | * We implement priority queues using a heap, or a balanced binary tree. | ||
| + | * The implementation details span from pg 60-64. | ||
| + | * This section was not interesting to read. 4/10. | ||
