#marchcohort

Mondays are interesting days at App Academy. Monday is test day — we begin each week with an assessment on the material from the preceding unit. Yesterday's was on SQL and ActiveRecord associations. Assessments here at App Academy are somewhat ominous, because if you fail to earn a passing score on more than one test, you will be asked to leave. They hold us to a pretty high standard, and they expect us to live up to our own expectations and goals.

Because of this, Monday mornings can be incredibly stressful. I stress out about the assessments, but at least that motivates me to study my ass off. I spent the weekend enclosed in my room doing SQL practice problems until the stacatto syntax flowed naturally. I did just fine on the exam. (The associations portion of the exam was Harry Potter-themed, lolz.) More important is that because I spent so much time reviewing what we had learned about ActiveRecord and database querying from last week, I have a much, much better understanding of it.

Now we're moving into the really juicy stuff, Rails projects. Yesterday we tinkered with some Google and Twitter APIs to get a sense of how they work and how to render and parse JSON objects. It was fun, but at the same time I was pretty burned out from the morning. Today we'll be playing with routes and controllers, and we get to build our own API.

Concepts

Data trees

Breadth-first search

Depth-first search

Stacks

Queues

Algorithms

Time Complexity

Algorithms and data structures were the orders of business for the final day of week one at App Academy. Our morning lecture delved (literally) into the concept of a branching data structure called trees. We had previously covered arrays — a linear data structure that can be used as a stack or a queue — but data trees have properties that make them advantageous in terms of time complexity. (I sort of know what that means.)

Whereas arrays are ordered in a line, trees are branching structures that are composed of nodes (the things that actually hold data) connected by links. If a node has sub-nodes, it is called a 'parent' and the nodes it connects to are 'children.' This parent to child structure continues until you reach the bottom layer of nodes that have no children, referred to as 'leaves' of the tree.

One advantage of this structure is that you don't have to check every node in order to find your target value or piece of data. Some examples are depth-first search and breadth-first search.

A depth-first search conducted on a binary tree will recursively travel down the tree adding to the 'call stack,' constantly checking the left child node of each parent until it reaches the end of the branch or finds the target. If the search gets to the end of a given branch and does not return the target, it will backtrack up the nodes until it can move to a right node. This pattern will continue until the entire tree is searched, or the target is identified.

In a breadth-first search, the tree is checked layer by layer. This is good if you know that the target node is close to the parent. This is accomplished using a queue. The parent node begins in the queue, and is then dequeued and checked against the search value. If they are equivalent, the parent is returned. If not, the child nodes of the parent are added to the queue, and the process is continued until the entire tree is searched or the target is found.

At the end of today, we coded up an AI for a tic-tac-toe game using a branching data structure. This was one of the most rewarding and fun things so far at App Academy. The feeling of satisfaction that accompanied running a computer player against another computer player and watching them continually play to a draw is hard to describe.

Today, April 3rd, a day that will live in infamy, will henceforth be known as Recursion Day.

Computerist humor:

To understand recursion, you must first understand recursion.

A recursive method calls itself, and then tries to solve a similar subproblem. Factorials are an example of a recursive solution.

5!  --->  5 * 4 * 3 * 2 * 1 == 120

I was able to wrap my brain around the concept of recursion fairly quickly, but the actual implementation is still difficult for me. However, with the help of our awesome TA Will we wrote a good recursive solution for finding all possible subsets of a given array.

Recursion is tricky. I still don't have a good handle on it, and I anticipate some late nights over the weekend working on it until I can write recursive methods fluidly.