Differences

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

--- courses:cs211:winter2018:journals:martinj:2.4 [2018/01/30 03:33] – martinj
+++ courses:cs211:winter2018:journals:martinj:2.4 [2018/01/30 03:51] (current) – martinj
@@ Line 2: / Line 2: @@
 This Chapter went into further detail about some common running times, including:
-__**Linear time O(n)**
+__**Linear time O(n)**__
-__
 This running time is at most a constant factor times the size of the input. Common problems that have this running time include computing the maximum and merging two sorted lists.
@@ Line 40: / Line 40: @@
 This chapter was very straightforward. The only algorithms it detailed were to demonstrate runtimes of simple algorithms such as those mentioned above. I don't have any questions about it and I think learning this will just be very straightforward and memorization-focused.
 ====== 2.5: Priority Queues ======
+This section focused on priority queues. It started with a general introduction of the data structure, which includes elements that each have priority values (keys). This allows us to select the elements in the queue by order of priority. It allows addition, deletion, and the selection of the element with the smallest key in O(logn) time each. The chapter then goes on to introduce the heap, which is a data structure for implementing a priority queue. It is a sort of balanced binary tree with a root and nodes that can each have up to two children. The keys are in "heap order" if the key of any element is at least as large as the key of the element at its parent node. The chapter then goes into heap operations, including heapify-up, which allows us to insert a new element in a heap of n elements in O(logn) time. It looks like...
+    Heapify-up(H,i):
+        If i>1 then
+            let j=parent(i)=[i/2]
+            If key[H[i]]<key[H[j]] then
+                swap H[i] and H[j]
+                Heapify-up(H,j)
+            Endif
+        Endif
+It also includes heapify-down, using which we can delete a new element in a heap of n elements in O(logn) time. The algorithm for this function can be found on page 63 in the textbook, and seems to be relatively intuitive once you get the hang of heapify-up. Near the end of this section is a list of other operations that we can create using the heap data structure and its heapify-down and heapify-up algorithms.
-====== 3.1 ======
-Brief summary of the section
+====== 3.1: Graphs ======
-~1 paragraph of about 5-10 sentences per section
+This section obviously focuses on graphs. The first couple of pages simply lists out common examples of graphs in our everyday life. They seem to be everywhere! Very promising and exciting! Everything discussed about graphs in this section was extremely basic, and relates directly back to the discrete math class I had last semester. All of the terms such as node, path, directionality, and connectivity are defined the same, and there is nothing about them that isn't very intuitive for me. For that reason, I don't see any real definitions or algorithms that are noteworthy about this chapter. It is just a fun and fluffy intro to graphs.
-feel free to write more if that will help you
-Include motivations for the given problem, as appropriate
-For algorithms, brief sketch of algorithm, intuition, and implementation
-Include runtime for algorithms
-Questions you have about motivation/solution/proofs/analysis
-Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa)
-Anything that you want to remember, anything that will help you
-Say something about how readable/interesting the section was on scale of 1 to 10