Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section4 [2012/01/24 02:16] – [Linear Time O(n)] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptter2section4 [2012/01/24 23:11] (current) – mugabej
@@ Line 11: / Line 11: @@
   * Computing the Maximum
-algorithm max = a<sub>1</sub> \\
+algorithm:
-          for i = 2 to n: \\
+          max = a <sub>1</sub>  \\
-               if a<sub> i</sub> is greater than max then \\
+          for i = 2 to n:  \\
-                      set max = a<sub> i</sub> \\
+              if a<sub> i</sub> is greater than max then  \\
-               Endif \\
+                    set max = a<sub> i</sub>  \\
-          Endfor\\
+              Endif  \\
+          Endfor \\
-  * Merging Two Sorted lists
- algorithm:
+Merging Two Sorted lists
+algorithm:
     To merge sorted lists A = a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,...,a<sub>n</sub> and B = b<sub>1</sub>,b<sub>2</sub>,b<sub>3</sub>,...,b<sub>n</sub>:
@@ Line 41: / Line 42: @@
-  * O(nlogn) Time
+=====O(nlogn) Time=====
+It's the running time of any algorithm that splits the input into two equal-sized pieces,solves each piece recursively and then combines the two solutions in linear time. Examples: //Mergesort//; finding the largest interval of time between the first and the last of the time-stamps during which no copy of a file arrived to a given server,...
+=====Quadratic Time O(n²)=====
+Often times, for problems involving pairs of things. Example: Given //n// points in space, each specified by (x,y), find the pair of points that are closest together. The brute-force algorithm for this problem would enumerate all pairs of points,compute the distance between each pair, and then choose the pair for which this distance is smallest. The number of pairs is //n//<sup>2</sup> because there are //n// possible ways to choose the first element and //n// -1 possible ways to choose the second element(almost //n//).
+Algorithm:   For each input (x<sub>i</sub>,y<sub>j</sub>)
+                 For each other input point (x<sub>j</sub>,y<sub>j</sub>)
+                     compute d = √((x<sub>i</sub> - x<sub>j</sub>)<sup>2</sup> + ( y<sub>i</sub> - y<sub>j</sub>)<sup>2</sup>
+                     if d is less than the current minimum,update minimum to d
+                 Endfor
+             Endfor
+ Another obvious instance of the Quadratic running time is the result of using a pair of nested loop within an algorithm,each loop taking O(n) time.
+=====Cubic Time O(n³)=====
+Example: Given two sets,find whether some pair of the given sets is disjoint
+algorithm:\\
+ for each set S<sub>i</sub>  \\
+    for each other set S<sub>j</sub> \\
+       for each element //p// of S<sub>i</sub>  \\
+         Determine whether //p// also belongs to S<sub>j</sub> \\
+       Endfor  \\
+       if no element of S<sub>i</sub> belongs to S<sub>j</sub> then  \\
+             Report that S<sub>i</sub> and S<sub>j</sub> are disjoint  \\
+       Endif  \\
+     Endfor \\
+  Endfor  \\
+=====O(n^k) Time=====
+This running time is obtained when we're searching over all subsets of size k. Example:Finding the independent sets in a graph. \\
+Algorithm: \\
+  for each subset S of k nodes \\
+      check whether S constitutes an Independent set \\
+      if S is an Independent set then \\
+         Stop and declare success \\
+      Endif \\
+  Endfor \\
+  if no k-node independent set was found then  \\
+     Declare failure \\
+  Endif \\
+=====Beyond Polynomial Time=====
+Example: Given a graph, find an Independent set of //maximum// size. \\
+Algorithm: \\
+  for each subset S of nodes \\
+     check whether S constitutes and independent set \\
+     If S is a larger independent set than the largest seen so far, then \\
+         Record the size of S as the current maximum \\
+     Endif \\
+  Endfor \\
+The running time of this brute-force algorithm is O(n²2<sup>n</sup>).\\
+Another example is when we have to find all ways to arrange //n// items in order,where we end up with a running time of //n//!; and the Traveling Salesman Problem.\\
+=====Sublinear Time=====
-It's the running time of any algorithm that splits the input into two equal-sized pieces,solves each piece recursively and then combines the two solutions in linear time.
+This running time appear when we have to query the input, the goal being to minimize the amount of querying that must be done.\\
+Example: //binary search//. It's total running time is O(log//n//) as we encounter successive shrinking of the search region.\\
+This section was easy to read, and the material within it were all familiar. I give it a 9/10.