DFS

Today is a Friday so today’s post comes a little early. I am going to go and post this a little early. In today’s class we began an introduction to algorithms and data structures. There are a lot of algos out there in the world - I was linked to a github (https://github.com/kanwei/algorithms) that had a whole bunch of them. To start us off as gently as possible, we started with understanding what was a data structure. We put together Node classes, which have parents, child nodes, and when put together make up a tree. Using this tree, we would be able to put together the next projects.

An algorithm is kind of like a recipe for data. It is written up in an abstract concept that can then be written in any programming language available. The two big algos that we worked on were Depth-First Search and Breadth First Search. These are things used for searching items in a Tree. In Depth First Search, you pick a “branch” of the tree and then explore it as deeply as you can. This way, you can be very thorough in the exploration of a branch before you move on to other branches. The Breadth First Search, you go through each level of a tree before you exit that level and then go down one more level.

Monday is the first assessment. If you fail 2 two of them they ask you to leave. I have to study hard this weekend and review everything that I have learned. Doing programs over and over again I think will help here.

3 Top Things I Learned:

After reviewing a lot of stuff last night, I felt that I made a lot of progress in implementing recursion. It is still challenging though. I put together a DPS program for a tree that used recursion but missed all the possible base cases. My partner did a good job in helping me find it.

It is interesting how things come up again and again. When putting together an earlier project (http://web.archive.org/web/20120418110425/http://www.rubyquiz.com/quiz44.html) word_chains, Ned had explained that a good way to help do this was to build a pool of possible words and then expand it slowly outwards. It took me a very long time to do this but the experience in putting it together helped in understanding DFS.

Names help a lot. While reading DFS on Wikipedia, I suddenly came across an explanation that labeled a vague abstract concept - the array store that stores the data objects that we have yet to scan and compare to our target - a “queue”. Ned had called this earlier a “pool” or a “thing that has to be expanded, possible words”. Calling a queue suddenly opened my eyes and when I came across DFS again it flowed much easier.

Things I Think I Think:

Reading the Wikipedia and understanding the pseudocode that they provide does so much in helping you understand how to implement an algorithm.

Talking through things aloud makes your throat parched but helps clear your brain

Putting “return” at the bottom of my methods is a bad habit that I just can’t quit

I keep writing “var ++” to increment something by 1 instead of the right “var += 1”. Ruby does not recognize this and gives me errors.