Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section4 [2012/01/24 13:07] – [Linear Time O(n)] admin
+++ 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 \\
-**Professor Sprenkle's test**
-<code>
+Merging Two Sorted lists
-algorithm:max = a <sub>1</sub>
-          for i = 2 to n:
-               if a<sub> i</sub> is greater than max then
-                      set max = a<sub> i</sub>
-               Endif
-          Endfor
-</code>
-  * Merging Two Sorted lists
- algorithm:
+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 75: / Line 65: @@
 algorithm:\\
-for each set S<sub>i</sub>  \\
+ for each set S<sub>i</sub>  \\
     for each other set S<sub>j</sub> \\
        for each element //p// of S<sub>i</sub>  \\
@@ Line 84: / Line 74: @@
        Endif  \\
      Endfor \\
- Endfor  \\
+  Endfor  \\
 =====O(n^k) Time=====
@@ Line 93: / Line 83: @@
 Algorithm: \\
-for each subset S of k nodes \\
+  for each subset S of k nodes \\
-    check whether S constitutes an Independent set \\
+      check whether S constitutes an Independent set \\
-    if S is an Independent set then \\
+      if S is an Independent set then \\
-       Stop and declare success \\
+         Stop and declare success \\
-    Endif \\
+      Endif \\
-Endfor \\
+  Endfor \\
-if no k-node independent set was found then  \\
+  if no k-node independent set was found then  \\
-   Declare failure \\
+     Declare failure \\
-Endif \\
+  Endif \\
@@ Line 109: / Line 99: @@
 Algorithm: \\
-for each subset S of nodes \\
+  for each subset S of nodes \\
-    check whether S constitutes and independent set \\
+     check whether S constitutes and independent set \\
-    If S is a larger independent set than the largest seen so far, then \\
+     If S is a larger independent set than the largest seen so far, then \\
          Record the size of S as the current maximum \\
-    Endif \\
+     Endif \\
-Endfor \\
+  Endfor \\
 The running time of this brute-force algorithm is O(n²2<sup>n</sup>).\\