Changes 12/17/14

Did EIMACS Test 21 with Sam.  It wasn't too hard, they had a lot of inserting into priority queues, then popping off the values in various ways.

I guess that in my last post, I didn't realize that the purpose of the exercise they gave me was to re-implement these ADT methods, even though they already existed.  However, that was not made clear, and so someone who is familiar with the ADT (which would hopefully be the people following the curriculum) would probably be confused by the fact that they are overriding this list functionality with identical methods.

Changes 12/23/14 - Javascript

I was ready for an EIMACS test but couldn't take it, so I just worked on JavaScript.  I'm trying to make the shaking elements on ahirschberg.github.io use canvases instead of changing the position of the elements directly, because that is more reliable and less resource intensive for the browser, since only the pixels move within the canvas rather than the browser constantly having to update the object's position in the DOM.

Changes 12/22/14 - EIMACS Sets and Maps, ListQueue analysis

Today, I worked though the set and map unit of EIMACS.  It's been pretty straight forward, and mostly review.

Kevin emailed me after seeing my post about the ListQueue exercise.  He had a couple of questions about the implementation:

1. Can ListQueue be substituted polymorphically anywhere a LinkedList is used?
2. What are the implications of inheriting both interface and implementation
3. Since Java doesn't have private inheritance, should composition be used instead?
4. How does this example play with the Liskov Substitution Principle?

I wasn't familiar with some of the terminology he used, but I tried to answer his questions.  For his first question about substitution, as far as I can tell ListQueue could be substituted for any LinkedList<Object> anywhere in the code, since it is a subclass which changes no functionality.  However, it's important to note that ListQueue hard codes in the fact that it inherits from LinkedList<Object> and not LinkedList<E>, so this object could only be used when the compiler is expecting a LinkedList<Object>, and not, for example, when using a LinkedList<String>.

I'm not sure what the second question means, since LinkedList<E> is a concrete class that implements List<E>.

For question three, I'm first going to write out what private inheritance and composition are.

• Private inheritance is when a child class inherits from a base class, but does not make any of the methods of the base class (including the public ones) publicly accessible.
• Composition is when one object internally relies on other objects.  In this case, composition would make the LinkedList<E> a private object defined within ListQueue, rather than a direct inheritance.

I think composition would make more sense for the ListQueue class, although it's not really clear what the purpose/role is anyway so it's hard to say

For question four, the Liskov substitution principle states that if S is a subtype of T, any expectations for the public interface of T should also be assumed about S, and therefore S could be replaced with T.  This is only true when referring to a LinkedList of Objects.  I'm not sure if that qualifies as adhering to the principle.

Changes 12/18/14

Continued working with Sam on the UMD contest problem 6 - Breaking Vigenere Cipher, which required you to develop a program to find the probable length of the keyword used to scramble a string by looking at distances between repeated patterns of letters.  First, we identified the frequencies of each three letter combination appearing in the text.  Next, for any combination that appeared more than once, we found the distance between the indexes of those combinations.  Finally, we found the values between 4 and 20 (this range was given to us in the problem description) that were factors of the distances we found.  If a factor matched up with more than 90% of the distances, it was added to a results array.  Sam did most of the work on this, and I helped him out with some stuff.  I would like to review the code in more depth so that I can understand his approach a little bit better, though.  I'll definitely read his blog on this topic.

Changes 12/16/14

Today I reviewed my answers for EIMACS test 21. I started learning about stacks and queues. I also came across this really strange exercise. The code started off as: The interesting thing is that this code already works perfectly, since LinkedList already has the methods #add(), #isEmpty(), #peek(), #pop(), and #remove(). However, their solution overrides these methods and re-implements them to have practically identical functionality:I'm not really sure what the point of that was.

I also learned about PriorityQueues, which take Compareable objects and rather than popping the first or last element added, they pop the element with the lowest value as determined by #compareTo().  The way they explained it was kind of weird, but I assume that this type of data structure does have use in actual applications.

Changes 12/15/14

EIMACS:

• Finished learning about quicksort, reviewed big O notation
• Reviewed the Java List interface and some of the concrete classes like linked lists, ArrayLists, and their traversal methods like iterators and ListIterators.
• Took EIMACS test 21, which was on lists and iteration.

Changes 12/12/14

EIMACS:

Looked at the quicksort a little bit more, using their graphical explanation.  Based on my observation, it "locks in" elements to their final resting positions by incrementing the position of a bottom index and decrementing the position of the top index. Along the way, if it finds that an element at a bottom index greater than the pivot element and an element at a top index less than the pivot element, they are swapped.  Eventually, the top and bottom indexes intersect, or cross over one another, such that the top index is less than the bottom index.  At this point, the pivot element is known to be greater than all elements in indexes less than the pivot index and less than all elements in indexes greater than the pivot due to how the elements were swapped.  The pivot element is now in its final position in the array, and the list is then split along the pivot element, and the process repeats recursively.

Sam showed me a cool website which gives a visual of the quicksort (along with other sorting algorithms)

Changes 12/11/14

Stuff:

• EIMACS - Learned more about quicksort.  I'll write more in depth about what I'm understanding/not understanding tomorrow.
• Other stuff - helped Jack with some ATIC mobile site stuff

Changes 12/10/14

EIMACS:

• Took test 19, went over some of the answers

Changes 12/9/14

EIMACS:

Finished up learning about merge sort, and started learning about quicksort. Interestingly enough, a basic recursive quicksort was actually really easy for me to understand, since it was a lot like the merge sort algorithm. However, it's starting to get into the in-place quicksort, which is very complex and confusing. I'm pretty sure I've already gone through this section (I already did EIMACS test 20, which is after this part), but I figure I should probably review it anyway because of its complexity.

Changes 12/8/14

EIMACS:

Today I worked through some more of the EIMACS curriculum. I learned about the merge sort algorithm, which I actually thought was pretty cool. It works by splitting the array in half, then splitting those halves in half and so on. It then merges each fragment back together, eventually sorting the array.

Web Design:

Helped fix the /~atic/ site when viewed on a mobile device by changing the mediaquery from max-width: 480px to max-device-width: 480px.

Changes 12/4/14

EIMACS:

• Did some more exercises, where I had to debug other people's mistakes.  Debugging (or writing) algorithms is something I'm really not good at.  It's just very hard for me to visualize what I'm doing
• I did well on the exercises though

Changes 12/3/14

Java:

• Finished Shut The Box algorithm with Sam, and I think now I understand how it works.  Tomorrow I'll spend some time trying to mark it up.
• Source

Web Design:

• Learned how to import code directly into my blog using github gists.  
• You can do this by going to gist.github.com and typing in code, then copying and pasting the embed script they give you