WDI week 11: algorithms, big O notation, regex and security


This week, we learned about some of the things people from a non-CS background might otherwise miss out on. It'd be kind of ridiculous to think you could cover anything like as much as a computer science degree in a week, but I'm glad we were at least exposed to a few of the basic concepts.

I think one of the problems with the kind of 'learning by doing' methodology we've followed so far is that you learn how to do things, but not necessarily why. Similarly, there tends to be a lot of desire among beginners to 'just make it work', rather than an interest in finding the best or most efficient way to do that, and being able to justify why you followed a specific pattern or made that particular choice.

We started on Monday by talking about data structures. We'd already been using some data structures (hashes, arrays etc.) in our programs so far, but we were also introduced to some new ones, namely linked lists and trees. A linked list is a data structure consisting of a group of nodes which together represent a sequence, and a tree is a data structure made of nodes which can have values as well as links to zero or more child nodes.

On Tuesday, we covered binary (which I thankfully already knew about), and then touched on algorithms. At its most general, an algorithm can be defined as a set of steps or instructions to achieve a particular outcome. So you can imagine, in computer science, there are many different algorithms we can use to achieve particular tasks, some of them more efficient than others. We represent the efficiency of a particular algorithm given a certain input with something called big O notation.

Wednesday we learned about some specific algorithms for sorting: bubble sort, merge sort and quick sort. Here's a nice d3.js visualization of some more common sorting algorithms.

Thursday morning was a welcome break from CS theory which, I'm not going to lie, did fry my brain a bit given the time we had to wrap our heads around it. We had some practice technical interviews, which actually turned out to be a lot less terrifying than I expected. Then in the afternoon, we did regex. Short for regular expressions, regex is how you check for patterns in strings. It's useful for things like validating form input if you want to check a user's entered a valid phone number format or long enough password, for example. I'd already learned a tiny bit of regex myself when building my Twitter bot, but it was cool to recap.

On Friday, we talked about security, with a focus on learning how to make our Rails apps more secure. Unsurprisingly, it hadn't even occurred to most of us the things you can do to attack a site. For example, several people's projects let their authenticated users do way more than they really should have been able to.

Beyond that, we learned about SQL injections, which is where an insecurely coded form input lets someone insert a malicious piece of SQL that could do bad things to your database. Similar things called XSS attacks can happen with JavaScript if you let people put arbitrary content on a page, allowing them to execute scripts on your users' pages.

Cross Site Request Forgery (CSRF) is when a user navigates to a page that the attacker controls, and that page prompts the user's browser to make a request to your server, and the user has a live session. Without CSRF protection, an attacker can trick the user into effectively submitting actions without knowing. The attacker can't look at the results of the request, so requests like index and show (GET requests) should be harmless if you're following the Rails and HTTP conventions, but if the attacker is creating, updating, or deleting records, that could be dangerous.

Luckily, Rails protects you from CSRF attacks with a forgery protection token, but several people had commented this out to overcome other issues, not really realizing what it was for.