Changes 11/25/14

Java:

• Changed PythagoreanSpeed program so that it recorded run time in nanoseconds rather than milliseconds.  Tweaked the output slightly
• I set it to do 100 passes at levels 50, 100, 500, and 1000:

• Timings:
  =======(n = 50)=======
  Strategy UMD solution: 0.1177920396039604 ms.
  Strategy UMD solution with Math.pow: 0.7689506237623762 ms.
  Strategy UMD solution with pre-squared array: 0.1406431188118812 ms.
  Strategy pre-squared with hash: 0.23302989108910893 ms.
  =======(n = 100)=======
  Strategy UMD solution: 0.2192501683168317 ms.
  Strategy UMD solution with Math.pow: 1.022717900990099 ms.
  Strategy UMD solution with pre-squared array: 0.15266823762376236 ms.
  Strategy pre-squared with hash: 0.21271922772277227 ms.
  =======(n = 500)=======
  Strategy UMD solution: 17.247952891089106 ms.
  Strategy UMD solution with Math.pow: 126.09220794059407 ms.
  Strategy UMD solution with pre-squared array: 12.931144465346534 ms.
  Strategy pre-squared with hash: 1.3764326336633663 ms.
  =======(n = 1000)=======
  Strategy UMD solution: 132.50848051485147 ms.
  Strategy UMD solution with Math.pow: 1036.010291940594 ms.
  Strategy UMD solution with pre-squared array: 100.51113749504951 ms.
  Strategy pre-squared with hash: 5.131068326732674 ms.

• I didn't add any code to round the output, so past the hundreds place or so those digits are probably not significant
• Pushed changes to github
• I then added an additional algorithm which is O(n²log(n)). All other conditions were kept the same.
• Github link to algorithm

• Timings:
  =======(n = 50)=======
  Strategy UMD solution: 0.12460728712871287 ms.
  Strategy UMD solution with Math.pow: 0.8824542277227723 ms.
  Strategy UMD solution with pre-squared array: 0.09626874257425742 ms.
  Strategy pre-squared with hash: 0.24894374257425742 ms.
  Strategy pre-squared with binary search: 0.14212682178217823 ms.
  =======(n = 100)=======
  Strategy UMD solution: 0.24023814851485148 ms.
  Strategy UMD solution with Math.pow: 1.1169474059405942 ms.
  Strategy UMD solution with pre-squared array: 0.23458126732673265 ms.
  Strategy pre-squared with hash: 0.2551629306930693 ms.
  Strategy pre-squared with binary search: 0.21795613861386137 ms.
  =======(n = 500)=======
  Strategy UMD solution: 17.942774574257427 ms.
  Strategy UMD solution with Math.pow: 126.00360138613861 ms.
  Strategy UMD solution with pre-squared array: 13.263654326732674 ms.
  Strategy pre-squared with hash: 1.4827347524752474 ms.
  Strategy pre-squared with binary search: 5.845997277227723 ms.
  =======(n = 1000)=======
  Strategy UMD solution: 132.98607085148515 ms.
  Strategy UMD solution with Math.pow: 1002.6387993267326 ms.
  Strategy UMD solution with pre-squared array: 100.78688199009902 ms.
  Strategy pre-squared with hash: 5.523412445544555 ms.
  Strategy pre-squared with binary search: 32.41068194059406 ms.
  

• It's interesting that the binary search algorithm is actually faster at low values of n, likely because a hash of the values doesn't need to be created.

Changes 11/24/14

Stuff:

• Replied to Mr. Elkner's comment about infinite meta refresh
• Read Kevin's email, he suggested that I improve the timings program by adding multiple values for n.  I was originally going to do values of {100, 1000, 10000, 100000}, but some of the algorithms seem to take a very long time values of n past 1000 so I'm not sure if I should figure out which ones run in a reasonable amount of time at large N values and run those, or just cut off the test after like 2,000 or so.
• To keep run-time down, I only did three passes for each level, so the average values aren't as accurate as they could be.

• Timings:
  Strategy UMD solution with n 100: 2 ms.
  Strategy UMD solution with Math.pow with n 100: 17 ms.
  Strategy UMD solution with pre-squared array with n 100: 1 ms.
  Strategy pre-squared with hash with n 100: 2 ms.
  ======
  Strategy UMD solution with n 1000: 103 ms.
  Strategy UMD solution with Math.pow with n 1000: 753 ms.
  Strategy UMD solution with pre-squared array with n 1000: 70 ms.
  Strategy pre-squared with hash with n 1000: 13 ms.
  ======
  Strategy UMD solution with n 2000: 797 ms.
  Strategy UMD solution with Math.pow with n 2000: 6051 ms.
  Strategy UMD solution with pre-squared array with n 2000: 637 ms.
  Strategy pre-squared with hash with n 2000: 21 ms.
  ======

• I realized that these numbers were being averaged as longs, and changed it so that they would be divided as doubles.  I re-ran the test:

• Timings:
  Strategy UMD solution with n 100: 2.75 ms.
  Strategy UMD solution with Math.pow with n 100: 19.75 ms.
  Strategy UMD solution with pre-squared array with n 100: 1.75 ms.
  Strategy pre-squared with hash with n 100: 1.75 ms.
  ======
  Strategy UMD solution with n 1000: 94.25 ms.
  Strategy UMD solution with Math.pow with n 1000: 754.5 ms.
  Strategy UMD solution with pre-squared array with n 1000: 70.75 ms.
  Strategy pre-squared with hash with n 1000: 15.0 ms.
  ======
  Strategy UMD solution with n 2000: 725.75 ms.
  Strategy UMD solution with Math.pow with n 2000: 6063.0 ms.
  Strategy UMD solution with pre-squared array with n 2000: 559.5 ms.
  Strategy pre-squared with hash with n 2000: 19.0 ms.
  ======

Changes 11/21/14

Ruby:

• Installed Ruby on Rails to my Ubuntu VM

EIMACS:

• Read more about selection sort

Changes 11/20/14

Web design:

• Migrated website from students.gctaa.net/~ahirschberg/ to ahirschberg.github.io
• I also accidentally created a redirect loop (now fixed), and I was surprised that chrome didn't warn me at all.

Changes 11/19/14

Java:

• Updated weekend blog post about Pythagorean Timings, uploaded timing source code to github
• Started learning about sorts

Website:

• Set up ahirschberg.github.io to redirect to my students website
• Learned about using meta refresh to redirect: code

Changes 11/18/14

EIMACS:

• Took EIMACS test 18, which was on binary and sequential sorts
• I'm finding that the tests put a lot of focus on being able to work through these obscure, pointless algorithms for no clear reason other than to jump through their hoop to get the answer.
• For example:
• What is the value returned by the line newsearch( new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 9 )?

•   public static int newsearch( int[] a, int t ) 
    { 
      int n = (a.length - 1) / 2; 
      int k = 0; 
      while ( true ) 
      { 
        for ( int j = 0 ; j < a.length ; j += n ) 
        { 
          k++; 
          if ( t == a[ j ] ) 
          { 
            return k; 
          } 
        } 
        n--; 
      } 
    }

• And my approach for solving it:
• What does this even do?  Why would you ever want to do this??  They make these complex algorithms for no reason!  The only thing they are testing is my patience by making me work through each iteration, not my knowledge of searches.

Changes 11/17/14

I didn't like this:

public boolean equals( Object o )
  {
    return compareTo( (Item)o ) == 0;
  }

Strictly speaking, by overriding the equals method in this way we are violating the general contract for equals, which is required never to throw an exception. The usual way to avoid this uses theinstanceof operator (which is not part of the Advanced Placement Java subset):

  public boolean equals( Object o )
  {
    return ( o instanceof Item ) &&
             ( compareTo( (Item)o ) == 0 );
  }

EIMACS:

• I don't like this because you would never, ever want to use the first implementation of equals.  Even though they make a note of this, it shows that the philosophy for their curriculum is out of touch with reality.
• Since the AB exam is no longer a thing, eimacs really needs to update their curriculum to stop focusing on the Collegeboard's curriculum.  Operators like instanceof are important in Java, and acting like they don't exist is just plain stupid.  I wish they would just teach instanceof once so they don't have to make a special case every time instanceof is necessary for solving a problem.

---

• Learned more about binary search, and wrote my own, which was kind of tough because I knew roughly what it should look like but forgot what the midpoint should be set to on each iteration.
• I had mid = (high - low) / 2, when it should actually be low + (high - low) / 2, or (high + low) / 2
• Learned that a binary search runs in O( log₂n )