Skip to main content

Diary

  • First day as a TA at Coding Dojo
  • Worked up through the automated testing portion of the Django official tutorial
  • Didn't have time to do any algorithms -- learned about a path-finding problem (2D array represents connections between nodes -- determine whether there is a path from A to B for arbitrary A and B)
    • e.g. for nodes A, B, and C
      • [ [0, 1, 0] , [0 , 0, 1], [0, 0, 0] ]
      • First entry says A is connected to B, second that B is connected to C -- so there's a path from A to C.
      • The connection relationship is not robust.  A can be connected to B without B being connected to A.  It must however in some sense give rise to another relationship that is at least transitive.  If A and B are connected, and B and C are connected, then I can get from A to C.  This does not mean, however, that I can get back from C to A.
      • Initial thought was do something with recursion.  Too complicated.  And what if you have loops?  Now it seems you just need a way to translate this information into a more manageable data structure -- for example the dynamic connectivity data structure.

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

The Jump Algorithm

Meetup Went to a Coding Whiteboard Meetup tonight.  It was pretty great.  One of the leaders was even a CS master's student.  At first, honestly, I felt a little bit frustrated, especially because everyone around me seemed to be using pretty high level concepts / approaches that I wasn't familiar with.  But I found someone and relentlessly talked him through his approach until we both kind of realized there were issues in the problem we hadn't worked out yet.  I guess it just reinforces my feeling that when something seems too difficult, if you can, you need to find someone and force him to explain it to you in terms you can understand.  If the people around you really understand what they're about, they will have no problem and you'll learn a lot (assuming they're patient, I guess).  If they don't, you'll realize you aren't as alone as you thought you were.  Bit of the old Socrates. Problem So imagine you have an array with a bunch of numbe...
Post a Comment
Read more

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...
Post a Comment
Read more