Changes 10/31/14

Ruby:

• Began creating a new thread pool prototype which has separate "download" and "parse" threads, to see how this construct might work in the end program

Website:

• Added audio to the MLG button in the header, try it out!

Changes 10/30/14

UMD Contest:

• Removed the unnecessary function to add missing zeroes to a binary number from ErrorDetection.java.  The functionality of the program is identical, but the code is much less complex.

Ruby:

• Clarified a previous blog post with Mr. Elkner.  I clarified why 20.times.each is redundant in ruby.  20.times returns an iterator, and calling .each on that iterator (or calling 20.times.each) just returns itself (the same iterator) again.

Changes 10/29/14

UMD Programming:

• Worked on 2012 UMD programming contest question 1 (page 3 of the link), which involves error detection for 16 bit integers
• My implementation is here. 
• It actually ended up being an easy problem, the hard part was getting used to the environment.  They had a TryTest file which loaded preset integers and their check bits, but it took a while to figure out that this is how I was meant to test my file
• Since Integer.toBinaryString(int i) doesn't allow you to specify the expected bits, I figured that I should append the missing zeros to the front, so an integer like 42 would return "0000000000101101" and not "101101".  In Python or Ruby, you could just do "0" * (16 - binary_string.length) + binary_string, but there is no way to do a string operation like this in Java as far as I could tell.  
• I ended up writing a whole separate method to prepend the missing zeroes.  
• In hindsight, I actually wasted a lot of time doing this, because only the ones are counted anyway.  Using the method I painstakingly created ends up being functionally equivalent to just calling Integer.toBinaryString(int i).
• Line 11 can be replaced with Integer.toBinaryString() for an identical result.
• I think my performance on this problem would have really benefited from a plan, rather than just jumping right in.  If I had thought about it more, I would have realized that Integer.toBinaryString() is sufficient for finding the number of '1's present in a binary integer.
• 
  

Changes 10/28/14

Java:

• Did the first Stringlist activity, where you are essentially creating a string-like class that follows the ADT list interface.  
• I was unhappy because it forced me to use string concatenation where a StringBuilder would have been much more efficient.  
• The underlying store of character data in the eimacs implementation was a String. Replacing this String with a StringBuilder make much more sense, as the object's implementation of List interface methods like #add() and #set() suggests that the underlying data will be modified quite a bit.
• I also had some trouble during that activity because I couldn't figure out how to get the length of a string.
• This caused me to realize that Java's naming conventions are really counter intuitive, and place too much emphasis on implementation details. 
• To get the length of an array, you call Array[].length;
• To get the length of a String, you call String#length();
• To get the length of a List, you call List#size();
• The reason I took 10 minutes trying to figure out how to get the length of a string was because I falsely remembered that you didn't need brackets after it.  A programmer really shouldn't need to care that the length of an array is a static field while the length of a String is a method, but Java forces you to know that because you must put brackets after #length when calling it on String.
• Then, they take this and just throw it all out when implementing ADT list, making it #size() instead.  I was also falsely under the impression that the naming convention was .length when the length is a static field and #size() when the length must be found using a method, but this is not the case.
• If I was using Eclipse or IntelliJ, I would have figured this out right away, but the eimacs web interface doesn't have tab completion. 

Life Skills:

• Learned how to order pizza online, which I had never done before.  People were kinda mean about it though, and acted like I was stupid for not knowing exactly how to do my first time.
• Learned that the Dominos website shows you coupons, which I guess is to make you feel like you are spending less on pizza.  One coupon cut our order from $30 to $20, and that $20 seems like much less when compared to the $30 than it might if that was the original order price.
• I'm assuming that's what their going for, because it's kinda stupid that you can get the exact same order for a drastically different price depending on whether you click on the site a couple of extra times or not

Changes 10/27/14

Java:

• Worked on some more exercises out of eimacs.  
• Started working on a string class called StringList that implements the interface of a list.  However, it's stupid because they are making it extremely inefficient for the sake of simplicity, so methods such as #add() and #set() use the + operand on a string, so a new string must be returned for each operation.  This makes me not even want to bother writing it, because it's a really stupid design.

Changes 10/23/14 (at NSF meetup) and 10/25/14

NSF Stuff:

• Kevin showed me a really interesting video where a C# API developer wanted to make his interface very understandable, and to do this was trying to avoid returning null in a method to try to read a string from a file.  He felt that this would be inconsistent with the rest of his interface, as other methods that returned strings were guaranteed to not be null.  
• He went through various different approaches, which should hold true (to some extent) in any language.
• What he settled on was returning a Maybe, a collection guaranteed to have either 0 or 1 elements: 0 elements if the file couldn't be read, and 1 if it could, where the element was the string.  This way, he could write code to handle a case with 0 elements much more fluidly than just having a null check.
• I also learned some stuff about C#!
• I guess the string data type is a primitive, because it was written as "string" when declaring the return type for his methods.  If my memory is correct, I think you can write it as String as well.
• I also learned about the out parameter in C#, which was used in one of the approaches to the problem, albeit one that the guy in the video didn't like.  It's still useful to know that you could have a specific variable be modified by a separate method, though.  I think that's pretty cool.

Ruby:

• Updated code and committed to repo.
• Fixed ThreadPool#join_all so that it works correctly.
• Now, when called, it sets the finished flag to true, then does one of two things:
• If there are still elements in the task queue, Thread#join is called on each of the worker threads.  Since the finish flag is now true, each worker thread continues to work as normal, but will abort once it completes a task and finds the task queue to be empty.  Once all worker threads have completed tasks and found the queue to be empty, the #join_all method will release the lock on the thread it is called in (the main thread, most likely) and the program can continue on.
• If the task queue is empty when #join_all is called, ThreadPool#kill_all is called, which terminates all worker threads.  This prevents a deadlock where all the threads are waiting on the queue already, and therefore never check to see that the finished flag has been set to true.
• I also cleaned up some things in the code, and learned some stuff along the way!
• I had a while loop that was something like
  

  int i = 0
  while i < 20 do
    ...
    i+=1
  end

  However this is very un-ruby like.  I changed this to be
  

  20.times do |i| 
    ...
  end

  which is much cleaner and easier to read.  In doing this, I also realized that I had code that read:
  

  some_integer.times.each_with_index do |i|

  which is just awful. It can be rewritten with the exact same functionality as

  some_integer.times do |i|

  . I'm not sure why I thought I needed to call #each on that, let alone #each_with_index! (If #each is redundant, #each_with_index is doubly redundant because you are already using the integer as an index, so getting the index of that index makes no sense)

Changes 10/23/14

Java:

• Finished lesson on LinkedLists.
• It was informative, they showed how adding a ListNode#getPrevious method and tail variable allowed much faster access to elements more than halfway into the list, since the list could now be iterated both backwards and forwards.
• Learned about iterators, which optimize the traversal of lists based on what kind of list it is.  For example, a LinkedList iterator prevents you from needing to call LinkedList#get(i) when traversing, since #get() is an O( n ) operation.
• For each loops in java (ex: for (Object o : list) ) actually use iterators when traversing
• Learned about ListIterators, a subset of iterators that add more methods like #previous(), #add(E x) which adds at the current iterative position, and #set(E x) which sets the current item to x.  E is a generic type, meaning that the user sets the actual type when creating the list.  As an example, LinkedList<String>() would cause E to be a String.

Changes 10/22/14

Java:

• Read more on eimacs about ADT interfaces in Java.  The curriculum is focusing on LinkedLists and their implementation.
• They are now talking about adding a getPrevious() method to each node in addition to getNext(), which will allow you to traverse the List both backward and forward.  The drawback of this would be a larger memory footprint.

Changes 10/21/14

Life Achievements:

• I managed to shut down Aki's computer using only my face.  I pressed the power button with my finger to open the shutdown menu, but he grabbed my hands.  I used my nose to push the down arrow twice and then the enter key, which selects the standby option.

Java:

• Read more in the Data Structures and Abstractions with Java book
• Started reading about big O in the ADT list implementation.
• Commented my own ADT Linked List implementation with run times.
• Separated the LList tests into a separate file.
• Had a good discussion about problems with Java's implementation, such as the fact that it is written by a corporation and therefore doesn't place any trust in the programmer

Ruby:

• Removed the condition variable wait from threading_queue_pooled.rb
• The condition variable allows the programmer to sleep a thread while waiting on a resource from another thread.  Once the resource is available, the #signal method is called, which releases the lock on one of the threads waiting on the variable. 
• However, I realized that I actually don't want this in my case, because Queue#pop already sleeps the thread when empty, making the condition variable redundant.  Additionally, the ConditionVariable#signal method doesn't do anything if the condition variable isn't currently causing the thread to wait, so if it is called when the thread is parsing stuff it is completely ignored.  Therefore, the threads always ended up waiting forever, because each element pushed to the queue would only be signaled once, and if that signal happened to be ignored, the condition variable would continue to pause the thread, even though there were more tasks in the queue.

Changes 10/20/14

Title:

•   public int firstDuplicate( int[] a )
    {
      int y = -1;
      for ( int i = 0 ; i < a.length - 1 && y == -1 ; i++ )
      {
        if ( a[ i ] == a[ i + 1 ] )
          y = i;
      }
      return y;
    }
  

• I've never seen an exit condition within the boolean of a for loop, which threw me off for one of the quiz questions for eimacs.
• This function could be simplified by removing the y variable and simply returning i when a[i] is found to equal a[i+1]
• I also was reminded that big O notation refers to asymptotic behavior, so a function with points (0,0), (1,1) (2,4) and (3,9) could still be O(n), because big O deals with behavior of large values for n

Changes 10/17/14

Java:

• Where the summation identity n(n+1)/2 comes from:
• If you have a sequence 1 + 2 + . . . + n - 1 + n, if you begin with the first and last terms and move inward, you will find that each of these adds to n + 1:
1. 1 + n =  n+1
2. 2 + n-1 = n+1
3. 3 + n-2 = n+1
• So you end up adding (n+1) n / 2 times, because each (n+1) accounts for two elements (one from each end), and therefore there are 1/2 * n instances of (n+1).

• I also tried to understand where the summation identity n(n-1)/2 comes from
• If you have a sequence 1 + 2 + . . . + n - 1, if you begin with the first and last terms and move inward, you will find that each of these adds to n:
1. 1 + n - 1 =  n
2. 2 + n-2 = n
3. 3 + n-3 = n
• But you only have (n-1) of these terms, which is where the n-1 comes from.  Then, like the above identity, you have to divide by 2, so you get a final identity of (n-1)n/2 or n(n-1)/2

Changes 10/16/14 - NSF Meetup

NSF Meetup:

• Talked with Kevin and another guy (can't remember his name, sorry) about threading.  Kevin suggested that the threads shouldn't be directly popping off of the queue, but instead be interacting with a middleman.  However, I'm not sure that this is necessary, as this object (as I imagine it, at least) wouldn't really be adding any functionality, but instead would just act as a redundant intermediary between the threads and the queue.
• We also talked about my problems with ThreadPool#join_all.  I learned that the ConditionVariable#broadcast method will wake up all the threads waiting on it, as opposed to ConditionVariable#signal, which wakes up only one.  However, since Queue.pop already pauses the thread, I'm not sure that my ConditionVariable is even necessary
• I also talked more about what I want to do in college.  I said that one of the reasons I don't like the math-heavy portions of programming is that I don't want to feel like a burden on anyone else.  In college, I would have professors whose whole job is to make sure that the students understand the information.  In high school, though, neither I nor my teachers have time to do this type of thing.

Changes 10/16/14

Ruby:

• File in its current state
• Today I worked on testing how the ThreadPool handled extreme conditions, such as a long list of tasks or a large number of threads.  The code I've written seems to handle these cases well.
• When I started trying to implement #join_all and #kill_all methods for the thread pool, I ran into some difficulties
• For #join_all, the intended behavior is for each thread to complete the current task, all the remaining tasks in the queue to be completed, and once these two conditions are met, for all the threads to stop.  However, since each thread is an infinite loop of checking whether there is anything to pop off the tasks queue, simply calling #join on each thread (the current implementation on line 31) will result in a deadlock because the none of the threads ever actually finish
• I'm not sure how to remedy this.  It seems that calling #join_all should stop the queue from accepting new tasks, allow each thread to continue as normal, and once the queue is completely empty, allow all threads to finish but prevent them from looping back into the waiting state (waiting state would occur on line 12).  This is quite a complex behavior, and I will have to put some additional thought into how it should be implemented

Why I like programming:

• Kevin asked me to write about why I like to program, in order to figure out what college and career paths might be good for me.
• I enjoy programming because I love creating unique and interesting things.  Programming is really cool because your creations actually do something; they work to achieve a task that you as the writer and designer have set out to complete.  I enjoy the feeling of writing a section of a program so that it fulfills its obligations and is well designed.  I also like the problem solving aspect: programming would be boring if everything were easy.  However, I'm always worried that I will never figure out whatever problem I happen to be stuck on at the moment, and this feeling of hopelessness can take away from the enjoyment quite a bit.  One of the things that drives me away from the more mathematical side of programming is the difficulty I have understanding it.  If I were to focus on the mathematics behind algorithms, I would need a good teacher there to answer my questions.  I do get this type of help in Advanced Topics when I need it, and I would expect that college professors would be able and willing to help me if I take these types of classes in college.
• Sorry if that was hard to read or understand, it was sort of a brain dump.  Let me know if you have any questions!

Changes 10/14/14

Ruby:

• File in its current state
• Got a better understanding of mutexes and condition variables by playing around with the code
• Mutexes ensure that only one thread at a time executes a critical section of code, while condition variables can temporarily disable a mutex upon receiving a signal.
• This allows me to have a mutex around the statement which pops an item off of the queue, but temporarily release that mutex when a new item is added to the queue
• I also realized that I had an error in my logic.  I was creating blocks of code to be executed with an incrementing variable saved in the block.  However, blocks don't store their variables' values, but instead evaluate them when they are called.
• I was doing

  i=0
  loop do
    block = lambda { i }
    queue.push(block)
    i+=1
  end

• However, by the time the block was called, the i variable had already changed from what I expected it to be

Changes 10/9/14

NOTE: This is Thursday's post.  Friday's post is below this.

Stuff:

• Watched pyCon talk about a history of Javascript as told by someone in the year 2035.  It was really interesting, and I learned a lot about how computers worked, especially in regards to memory addressing.
• I realized that using WordNet for word replacement isn't going to be as easy as I thought, because words like "went" which are past tenses of verbs aren't included in the base dictionary.  It seems like there is a way to convert "went" into "go", but I will have to look into that further.  In addition, determining what part of speech a word is can be tough.  For example, in the sentence "I go to the store", go is interpreted as a noun, a Chinese board game, rather than a verb.  I think this might be too complex of a project to work on in high school, especially at the level of commitment I'm willing to put into it.

Changes 10/10/14

NOTE: This is Friday's post.  Thursday's post is above this.

Ruby:

• Completed a rudimentary thread pool that takes tasks and delegates threads to complete those tasks
• I'm sure it's not quite thread safe, and I'm not sure how scale-able it is in it's current form to use in a real program.

Other:

• I'll think about Kevin's email over the weekend and answer it on tuesday.

Changes 10/8/14

Java:

• I finally realized why the equation n( n + 1 ) / 2 comes up so much in measuring efficiency of algorithms.  It is the identity of 1 + 2 + . . . + n.  So for algorithms that have multiple loops, this comes in handy, because things tend to increase from 1 to n.
• For example, in the algorithm:

  sum = 0
  for i = 1 to n
  { 
    for j = 1 to i
      sum = sum + 1
  }

• In this image I wrote out what the algorithm would do when n = 5.  I then counted up the number of additions and assignments (which was something they did in the textbook), and saw that the number of assignments matched up with what the book said.  They found that there were 1 + n(n + 1) / 2 assignments in this loop and n(n + 1) / 2 additions, leading to an overall operation cost of n² + n + 1.  This matches up with what I calculated at the bottom of the page.
• 

Changes 10/7/14

Ruby:

• Replied to comment asking for more information about Avdi Grim's videos

Java:

• Started reading Data Structures and Abstraction in Java's section about big O notation.  So far they seem to do a better job of explaining than either of the other two resources I used.  One thing I really liked about it was that when they introduced the concept of algorithms of varying efficiency to accomplish the same task, they gave examples and then broke those examples  down into their speeds based on the number of calculations done.
• I still don't quite understand how they got n(n+1)/2 as the number of additions in the algorithm:

  sum = 0
  for i = 1 to n
  { for j = 1 to i
      sum = sum + 1
  }

• Mainly, I don't really understand how they are calculating this.  I guess the first n would come from the exterior loop, but how is the (n+1)/2 calculated?

Changes 10/6/14

Advanced Data Structures:

• Kept reading about measuring the efficiency of algorithms out of the book on Safari
• I started talking about amortized analysis of algorithms,  but I didn't really understand what they were trying to say. It turns out that the book covers topics beyond the scope of a 2nd semester computer science course, so I'm not going to use it anymore

Ruby:

• Got distracted and started working on a small project that will eventually replace words in a sentence based on their definitions/parts of speech
• Uses ruby-wordnet, which is a really cool lexical(?) dictionary

Changes 10/3/14

Ruby:

• Added a mutex to the @queue.empty logic in threading_queue.rb (lines 22-25), because it probably should be an atomic operation.  This means that if multiple threads are acting on the queue, between the @queue.empty? check and the @queue.pop statement, there should be no opportunity for another thread to modify the queue.
• Started working on a thread pool for multiple parsers/downloaders, but I'm kind of stuck
• I'm not sure what data structure I should store the different parse threads in, and how to make the best use of them.  For example, if there are 20 things in the parse queue and only 10 threads to handle them, how can the program get notified when a thread has completed its task so that I can assign it to the next item in the queue?

Code:

file = @lock.synchronize do
  puts "Waiting for queue" if @queue.empty?
  @queue.pop # this method is blocking if @queue is empty
end

Changes 10/2/14

Java:

• Read more about timing algorithms and big O notation

Ruby:

• Talked to Kevin about threading, watched some videos by Avdi Grim about threading in ruby

Changes 10/1/14

Java:

• Uploaded LList.java to github.  It still needs some formatting work, as the code to exhibit the functionality (The LListTest class) should probably be in a separate document from LList
• The LList class's actual behavior doesn't start until line 64, which probably isn't good.
• I also finished up big O notation in eimacs and started reading about it in the Software Engineering and Development book.  It seems like a thorough explanation so far, but there are still things that they don't explain.  This might just be because I'm jumping into the middle of the book, though.
• 
• The main thing was that in this image, they don't really explain where they get the ~(N^2)/2 and ~(N^3)/6 from.  I'm assuming it's just because you don't know when the if conditional will be satisfied, but it will average out to being near the middle, hence the 1/2.