Differences

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

--- courses:cs211:winter2018:journals:mccaffreyk:home:2.3 [2018/01/23 03:26] – mccaffreyk
+++ courses:cs211:winter2018:journals:mccaffreyk:home:2.3 [2018/01/30 04:21] (current) – mccaffreyk
@@ Line 1: / Line 1: @@
+===== Chapter 2 =====
+==== Section 2.1: Computational Tractability ====
+Many of the problems we will focus on have clear conditions. Efficiency is an important component of algorithms. In addition to run-time efficiency, we must also consider concepts such as space efficiency. As we have touched on already, efficient algorithms generally lack unnecessary details. Efficiency is not simply how fast an algorithm runs. There are many components to efficiency such as scale, location and how the algorithm is run. Thus, in forming a definition of efficiency we must use mathematics rather than simply relying on base intuition. Our approach to the speed component of efficiency will be the running time of the worst case. Worst-case analysis is easier to handle(less complications,often little uncertainty over what the worst case is), and tells us key information about the algorithm itself rather than simply the way in which it is run. Further, something that I brought up in class is that many programmers refuse to tolerate things ever going wrong. Thus, since worst-case running time holds the highest risk of consequences, it is logical to focus on it. Brute force search provides an excellent way to compare algorithms. Bts is simply iterating through every single possibility and stopping when we find one that works. Generally, this fails to give insights into problems and has high running time(simple matching problem n! pairs, so brute force is O(n!). Thus, we conclude that **"An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute force search"**. A weakness of this definition is that it is overly vague. One desirable property of algorithms is that when we scale up the input size by any factor x, the running time only increases by some constant c. This holds for any algorithms which run in polynomial time. Thus, a new and perhaps too simple definition of efficiency for an algorithm is **"running in polynomial time"**. There are benefits to such a concise definition such as the ability to classify problems as having an efficient algorithm or not. Overall, this section had a great deal of material but was easy to read/understand. I would rate it 8/10.
+==== Section 2.2: Asymptotic Order of Growth ====
+We analyze run-time in terms of steps(arithmetic operation, following a pointer, looking up an entry, or assigning a value to a variable. We will ignore the coefficients and all but the highest terms in our big-o notation. This is mainly because we want to emphasize similarity between algorithms, it is easier to derive,and at high(significant) running times, the nature of the largest term in the equation holds far more significance than the others. Asymptotic Upper Bound: T(n)=O(f(n)), where T(n)<=c*f(n).O(n) is a familiar concept, where O stands for order and n is the highest-term with its coefficient removed. Asymptotic lower bound: show that a bound is the best possible instead of the worst possible(we will mostly be working with upper bounds). Asymptotically tight bounds are (basically) both upper and lower bounds.This section reviews the mathematical concepts of transitivity and sum and how they apply to bounds/asymptotic growth rates. As input size increases, logarithmic running times increase the slowest, then polynomial, then exponential(extremely fast, sometimes just described as "exponential running time"). Overall, this section was very hard for me to understand, in part because of the prevalence of dense equations. I would rate the ease of reading at between 4 and 5/10. I feel that my understanding of Asymptotic Lower Bounds and Asymptotic Tight Bounds is limited and I will need to continue studying the math for it to improve.
 ====== Section 2.3:Implementing the Stable Matching Algorithm Using Lists and Arrays ======
-    This chapter discusses the importance of picking the right data structures in terms of run-time. For instance, it reviewed how linked
+This chapter discusses the importance of picking the right data structures in terms of run-time. For instance, it reviewed how linked
-    lists are constant for search and deletion yet not for access while arrays have constant access time but linear, O(n) addition.
+lists are constant for search and deletion yet not for access while arrays have constant access time but linear, O(n) addition.
-    Overall, linked lists are therefore better for dynamic data subject to change whereas arrays are best when the data maintains its
+Overall, linked lists are therefore better for dynamic data subject to change whereas arrays are best when the data maintains its
-    size. We can convert between arrays and lists in O(n) time and it is often worth it such as when the input comes in an inefficient
+size. We can convert between arrays and lists in O(n) time and it is often worth it such as when the input comes in an inefficient
-    format. We apply out learnings to the stable matching algorithm. To make the algorithm O(n^2), all components in the loop must run in
+format. We apply out learnings to the stable matching algorithm. To make the algorithm O(n^2), all components in the loop must run in
-    constant time. To achieve this, we can represent free men as a linked list, we build an array to represent the indexes of the next
+constant time. To achieve this, we can represent free men as a linked list, we build an array to represent the indexes of the next
-    choices of women,and use an array to hold women's current matches. Finally, we create a 2d array for men's preferences and a 2d array
+choices of women,and use an array to hold women's current matches. Finally, we create a 2d array for men's preferences and a 2d array
-    for women's preferences. To check who women would pick between two men, we just access two arrays which is in constant time. Overall,
+for women's preferences. To check who women would pick between two men, we just access two arrays which is in constant time. Overall,
-    this section was quick and easy to read and understand. I would rate it at 8/10 to 9/10. One question I have is why the book didn't
+this section was quick and easy to read and understand. I would rate it at 8/10 to 9/10. One question I have is why the book didn't
-    discuss possibly using other data structures for men and women such as stacks or dictionaries. Also, I am curious how memory would
+discuss possibly using other data structures for men and women such as stacks or dictionaries. Also, I am curious how memory would
-    factor into this design in a real world scenario.
+factor into this design in a real world scenario.
+==== Section 2.4: A Survey of Common Running Times ====
+This chapter discusses some common run-times for programs and the reason that they are so prevalent. These run-times include O(n), O(n^2), O(nlogn), O(n^3),O(k^n), O(n!)and O(log(n)). O(n) arises when programs do one sweep through a set of input data and then perform some constant time operation on it. O(n^2) can arise either when programs use nested loops on the input values or one loop and then perform an operation on each value which requires O(n) time. For instance, selection sort has O(n^2) time complexity. O(n^3) often occurs when programs require two nested loops inside one outer loop. An example is a program which attempts to see if any set in a group of sets has no elements in common with the others. This goes through each set then through each other set then for each element in the outer set, making it have 3 loops. O(nlog(n)) occurs generally when an algorithm splits its input into two pieces, solves each in log(n) time, and then combines them in linear, O(n) time. One example of this complexity is merge sort. Log(n) time represents querying (partial reading) of input. It is often called sublinear time. One common example of this is binary search. O(k^n) is exponential rather than quadratic. We get this for some brute force algorithms. For instance, searching a node graph for independent pairs may be exponential. Finally, factorial time stems from  products which subtract or add 1 from 0 to n and multiply that by n. For instance, the brute force solution for the stable matching problem would be O(n!) because we do not count matched pairs, allowing us to subtract from the possible matches each time it is run.I would rate the reading for this section at 9/10. It was very straight forward and easy to intuitively understand the causes of these complexities.
+==== Section 2.5: A More Complex Data Structure: Priority Queues  ====
+Sometimes, we can improve running time by using complex data structures. The priority queue is one of these. In a priority queue, each value has a key where the smallest is first priority and the largest is last priority. Priority Queues may be applied to manage the order of processes in a computer. For operations such as adding, deleting, or selecting the element with the minimum key, priority queues generally run in )(log(n)) time. Thus, extracting all minima or maxima is O(nlog(n)) time as well as using a priority queue to sort. To implement priority queues, we use the heap. Heaps work better than simpler approaches because all operations take less than O(n) time. The best way to maintain heaps is in an array of nodes with their edges in linked list form. For heaps, basic operations are in constant or O(log(n)) time. For instance, Heapify-up and Heapify-down have log(n) complexity. Change key and delete are also in O(log(n)) time. I would rate the ease of reading for this section at 6/10. I feel like its descriptions were overly complicated and understanding these concepts was far easier with the material from class.