Differences

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

--- courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/01/25 03:21] – created garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/01/25 04:14] – [Chapter 2: Basics of Algorithm Analysis] garrettheath4
@@ Line 1: / Line 1: @@
 ====== Week 2 ======
-===== Section 2.3 =====
+==== Chapter 2: Basics of Algorithm Analysis ====
-Algorithms tend to abstract away the method for storing data that is needed to actually run the algorithm.  In order to run the algorithm on a computer, we need a way to transform our algorithm into a form that a computer can recognize.  Luckily, most of the steps in the algorithm are usually easily transferrable, but the implementation of data structures is not specified in the algorithm and so is left up to the programmer to determine.  The problem with this is that the efficiency of the data structure in terms of space and the way it is manipulated by the algorithm can severely hinder the runtime complexity of the algorithm.  Thus, we must be careful in determining which data structures will suit the algorithm best.
+=== Arrays and Lists ===
+/* True Story */ Algorithms tend to abstract away the method for storing data that is needed to actually run the algorithm.  In order to run the algorithm on a computer, we need a way to transform our algorithm into a form that a computer can recognize.  Luckily, most of the steps in the algorithm are usually easily transferrable, but the implementation of data structures is not specified in the algorithm and so is left up to the programmer to determine.  The problem with this is that the efficiency of the data structure in terms of space and the way it is manipulated by the algorithm can severely hinder the runtime complexity of the algorithm.  Thus, we must be careful in determining which data structures will suit the algorithm best.
+The two most basic data structures are arrays and linked lists.  The following table summarizes the pros and cons of both.
+^ //Operation//  ^ Arrays    ^ Lists                                                  ^
+| Get Element    | Fast      | Slow                                                   |
+| Add Element    | Slow      | Fast                                                   |
+| Replace Element| Fast      | Fast((After finding the element, which is **slow**.))  |
+| Remove Element | Slow      | Fast((After finding the element, which is **slow**.))  |
-~~DISCUSSION~~
+=== A Survey of Common Running Times ===
+Any algorithm can be characterized by its running time.  There exists an ordered list of different running time complexities such that the lower order running time complexities will decrease, stay the same, or increase by very little as the problem set grows larger.  Likewise, the running time complexities at the high end of the list will increase very very fast as the problem set grows larger.  All of these runtime complexities are categories of Big-O complexities and can be expressed in terms of Big-O notation.  //Big-O notation// is discussed in [[courses:cs211:winter2012:journals:garrett:entries:week_1#asymptotic_order_of_growth|Section 2.2]].
+{{ :courses:cs211:winter2012:journals:garrett:entries:linear.png?|In this graph, the x axis is the problem set size and the y axis is the amount of time needed to finish the computation.}} **Linear time** problems are problems whose time complexity increases at a constant rate as the problem set grows larger.  Examples of linear-time problems include finding the maximum element (such as a number) of a set and merging two sorted lists.
+{{ :courses:cs211:winter2012:journals:garrett:entries:growthcurves.png?400|}} **n log n time** problems are problems whose time complexity increases at a constant rate as the problem set grows larger.
+~~DISCUSSION~~