Skip to main content

A Mistake In Binary Search / Making Three Sum More Efficient (Quick Note)

Not a lot of updates for today.  This morning I worked through a little bit of the algorithm course, including coding a very sloppy version of binary search.  The Java...I'm still learning the Java.  But the main problem I was having was my binary search getting stuck in an endless loop.  It was because I was updating my high and low values improperly.  What was happening was that I was setting my low as the average of the difference between high and low, rather than setting my low as the current low plus the average of the difference between high and low.  But once I figured that out I saw a much nicer implementation from the course instructor himself.  The big take away from the lesson, though, was that you can use binary search, which is pretty efficient (I forget exactly how efficient -- something something log N), to make the three-sum algorithm much more efficient.  Instead of searching through loops j, k, and l, for every unique pair j and k, you should do a binary search for an l such that

j + k + l = 0

or, equivalently,

j + k = -l

So that's the big idea that helps make the three-sum algorithm much more efficient.

Other than that, had lunch with some tech leads via networking (TM).  But it was just a meet and greet (with expensive wine that I didn't have to pay for thank the lord).  They remarked in passing after I'd introduced myself, to the man who introduced me, "Oh but we need senior developers!"  Just a little joke -- but I think I took it in stride.  And I talked a lot.  Maybe too much.  At least I got lunch out of the deal...and met a developer who is also reading Das Kapital -- which is something you don't find everyday, I think.

Turning in.  See you next time.

Comments

Post a Comment

Popular posts from this blog

Getting Geodata From Google's API

The apps I'm going to be analyzing are part of Dr. Charles Severance's MOOC on Python and Databases and work together according to the following structure (which applies both in this specific case and more generally to any application that creates and interprets a database using online data). The data source, in this case, is Google's Google Maps Geocoding API.  The "package" has two components: geoload.py  and geodump.py .  geoload.py  reads a list of locations from a file -- addresses for which we would like geographical information -- requests information about them from Google, and stores the information on a database ( geodata.db ).  geodump.py  reads and parses data from the database in JSON, then loads that into a javascript file.  The javascript is then used to create a web page on which the data is visualized as a series of points on the world-map.  Dr. Severance's course focuses on Python, so I'm only going to work my way through ...
Post a Comment
Read more

Compiling and Executing Java Files With -cp

I decided I was going to "man up" and figure out how to compile a java program with an external dependency from the command line instead of relying on an IDE-- the DOS command line, to be more specific. I ran into a few problems: 1.  The external dependency was given to me as a java file.  I experimented compiling it as a .jar, but I wasn't sure how to import a class from a .jar, so I ended up compiling it into a class. 2.  When I tried to run the file, I got an error saying that the class had been compiled with a different version of Java than my JRE.  The Internet told me to check my path variable for Java.  It sure looked like it was pointing to the latest JRE (and the same version of Java as my compiler).  I asked the Internet again and found the following command: for %I in (java.exe) do @echo %~$PATH:I I'm not exactly sure what the syntax of that magic command is (intuitively it's returning the path that executes when I run the "java" com...
Post a Comment
Read more

Quick Find / Quick Union (Connected Nodes)

Setup This week I learned about the "Quick Find" or "Quick Union" algorithm. Imagine an NxN grid of nodes, some of which are connected by lines. A connection can be interpreted as accessibility: if two nodes are connected, you can get from one to the other. Every node is accessible to itself: to get where you already are, stay there. Also, If you can get from A to B, you can go back from B to A. And if you can get from A to B and from B to C, then you can get from A to C. As a consequence, the connection between nodes divides the grid into regions of mutually accessible nodes. You can travel from any node in a given region to any other node in that region -- but not to any nodes outside that region (exercise to reader -- proof by contradiction). The problem has two parts. First, find a way to represent this grid structure and the accessibility relation; second, use your schema to efficiently calculate whether two given nodes are accessible to each other. ...
Post a Comment
Read more