Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section4 [2012/01/24 02:37] – 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:
+          max = a <sub>1</sub>  \\
           for i = 2 to n:  \\
-               if a<sub> i</sub> is greater than max then  \\
+              if a<sub> i</sub> is greater than max then  \\
-                      set max = a<sub> i</sub>  \\
+                    set max = a<sub> i</sub>  \\
-               Endif  \\
+              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 43: / Line 44: @@
 =====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,...
+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²)=====
@@ Line 57: / Line 58: @@
  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=====
+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.