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

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 ...

Shell Sort

Today I spent a little bit of time researching the "Shell" sort. I wanted to post a few notes about the Princeton Algorithms Course's implementation to help me solidify my understanding. First, a little tidbit. When I first heard about this algorithm, I thought it had something to do with shell games. Turns out a man named Donald Shell discovered this method of sorting, whence the name. The Algorithms book gives the following explanation (Sedgewick and Wayne, Algorithms, 4th ed., p. 258): The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values o...

Cash Register Algorithm

Goal: Given a price, cash tendered, and two dimensional array of change ordered by denomination (pennies, dimes, quarters, etc.), return an array of exact change. Exceptions: return "insufficient funds" if there isn't exact change; return "closed" if exact change is equivalent to the contents of the array; return a warning if the price is greater than the cash tendered. Analysis First, check the difference between the price and cash tendered. If the price is greater than cash tendered, return an error. If the price equals the cash tendered, no change is needed. From this point, we assume the price is less than the cash tendered. It helps to consider a simpler case where the cash tendered and the change on hand is all pennies and dimes. You could proceed like this: (1) see if all of the change can be given in pennies. If it can't (2) see if the remainder can be made up with dimes. We could get the following cases: A. All your pennies and som...

Coding Journal

Search This Blog