Tag Archives: algorithms

Notes from 27 October, 2015: algorithms, panicccc, bike-ifying my weather app

Earlier start to the day! I even did some chores at home, and saw the sunrise. (It was slightly foggy and ethereally beautiful.)

The Coursera Algorithms course continues to walk that line where it’s alternately awesome and completely baffling. It’s fine. This is fine.

Started in on quicksort today — partitioning is so simple it seems like it shouldn’t be so cool. And yet.

I feel like I have a reasonably good grasp on comparing Big-O complexities of various algorithms (like O(n log n) vs. O(n)), but DETERMINING the Big-O complexity of a given algorithm is something that I understand only temporarily, and then it slips away again. (I only know that merge sort is O(n log n) because I accidentally memorized this.)

My mom (who teaches programming) says Big-O is one of those things that you get, and you are so relieved, and then you learn more and it becomes SO HARD, and then you learn more and things start to click again. I think I’m in the middle part.

Finally headed back to Concordia University’s library for afternoon studying. (Also picked up my community library card!!) Decided that panicking for several hours over not being able to build a database from super messy data is not productive, and also it makes sense that I do not yet know how to do something I haven’t done before. (Panicked about other things instead [work-related things].)

Instead of panicking about the database that isn’t (yet), I headed back to my little weather app. I added in some temperature stuff, which I’ve been way more interested in since the answer stopped being “it is hot all the time, except when it is DANGEROUSLY hot and the air is poison.”

I started a new branch to do something I’ve been excited about since well before I started this project — I’m going to gather together whatever information seems most relevant for bike commutes so I can call up that info with a single command. (Maybe I’ll fling it in a mobile app someday, so I can call it up with a single tap.)

How much will this rule? I’ll just get to be like, “yo computer, I’mma bike today,” and it will give me relevant data.

From my preliminary notes, here’s what I want to include, with aspirational stuff in italics:

  • precipitation, if there’s going to be any today (later: narrow this to commute hours, so just morning/evening)
  • humidity, if it’s high (also decide what constitutes “high”)
  • temperature, if it’s “low” or “high” (decide what constitutes low/high) (later: only display if it’s very different from yesterday)
  • visibility, if it is (or will be) pretty low at some point today
  • sunset time, if it’ll be before I expect to head home
  • apparent_temperature (Dark Sky defines this! how rad), if it’s very different from the actual temperature. I’m fairly certain I care more about THIS measure of temperature than the technically-true one, unless there’s a good reason to pay more attention to actual-temperature (like…danger?). Haven’t thought of one yet, though.

Maybe I’ll do something really weird like make up a “biking pleasantness score” or something so I can be all, “ugh, today’s gonna be a 12” or “oh wow, I just HAVE to bike today; it’s a 47!”

Notes from 19 October, 2015: remembering that things exist, inertia, OpenHatch, man page humor

It’s Monday! I am READY FOR THIS (I am sleepy, but I have coffee, and I did get out the door in plenty of time to have a full day AND enjoy some daylight). I am not feeling totally awesome, but am trying to ignore this.

I am officially almost lost, but I recognized literally non-zero concepts in my algorithms course. I know about Big-oh notation! Today I also learned about Big Omega, Big Theta, and Big Brother notation.

Just kidding about the last one!


 

Had a kind of rough momentum-crushing lunch break (but a deliciously weird burrito). Took a short nap, which sort of helped, mostly because it gave me a deadline for getting up and going again. Took some ibuprofen in the hopes that it would decrease the amount of space that “pain” is taking up in my attention. It maybe helped?

Remembered that workfrom.co exists and learned that there’s a new tea café not that far away from here. It is like some sort of light-filled hipster dream space, filled with white walls and plainly finished wood and mason jars and succulents in tiny pots, so I wanted to be Too Cool for it…and instead, I kinda dig it. I’ve been kind of blown away by the gluttonous uses of spaces here since returning from New York (so much space unused! how can you afford that?), but sometimes that feeling is really good.

Decided that rebuilding inertia was more important than working towards graphing my UP data today, and tried poking through YourFirstPR tweets (it’s Hacktoberfest! I still haven’t submitted any PRs!), then remembered that OpenHatch exists and went there instead.

I’m practicing using my newly installed (as of Friday) wget, and I made my first tarball (!), and I read a ton of the man pages for tar,  and boy howdy is there a lot there. Knowing how to search for things in vim/vi has been SUCH a huge boost in reading man pages. (Don’t know how? In vim, or in a man page, type / and then your search. [Since you can do really complicated searches if you want, searching for . will not search for a literal period — it’s a wildcard! — but letters and many kinds of punctuation should work as you expect.] Type n to find the next instance of that term, or N to find the previous instance. Bask in your wizardry.)

In further man page adventures, patch has (surprise) another long one, but check out this gem:

Assume  that  this  patch  was  created with the old and new files swapped.  (Yes, I’m afraid that does  happen  occasionally,  human nature being what it is.)

The -s flag is also basically how I work as a human being. I will leave it as an exercise for you, the reader, to figure out what that is.

ALSO learned about diff, which is one of those things that people have mentioned in context a lot, as if any garden-variety nerd toooootally knows what that is. “Yeah so like you just do a diff on it; it’s super easy.” Well, I didn’t. I mean. I got the concept. But apparently it’s a command-line tool. To generate these files that tell you the difference between this file and this updated/fixed one. Which rules.

diff -u nutty-pancake-original.txt nutty-pancake.txt

On the OpenHatch patching mission, they’re like, “yeah use the -u option, because this creates a unified diff (“the universally preferred flavor of diff output”). So it’s just diff, that flag, the original file, and the newly updated file. (Having used git a bunch, it took me a second to realize these files had to be separate.)

Also practiced using more grep to find and destroy every aubergine, regardless of capitalization. Turns out Digital Ocean has a nice little grep reference here.

Whew. I feel like I got through some stuff today! It’s still in short-term memory, but that’s a fine place to start.

Notes from 16 October, 2015: algorithms resources, Apple Store win

Started the day flipping through Mathematics for Computer Science (amazing old link here — it has the very incredible “What is a Proof?” introduction to Chapter one; a more recent iteration of MfCS is here). It was mentioned by the Coursera algorithms course I’m trying out, so, hey! I have indeed already been lost by some of the math stuff in CLRS, so it seems like having a concise-ish reference on hand will be…handy.

Really, all this algorithms stuff seems to be a knowledge rabbit hole. “But I need to learn more math!” I hear myself say. I took calculus in high school (it was fine, and then it was a disaster), and then again after I dropped out of college because it seemed like fun (hello, I was raised by engineers!), and then…that was a very, very long time ago at this point. I ran into trouble trying to use my phone calculator to compute logs of things yesterday. So. Fortunately I know some excellent math nerds, and now I have actual things to ask them about.

Also! Do you love algorithms, too? Or would you maybe like to? Maybe you would just like to “Netflix and chill” with some algorithms. The animated (i.e. lively, not a cartoon) lecturer of this Coursera course has some recommendations, which I’ll share here for fun.

Aside from the Eric Lehman and Tom Leighton document, there are also books! The instructor gives his four favorite algorithms books, the second and fourth of which are available for free (!) online:

  • Kleinberg/Tardos, Algorithm Design, 2005.
  • Dasgupta/Papadimitriou/Vazirani, Algorithms, 2006.
  • Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms, 2009 (3rd edition).
  • Mehlhorn/Sanders, Data Structures and Algorithms: The Basic Toolbox, 2008.

Also there’s a brief “you may be rusty on this stuff” explanation of log base 2, which is just, like, plug a number n into your calculator, then divide by two. Then keep dividing by two until the number is smaller than one. And the number of times you needed to do that is the log. WHAT. Awesome.


 

Trying to learn stuff and immediately apply it is still kind of terrifying. Maybe just with Postgres.

Also I had a way shorter afternoon than I intended, because I ended up going into the Apple Store to get my phone fixed. (There’s this thing with some early iPhone 5s, and I do indeed have a very early iPhone 5, and the sleep/wake button on top stops working, and it’s…not great. The fix requires sending the phone away, where they have to take EVERYTHING out, and you have to wipe your phone beforehand, so you have to have a recent backup, which I did not when I first went in in June.) The wait was especially long, I went to the library nearby and tried to study a bit, there was a really distracting dude nearby…and then Apple texted me to head back.

Here’s a fun fact: I got the iPhone 5 when it was new, to replace the iPhone 3 my dad had given me when he was fed up with it (I had no smartphone). Know when the 5 came out? A little over three years ago. Know how long this warranty fix is good for the faulty button? …Three years. So I was toast.

Fortunately, I had YET ANOTHER experience at an Apple Store where the people helping me intuitively understood the right thing to do (<3 to Erika/Erica and Mark, who modeled really good mentorship interactions during this whole thing). They found the note from when I came in early this summer, and they got a manager to sign off on…just swapping my phone out (!).

Anyway so I have a phone that just, like, works now.

This took forever, though, and I didn’t fancy studying til 7. Back to it Monday, then.

Notes from 15 October, 2015: loop invariants, psql will eat your soul, bad server.log pickup lines, TV ideas

Autumn Bridge Term continues!

I have some outstanding questions from the end of chapter 1 of CLRS (outstanding questions…they’re terrific!) (ho ho ho), and I will ask about them later, but also I dove right into chapter 2.

Unsurprisingly, it gets denser pretty fast. I am reading and rereading and rerereading a bunch of things. I have a basic grasp on, say, loop invariants, but I absolutely do not yet grok them.


Had a part-social-catchup, part-lunch-with-Nathan-and-his-mom-who’s-in-town lunch, and have significantly decreased my FOMO related to RC chat (Zulip). (I made a lot of choices about what NOT to read, which I am really proud of, and chose to read a small number of threads. All hail good threading.)

Now I do not have a big glaring “6949 UNREAD MESSAGES” thing hovering over the icon, and also I haven’t been keeping Zulip open, which makes it even easier. And I didn’t have to read 6949 messages to get there. (Phew!)

Decided to bravely tackle a Postgres problem with Nathan after lunch. We’ve previously tried to work on programming problems before, and it turns out that that might be a dangerous thing to do with your partner?

This time went a lot smoother, though, than any previous attempt, which I suspect is largely due to practicing “I don’t know” and related skills at RC.

Let’s back up in the terminal and see what we discovered! My brain is exhausted, but I know that I can understand my past.

? ? ? ? ? ? ? psql
psql: could not connect to server: No such file or directory
	Is the server running locally and accepting
	connections on Unix domain socket "/tmp/.s.PGSQL.5432"?

As you may remember from previous adventures with my prompt, the “? ? ? ? ? ? ?” is literally my bash prompt and I refer to it by its shortname sometimes, “chickparty,” because that’s what you get with a baby chicken and six balloons.

Anyway.

All the googling in the world yesterday & today helped me find some interesting information: namely, be exquisitely careful with your postmaster.pid, because you can do DEEP DAMAGE if you go messing with it all willy-nilly, but sometimes you MUST mess with it. This was not one of those times, regrettably.

For an excellent explanation of one possible path here, see this StackOverflow post. I’m especially impressed that the OP  ultimately solved their own problem, and THEN took the time to retrace their steps, explaining each one for the benefit of others.

I tweaked the find command just in case I was missing something, but there was indeed no postgres…except, as Nathan explained to me, the instance of grep that was searching for postgres. Sigh. Now I know!

  501  6548  3487   0  3:19PM ttys016    0:00.00 grep postgres

Ugh. Go find yourself, grep.

Alas, the end of my server log had an entirely different error than the one in the SO post:

LOG:  skipping missing configuration file "/usr/local/var/postgres/postgresql.auto.conf"
FATAL:  database files are incompatible with server
DETAIL:  The data directory was initialized by PostgreSQL version 9.2, which is not compatible with this version 9.4.4.

Yesterday, I had PAGES upon pages upon pages upon pages of this, almost endlessly repeating (there was some other stuff way way way up high, and the only dates I found for THOSE were in early 2014…hmm!). I scrolled with the mouse, the scrollbar barely moved, and I ultimately just had to drag and drop it like some kind of…person who does inelegant things.

For fun, and because both the internet and Nathan had suggested this, I ran tail -f,  which follows (aha! there’s the f) the progress of the file until you tell it to stop. Sure enough, guess what kept adding to itself every few beats:

? ? ? ? ? ? ? tail -f /usr/local/var/postgres/server.log 
DETAIL:  The data directory was initialized by PostgreSQL version 9.2, which is not compatible with this version 9.4.4.
LOG:  skipping missing configuration file "/usr/local/var/postgres/postgresql.auto.conf"
FATAL:  database files are incompatible with server
DETAIL:  The data directory was initialized by PostgreSQL version 9.2, which is not compatible with this version 9.4.4.

(and on and on until control-c stopped it)

SPOILER ALERT it is the postgres logs! My friend, you have been so, so busy for SUCH a long time, huh? Your legs must be tired (why) because you have been running on my computer for all eternity (groan) ho ho ho

This postgres directory had all kinds of goodies in it:

? ? ? ? ? ? ? ls
PG_VERSION	pg_clog		pg_multixact	pg_subtrans	pg_xlog		postmaster.pid
base		pg_hba.conf	pg_notify	pg_tblspc	postgresql.conf	server.log
global		pg_ident.conf	pg_stat_tmp	pg_twophase	postmaster.opts

And yeah, doing cat PG_VERSION netted a clean 9.2. Rats. 9.2 is apparently five hundred kinds of trouble! Down with 9.2; long live 9.4 until the next Extremely Different New Version comes out.

We looked at disk usage here with the -h flag, which stands for human? It displays it not in…another format which is trickier.

? ? ? ? ? ? ? du -h
6.0M	./base/1
6.0M	./base/12265
6.0M	./base/12270
6.0M	./base/16384
 24M	./base
428K	./global
8.0K	./pg_clog
8.0K	./pg_multixact/members
8.0K	./pg_multixact/offsets
 16K	./pg_multixact
8.0K	./pg_notify
4.0K	./pg_stat_tmp
8.0K	./pg_subtrans
  0B	./pg_tblspc
  0B	./pg_twophase
 16M	./pg_xlog
 83M	.

All the base are belong to us directories correspond to previously existing databases (from a zillion years ago when I managed QA reports for support, and also possibly from an open source day at Grace Hopper a few years ago?). Which is neat! I did not know that. That is a thing I learned today, too.

Because I decided that I did not care about these old databases that I have not looked at in literally years, we sallied forth with a rm -rf *,  which felt so so spooky to run.

Just. Whole postgres folder there. GONE. Run ls, completely empty.

Running psql still gave the same error (about /tmp/.s.PGSQL.5432), BUT, I ran ls again in /usr/local/var/postgres/, and we NOW have…dun dun dun…a server.log file! It’s Not Nothing!

Look at the cool new stuff at the end of server.log:

postgres cannot access the server configuration file "/usr/local/var/postgres/postgresql.conf": No such file or directory

It’s different! And then it was just THAT forever and ever, ^C (which is, I don’t know, like a computer’s “amen”? sure).

Okay so maybe not the most thrilling, but it’s Progress, and that is what I was after today.

Tried to get something going, since we’d now cleaned out all the old misbehaving stuff. Ran a series of commands that did not impress the computer:

  • initdb? no.
  • initdb -D .? no, initdb: directory “.” exists but is not empty. If you want to create a new database system, either remove or empty the directory “.” or run initdb with an argument other than “.”.
  • How about rm server.log; initdb? nooope. How about…
  • rm server.log; initdb -D . ? JACKPOT. By which I mean “success messages.”

So about that empty postgres directory. What’s it got in it NOW?

? ? ? ? ? ? ? ls
PG_VERSION		pg_ident.conf		pg_snapshots		pg_xlog
base			pg_logical		pg_stat			postgresql.auto.conf
global			pg_multixact		pg_stat_tmp		postgresql.conf
pg_clog			pg_notify		pg_subtrans		postmaster.opts
pg_dynshmem		pg_replslot		pg_tblspc		postmaster.pid
pg_hba.conf		pg_serial		pg_twophase		server.log

It’s not nothing! [distant cheers] The crowd goes wild [some woo-girls scream “WOO” in the background] everything is coming up Chickparty

And look at this adorableness (this is the whole server.log, not just the constantly expanding tail of suffering):

? ? ? ? ? ? ? cat server.log 
LOG:  database system was shut down at 2015-10-15 15:31:42 PDT
LOG:  MultiXact member wraparound protections are now enabled
LOG:  autovacuum launcher started
LOG:  database system is ready to accept connections

So then we whacked a few sticks against the wall, eventually creating a database, but that part almost feels like it will be helpful to struggle through a few times.

psql
(no)

psql foo
(no)

psql postgres
(yeah, but, what if we want something else. let's try to do something else.)

psql postgres 'create database foo'
(no)

psql postgres -c 'create database foo'
CREATE DATABASE

(thus spake Zarapostgres)

This puzzled Nathan for a bit, too (we didn’t hit on the perfect command the first time, anyway), which made me feel way better, because he does Postgres-y things a bunch for work. It’s nice to have people model that expertise does not equal omniscience — part of being experienced is knowing how to be productive and curious when stuck, I think.

So! Now I still have four CSVs full of all numbers (one date, many many many floats with 15 digits past the decimal…if they’re already double precision types, I’m kinda wishing there were a non-CSV format for these SUCH AS perhaps a database file). But I also have a working postgres to wrestle with tomorrow.

Postgres wrestling! Coming to a television near you. It’s gonna be big.

Notes from 14 October, 2015: autumn bridge term, libraries, & Jawbone

Back in Oregon. It’s strange here. People look at you on the street and I notice the air every time I go outside (it’s delicious; I breathe in and sigh and exclaim) and we only took a few hours to get back in our house (key excitement) and our friends are lovely and it gets so, so much colder at night here.

Today’s day one of Algorithm Study Time (I didn’t start on the road, we got home last Friday, and I gave myself Monday & Tuesday to take care of pressing home needs). Or maybe I’m calling it Autumn Bridge Term. I feel like I need a name for this.

Sonali at RC told me that for the next three weeks, it’s algorithms in the morning, building stuff in the afternoon, with lunch or a bike ride or whatever in the middle, and also I don’t have friends for now. Okay! I’m finding it comically freeing to have this much structure. Also that this feels like structure after the vast open fields of RC.

Cracking into the apparently-infamous CLRS algorithms book on Sonali’s recommendation. It is a beast, and it is a self-aware beast (it has already made references to its enormous size two times outside of the introduction, and I’m only in the first chapter). It is also the first time that I am doing highlighters to a book (perhaps ever), and I’m starting to find my way with this. It doesn’t hurt that I have magic windowed highlighters from Muji, so I can see through the pen as I’m highlighting (!). I continue to find ways to do small, personally meaningful rebellions, like writing “WTF” in the margin when appropriate. This continues to alarm and delight me.

I’m writing all my questions in a notebook, and typing out my exercise answers in a brand new repo. It seems like the kind of thing I should keep to myself, so I’m sharing it, because this is the kind of thing that seems reasonable now, after RC. Just. Share all the things. I like this feeling.

I got through Chapter 1, just not all the exercises or the problem yet. My brain is full, so now it’s time to give my stomach the same treatment. I’m talking, of course, about lunch. We will represent lunch here as a horizontal bar:


I either snuck into or went to the Concordia University library after lunch. The whole third floor, to my delight, is a quiet zone. No music. No talking. Just big beautiful windows and books and study corrals (in case you are a study horse or other study livestock) and wooden chairs and squishy chairs. There IS a “community library card” available here, but I don’t know if that means I’m also allowed to, like, come do stuff here. The existence of a Guest wifi network suggests that yes, however.

¯\_(ツ)_/¯

As mentioned above, the second half of my days for the next few weeks is (are?) Building Something. I ended up deep in the mud of “interesting datasets” and then tried to scale back and think about datasets I have on myself, which might be more interesting to me. Handily enough, I’ve been tracking my sleep and steps nearly every day for almost three years now (with some gaps due to technology or human errors of one kind or another).

Haven’t been using my Jawbone UP24 to track sleep lately, but I’ll figure out if that matters. The Mi Band I got after learning about Xiaomi from the Keyboard.io Kickstarter [whew!] is so so so much easier for sleep tracking, and has stellar battery life…but also a pretty bare-bones app. But also it was $15. In any case, the UP should have excellent coverage as far as steps go. (And also non-labeled “workout” sessions that are mostly bike commutes!)

So! I’m thinking I’d like to do stuff with that data, even if I’d had a rocky relationship with Jawbone products. I had a semi-original UP (not the very first generation, but the second gen, IIRC, which still plugged into the phone’s headphone jack to transmit information). I’ve had a series of misadventures with my original UP and UP24:

  • Original UP (headphone jack sync) stopped working entirely. Just. Blinked out of existence in a way no charging could fix. I eventually received a replacement (through a convoluted return process that almost turned me off of Jawbone entirely), AND, some time later, what I believe is the original defective bracelet. Hmm.
  • Next one stopped vibrating entirely (the vibrations partially confirm mode changes, give alerts, and function as the alarm). Since one of the reasons I am gleefully fond of this band is the little buzzing smart alarm, this was pesky/removed a functionality I had come to depend on.
  • Not wanting to deal with the return process again, and ready to leverage Bluetooth technology to be lazier (programmer’s mantra!), I got a new UP24 (which syncs via BT). It eventually became filthy (fine) and stopped functioning completely, except for secret flashing error codes (not fine). After a series of emails, I eventually had to call (on the telephone!) and go over all the information again to convince them that the thing was really really broken, and there was really really no way for me to fix it, and yes I know how to soft- and hard-reset my band now. It was a new kind of miserable, but the return process was much much easier.
  • And then there’s this one…the rubber has detached at both ends, eventually splitting on the cap side, and it can’t be slid back down to where it should reside. So it is eating itself at both ends, like some sort of Ouroboros.

But! Jawbone continues to make, as far as I can tell, incremental improvements in their support experience. Went to the FAQ, found something about Rubber Warping (sounds about right), filled out a tiny amount of information…and they’re sending me a warranty replacement (!) and it’ll have a return shipping label included (!!). A+, Jawbone.

Anyway now I’ve got five CSV files, each of which was just a click away once I found what I was looking for (thanks, Quora), one for each year from 2011-2015, including one from a year where there shouldn’t be any information (2011 — I got my first UP in November 2012).

Don’t know quite what I’m doing with it yet, but when building something, it helps to have literally any clue about what you are doing. And unless I find something wicked compelling, it’s Data On Myself which I am Finally Using For Something.

I eventually threw up my hands in frustration and headed back to the Udacity Relational Databases course, which I’d really like to finish up (and maybe review a bit). It is, after all, exactly what I am wanting to do with my project (Python + DB == BFF). And I finished lesson 4 of 5!

I also found a bilingual copy of Rainer Maria Rilke’s French poems in this library (yes! he wrote some French poems!) and anyway I guess I DO need to find out about this community library card business.

I can’t get Postgres to start, but fortunately I’m not even sure I’m doing the right thing (something may be broken, and if so, I just found one of those quintessentially lovely StackOverflow pages so I can piece through why and solve it).

Also, my Pomodoro timer went off again, and that makes 10 half-hour ticks or tocks or whatever today, and that’s about three hours of morning & three hours of afternoon and I am happy with that.