TADM2E 1.5 - Revision history

Landron: Well defining counterexample

2019-01-21T16:08:23Z

Well defining counterexample

Algowikiadmin: Recovering wiki

2014-09-11T18:22:33Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:16Z

Recovering wiki

New page

First-fit algorithm counterexample:

<math>S = \{1, 2, 3\}</math>
 
<math>T = 5</math>


Best-fit algorithm counterexample:

<math>S = \{1, 2, 3\}</math>
 
<math>T = 5</math>


Largest to smallest algorithm counterexample:

<math>S = \{4, 3, 2\}</math>
 
<math>T = 5</math>

----
Another counterexample:
If <math>t=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.

Using first-fit algorithm (left to right)
{| class="wikitable"
|-
! Item added
! Subset of <math>S</math>
! Sum
|-
| 1
| <math>\{1\}</math>
| 1 < 11
|-
| 2
| <math>\{1, 2\}</math>
| 3 < 11
|-
| 5
| <math>\{1, 2, 5\}</math>
| 8 < 11
|-
| 9
| <math>\{1, 2, 5, 9\}</math>
| 17 > 11
|}

Using best-fit algorithm (smallest to largest)
{| class="wikitable"
|-
! Item added
! Subset of <math>S</math>
! Sum
|-
| 1
| <math>\{1\}</math>
| 1 < 11
|-
| 2
| <math>\{1, 2\}</math>
| 3 < 11
|-
| 5
| <math>\{1, 2, 5\}</math>
| 8 < 11
|-
| 9
| <math>\{1, 2, 5, 9\}</math>
| 17 > 11
|}

Using largest to smallest
{| class="wikitable"
|-
! Item added
! Subset of <math>S</math>
! Sum
|-
| 10
| <math>\{10\}</math>
| 10 < 11
|-
| 9
| <math>\{9, 10\}</math>
| 19 > 11
|}

[[introduction-TADM2E|Back to ''Introduction ...'']]

@@ Line 21: / Line 21: @@
 ----
 <p>Another counterexample:</p>
-If <math>t=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.
+If <math>S = \{1, 2, 5, 9, 10\}</math> and <math>T=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.

@@ Line 1: / Line 1: @@
-&lt;p&gt;First-fit algorithm counterexample:&lt;/p&gt;
+<p>First-fit algorithm counterexample:</p>
-&lt;p&gt;
+<p>
-&lt;math&gt;S = \{1, 2, 3\}&lt;/math&gt;
+<math>S = \{1, 2, 3\}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;T = 5&lt;/math&gt;
+<math>T = 5</math>
-&lt;/p&gt;
+</p>
-&lt;p&gt;Best-fit algorithm counterexample:&lt;/p&gt;
+<p>Best-fit algorithm counterexample:</p>
-&lt;p&gt;
+<p>
-&lt;math&gt;S = \{1, 2, 3\}&lt;/math&gt;
+<math>S = \{1, 2, 3\}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;T = 5&lt;/math&gt;
+<math>T = 5</math>
-&lt;/p&gt;
+</p>
-&lt;p&gt;Largest to smallest algorithm counterexample:&lt;/p&gt;
+<p>Largest to smallest algorithm counterexample:</p>
-&lt;p&gt;
+<p>
-&lt;math&gt;S = \{4, 3, 2\}&lt;/math&gt;
+<math>S = \{4, 3, 2\}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;T = 5&lt;/math&gt;
+<math>T = 5</math>
-&lt;/p&gt;
+</p>
 ----
-&lt;p&gt;Another counterexample:&lt;/p&gt;
+<p>Another counterexample:</p>
-If &lt;math&gt;t=11&lt;/math&gt;, the solution would be the subset &lt;math&gt;\{2, 9\}&lt;/math&gt; or &lt;math&gt;\{1, 10\}&lt;/math&gt; which none of the algorithms found.
+If <math>t=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.
 Using first-fit algorithm (left to right)
-{| class=&quot;wikitable&quot;
+{| class="wikitable"
 |-
 ! Item added
-! Subset of &lt;math&gt;S&lt;/math&gt;
+! Subset of <math>S</math>
 ! Sum
 |-
 | 1
-| &lt;math&gt;\{1\}&lt;/math&gt;
+| <math>\{1\}</math>
-| 1 &lt; 11
+| 1 < 11
 |-
 | 2
-| &lt;math&gt;\{1, 2\}&lt;/math&gt;
+| <math>\{1, 2\}</math>
-| 3 &lt; 11
+| 3 < 11
 |-
 | 5
-| &lt;math&gt;\{1, 2, 5\}&lt;/math&gt;
+| <math>\{1, 2, 5\}</math>
-| 8 &lt; 11
+| 8 < 11
 |-
 | 9
-| &lt;math&gt;\{1, 2, 5, 9\}&lt;/math&gt;
+| <math>\{1, 2, 5, 9\}</math>
-| 17 &gt; 11
+| 17 > 11
 |}
 Using best-fit algorithm (smallest to largest)
-{| class=&quot;wikitable&quot;
+{| class="wikitable"
 |-
 ! Item added
-! Subset of &lt;math&gt;S&lt;/math&gt;
+! Subset of <math>S</math>
 ! Sum
 |-
 | 1
-| &lt;math&gt;\{1\}&lt;/math&gt;
+| <math>\{1\}</math>
-| 1 &lt; 11
+| 1 < 11
 |-
 | 2
-| &lt;math&gt;\{1, 2\}&lt;/math&gt;
+| <math>\{1, 2\}</math>
-| 3 &lt; 11
+| 3 < 11
 |-
 | 5
-| &lt;math&gt;\{1, 2, 5\}&lt;/math&gt;
+| <math>\{1, 2, 5\}</math>
-| 8 &lt; 11
+| 8 < 11
 |-
 | 9
-| &lt;math&gt;\{1, 2, 5, 9\}&lt;/math&gt;
+| <math>\{1, 2, 5, 9\}</math>
-| 17 &gt; 11
+| 17 > 11
 |}
 Using largest to smallest
-{| class=&quot;wikitable&quot;
+{| class="wikitable"
 |-
 ! Item added
-! Subset of &lt;math&gt;S&lt;/math&gt;
+! Subset of <math>S</math>
 ! Sum
 |-
 | 10
-| &lt;math&gt;\{10\}&lt;/math&gt;
+| <math>\{10\}</math>
-| 10 &lt; 11
+| 10 < 11
 |-
 | 9
-| &lt;math&gt;\{9, 10\}&lt;/math&gt;
+| <math>\{9, 10\}</math>
-| 19 &gt; 11
+| 19 > 11
 |}
 [[introduction-TADM2E|Back to ''Introduction ...'']]