Changes 1/30/15 - Firefox OS!

Started working on Firefox OS, which is actually really easy to develop for.  Since it's all web based, it runs very smoothly within firefox and even comes with a built in IDE, right in the browser!

I wrote a quick Hello World app, which was really easy to set up and push to my local emulator.  The hardest part was getting access to the jQuery library I was trying to use.  I assumed the phone would have it built in so that not every app had to have its own copy, but apparently that's not the case.  Once I figured out that I needed to download a copy of jQuery to get access to it, everything went smoothly.  I wrote a quick app that displays some text.

It's really nice that since the emulator is using the browser to render, I can use the Firefox element inspector to alter how my app displays while it is running, which can be really useful for previewing changes

I can also paste my code right into blogger, and with a little bit of tweaking, have my app running embedded in the page!  That's really cool!

This is what it ended up looking like:

World

Changes 1/29/15 - Printing a heap, Firefox phone

                98
        77              83
    63      70      58      62
  18  7   17  30  28  54  10  22

So I got the formatting to work! Sam gave me a hint--his program based the spacing between each node (Such as the spaces between 77 and 83) on the total number of columns available on the terminal. In my code, the spacing between each node is calculated with the expression:
" " * (str_width // (2**level_index))
where str_width is a constant dependent on the columns in the terminal and level_index is the level of nodes currently being iterated over (so for 98 level_index would equal 0, for 77 and 83 it would equal 1, and so on).

The left offset, or the whitespace to the far left of all the nodes, is calculated by dividing the spacing between each node by two:
(" " * str_width // (2**level_index + 1))

This approach works very well, but I wouldn't have been able to figure it out on my own. I guess it makes sense, but I just have trouble wrapping my head around what I'm doing. The only reason I got this to work at all was because I played around with the math without really understanding what I was doing and happened to eventually hit the right answer.  It's really frustrating though because I'm just not good at thinking in this sort of way.

I also got Firefox Hello to work, since we are going to be videoconferencing with some people over at Mozilla at some point in the future.  I started looking at the oneanddone site, but ran out of time.  If we only have one Firefox phone between the three of us, I don't think we all really need to do these though.

Changes 1/28/15 - Heap printing

Worked more on my heap output. So far the best I've gotten it is

                       98
                77            83
        63        70        58        62
   18    7    17    30    28    54    10    22

So the spacing isn't quite right. I've kind of run out of time to blog the past couple of days, I'll make sure to blog in more detail tomorrow about what I've been working on. Sam also showed me his implementation, which I think is going to help with the spacing problems I'm having.

Changes 1/27/15

Today I worked on extending the heaps.py file so that it can print out the heap with proper structure.  It's pretty tough--I got the output to be correct after a while but the spacing is way off, so it still needs a lot of work.

Changes 1/26/15 Heaps

Mr. Elkner gave me a python implementation of a heap to type up and a couple of questions to go along with it.  It was a good exercise because it showed how a regular array can be used to represent values in a binary tree.  EIMACS had talked a little bit about that but getting to actually work with the code was really helpful.  I think I have a good understanding of how the heap is actually built.  The method #heap_down, which swaps elements to ensure they obey the contract of a max_heap was a bit hard to understand at first, but I understand it much better after going through the code line by line to try to understand it.

Changes 1/23/15

Helped Aki with the Bottle Zoo webapp, and did more binary tree stuff.  I started writing a binary search tree implementation in Ruby.

Changes 1/22/15 - EIMACS trees test

Took EIMACS test 24, which was on binary trees and heaps.  I didn't actually understand binary trees until halfway through the test, though.  I thought that they had to be balanced, but they actually don't.  EIMACS did a really bad job explaining this!  I'm definitely going to do some additional reading on heaps and binary search trees.

Changes 1/21/15 - More EIMACS Binary Search Trees

I read more about binary search trees on EIMACS, like how they are sorted as the initial values are appended. It showed a little bit of the behavior of Java's TreeSet class, like the fact that #toString() uses an inorder traversal to output values. Then it started teaching me about heaps, which are structured like BSTs but with a different sorting method. There are two types: a min-heap and a max-heap. Min-heap means that the value at the root of each tree is less than the value of each of its branches, whereas a max-heap means that the root of each tree is greater than the values of each of its branches.

This is a min-heap: each node's value is greater than the value of its parent.

EIMACS really didn't to a good job of explaining complete trees, but I think that in order for a heap to behave correctly it needs to be complete.  This means that the nodes fill from left to right such that there is never a node with a right branch but not a left one, while also keeping greater or equal amounts of nodes on the left as compared to the right.

Heaps can also be represented as arrays, with each level being added successively.  EIMACS also inserts a null value at position zero to make some properties easier to describe.

The above heap would be written as {null, 1, 2, 3, 17, 19, 36, 7, 25, 100}, and would have the following properties:
The index of a given node's child elements will be at double that node's index and, if a right node exists, double that node's index + 1.
The inverse is also true: a given node's parent element can be found by taking (int)(node index / 2).

This seems like it is definitely useful!  EIMACS gives priority queues as an example where heapsorts are often used.

An algorithm that organizes nodes to create a min-heap does the following:
Each value is added as a new leaf to the bottom row or starts a new row if the current bottom is full. If the new value is found to be greater than or equal to the parent value, then the insertion is complete. Otherwise, the values of the new node and the parent node are swapped.

Changes 1/16/15 - Recursion and binary search trees

At NSF last night, Kevin and I talked about recursion.  He emailed me after my blog post about recursion in binary trees and mentioned that recursion is also evident in linked lists, since they are a chain of the same type of object linked to each other.

Unfortunately I didn't take a picture of his diagram, but this image sort of shows the same thing: each node links to another node, or null.  I'm still feeling a little shaky on his explanation, because I thought recursion was more of a strategy for an algorithm rather than inherently in a data structure.

Sam also wrote up and explained a cool C file that emulates the car, cdr, and cons LISP functions in C, so I have a better understanding of what those actually are doing now.

This program outputs

6 7 8 3 2 1

I also got further in the EIMACS binary search tree curriculum. They still haven't explained what makes a balanced search tree balanced, so I'm a little confused as to the significance. I'm pretty sure it's because that way you can guarantee that the sorted tree has the elements where you think they are, because otherwise it could be arbitrary (I know that's vague, I'll try to expand on that on Monday but I'm running out of time.)

Changes 1/15/15 - EIMACS and Open closed principle

I finished up the portion of EIMACS about traversing binary trees and started searching algorithms.  Binary search trees are trees where the value of the left node is less than the root value, while the value of the right node is greater than the root value.

Kevin also asked me to look at the Open/closed principle of object oriented programming, which states that software entities should be open for extension, but closed for modification.  Basically, inheritance allows a programmer to add their own code to a base class without modifying that base class.  That seems pretty simple, but I'm sure I'm not thinking of all the implications that brings.  Also, it's interesting that Ruby doesn't seem to adhere to this principle because you can modify essentially any classes you want, even if they are base classes.

Changes 1/14/15 - UMD Contest 2014 problem

Today, Sam and I worked on 2014 UMD contest problem number 4, which is called Minion Walk.  It involves checking if there is a path from the top left of a grid of squares to the bottom right using a flood algorithm.  The algorithm checks if the space it is currently in is empty, then makes a recursive call to each adjacent space, eventually traversing all possible spaces.  It was actually pretty easy for Sam and I, since Sam already had experience with this sort of algorithm.

Kevin also emailed me and asked me to look into the Open Closed Principle of object oriented programming, which I didn't get a chance to do today.  I'll be sure to look into that tomorrow.

Changes 1/13/15 - EIMACS Trees

Today I learned about binary trees, which are a lot like LinkedLists (in the implementation EIMACS is using) except that they have two "next node" values instead of just one: a left and a right value.  This means that pretty much every method I've had to code for the exercises so far has been recursive.

Changes 1/12/15 - Liskov corrections, Bottle stuff

After the post I made on Friday (1/9/15), Kevin emailed me to clarify some Liskov Substitution stuff.

First of all, shout out to Kevin for reading my blog:


He wanted to make sure it was clear that you need to look at the specification rather than the implementation of a method in order to verify that a subclass method does not violate the LSP.

Kevin gave three examples of the same method with different specification. In the first two examples, #get_number has been stubbed out (given a return value that fits its expected behavior without actually containing any functionality). We need to look at the specification for the method, not the implementation, for clues on obeying LSP.

Implementation 1:
In this example, it is easy to define a subclass that obeys the LSP - you just need to implement it such that the range of possible outputs for #get_number is less than or equal to the numbers 0 to 100.

Implementation 2:
Just like in Implementation 1, a subclass overriding #get_number would need to take into account the specification given in the method.

Implementation 3:
In this example, it is impossible to determine what is expected of a subclass' overridden method--there is nothing to go off of. This is very bad! Obviously the method is expected to be overridden but offers no other information.

Also, for the record, I didn't come up with all this on my own, I pretty much just paraphrased Kevin's email.  I think I definitely understand the concept better now.

He also put this in the email, and I thought it was worth sharing:

---

Today I also helped Aki and Dylan with some Bottle stuff. They're trying to push HTML form data into an sql database using Bottle, which is something I did in math-drill last year. I showed them my code as an example, but unfortunately it's a bit more complex than what they need. My code actually generates the form using python, which isn't something they need to worry about and just makes it harder for them to understand. If they need my help, hopefully they'll ask...

Changes 1/9/15 EIMACS and more NSF meetup stuff

Sam, Finn, and I took EIMACS test 23, which was on Sets and Maps.  It was pretty easy.

At NSF, Kevin and I also talked about something he had asked earlier, which was about the EIMACS ListQueue class.  This is the earlier blog post I had written.  When I was thinking of the answers to his questions, I was assuming that the implementation of ListQueue was empty (the first implementation I listed in this post), whereas Kevin was thinking of the second implementation listed in that post, where methods of LinkedList are actually overridden.

It turns out that the class, even with the listed overriden methods, does fulfill the Liskov substitution principle, because the re-implemented methods have the exact same functionality as the parent methods as defined in LinkedList.

Kevin also mentioned that in order to fulfill this prinicple, the range of valid inputs for your method should be larger than that of the method you are overriding, while the range of outputs should be the same or smaller than the overridden method.  This prevents code that is using your object as though it is its superclass (for example, calling code expecting a LinkedList<Object> and passing in a ListQueue) from being "surprised" by differences in functionality.

A concrete example of this:
The NarrowNumberGenerator has a narrower range of outputs (0 to 5 inclusive) than its parent, so a class which uses a NarrowNumberGenerator in place of a NumberGenerator doesn't need to worry about the differences in behavior.  All the outputs of NarrowNumberGenerator are also valid outputs of NumberGenerator.

Changes 1/8/15 - UMD Contest and Laptop Issues

I was having laptop issues in class today.  Since my laptop is really a tablet, it has a battery in the tablet itself and a second battery in the keyboard.  The keyboard battery was at 0% and the tablet would try to switch to the keyboard battery and instantly shut off since it had no power.  Jack helped me out by removing the tablet battery, which let us see a boot message that said the power adapter I was using wasn't outputting enough voltage for the computer.  So thanks, Jack.

Also, at NSF I talked with Kevin and Sam about UMD problem #5.  The solution given makes use of a data structure called a directed graph, which can be used to find the shortest path between data points.  This is important because the problem asks you to predict the outcomes of battles between Avengers (and Catwoman, I mean come on what were they thinking? Get it straight, UMD!) based on their past battles.  So basically, if Thor beats Loki and Loki beats Catwoman, the algorithm should show Thor beating Catwoman.  Directed graphs make this possible.

Tomorrow I will try to look into the code behind the UMD solution, as well as take EIMACS test 23.

Changes 1/7/15 - UMD Contest problem

I'm starting to piece through number 5 on the 2012 UMD contest problems.  First of all, Catwoman is not a Marvel character, so I don't know why they're fighting her.  I also don't know how to do the problem.  It's just really hard to visualize how to do what they are expecting me to do.

I'm focusing on doing the easier stuff first, so right now my code can determine the winner if the two combatants have already directly fought.

Changes 1/6/15 - canvas_spritesheet optimizations

Since the second half of the Snoop Dogg gif I'm using for my spritesheet is simply the reverse of the first half (in order to make it loop the creater put part of a video back to back with the reverse of that video), so the spritesheet can be cut in half by setting the frame counter to increment up to the final frame, then decrement back down to the first frame.

canvas_spritesheet.html

Changes 12/24/14 - 1/4/15 (Winter Break) - Javascript Canvas stuff

On my website, ahirschberg.github.io, if you click the button that says "Wot's this, m8?", images and gifs will start to shake across the screen.  However, these elements are shaken by updating their positions on the page, which is pretty inefficient when being done over and over again for a large number of elements.

Last year, I had worked on a page that tested the basics of shaking an image using a canvas.  It wasn't very impressive and didn't really capture what I was trying to do.  Over winter break I started to work on a page that properly shook the images within the canvas.

canvas_shake2.html

It generates a set number of canvases (at the time of writing it's 10, but on the actual implementation it will probably be higher).  Each of these canvases is assigned a random image from a pool of possible images.  A tick function called using the javascript setInterval() function updates the canvases every 30 milliseconds. Each frame loads the image at a different position:

This method of changing an image's position is much more efficient than my previous method of actually creating an image element and directly updating its position.  For example, my computer at home can handle about 50 canvases all shaking elements, while it would start to lag long before that number of elements was reached directly updating image positions in the DOM.

Please try out the different buttons on the page and see what they do!

The main limitation of this method is that gifs no longer render past the first frame because javascript doesn't offer an easy way to choose which frame in a gif is drawn to a canvas using the drawImage() method.  A lot of the shaker elements are gifs, so that's a big problem.

canvas_spritesheet.html

To work around this limitation, I started working on a canvas implementation that would create an animation using a spritesheet, an image with all the frames of a gif lined up like a film strip.

In order to help the viewer visualize this, I added a canvas below the main animation which illustrates the bounds of the spritesheet currently being drawn to the canvas.

Please try out the different buttons on the page and see what they do!

Also, if your sound isn't on, turn it on!  I set up the javascript so that it seamless(ish)ly loops a part of a song.

For both of these pages, there's a link to the proper github page where you can see the relevant code with proper syntax highlighting.