Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:haley:chapter2 [2014/01/22 01:08] – 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 45: | Line 45: | ||
| * Finding the maximum of a list or array of numbers | * Finding the maximum of a list or array of numbers | ||
| * Merging two sorted lists | * Merging two sorted lists | ||
| - | | + | |
| - | * I found this section | + | * Sorting: merge sort |
| + | * Quadratic | ||
| + | * 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 | ||
| + | |||
| + | ===== 2.5: Priority Queues ===== | ||
| + | |||
| + | * This section discusses priority queues, which is a set where each element has some key indicating how important it is. The lower the key, the higher the priority. | ||
| + | * 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. | ||
