Today marks the beginning of a two-part series on graphs, starting with a special type of graph, and perhaps the most common one in interview-style problems, the tree. Trees are a hierarchical data structure, meaning that data is arranged in a parent-child relationship. You are, doubtless, familiar with various kinds of trees, as they are a common way to visualize relationships in the real world. A family tree, a corporation with all its subcomponents and employees, or, for a more to-the-point example, the file tree in your computer, all represent data as a tree, in which a root node points to its child nodes, which point to their child nodes, and so on and so forth. For all my Windows users (Woot Woot! Go Windows!), you have probably at some point had to manipulate your hosts file, which lives at the path C:\WINDOWS\system32\drivers\etc\hosts. To help visualize, here is the same thing, written in tree form.
C: | \Windows | \system32 | \drivers | \etc | \hosts
Today, we will briefly consider a few distinct but closely related concepts in algorithm design: dynamic programming, memoization, and the “greedy algorithm”. Another closely related concept is caching, which I will not go into detail about, but encourage you to study up on. The following material assumes that you have some familiarity with recursion, which I have not gone over, but assume you have seen at least a few times. The idea of recursion is to divide a problem into a series of subproblems and solve each one. It can be referred to as “divide-and-conquer” or “top-down”, and merge sort and quicksort, which I discussed previously, are examples of recursive algorithms. Right then, let’s consider an example to illustrate why dynamic programming is useful.
Today, I will introduce the concept of the binary numeral system on which computers rely. Please note that this is a VERY basic introduction to binary numbers, their purpose and uses, and the operations that can be performed on/with them. Until very recently, I had almost no experience working with binary, and my knowledge is still a work in progress. Bit manipulations such as bit vectors etc. are complex topics, and as a junior engineer, you will need to have only a very surface-level understanding of bits and the like. That said, I encourage you to study further on the topics I introduce today, since understanding how computers work at the lowest level can only help you as a programmer. Okay, that aside, let’s get cracking.
Before we begin, I did in fact butcher the quote from yesterday. Mr Dimopolous actually said “Jumping from failure to failure with undiminished enthusiasm is the big secret to success” See, way more poetic. Now, onto topics of substance.
Welcome back aspiring engineers! Today, I will tell you about a few common algorithms for sorting lists. You have, undoubtedly in your time as programmers, come across instances where it helped to have items in a list appear in sorted order. Whether finding the first instance of a user alphabetically, finding a user’s first pet’s name alphabetically, or for countless other applications, you have probably used your language of choice’s array.sort() method and thought little of it. That is fine, but in moving from programming small, personal apps to large, data-intensive, team-oriented software, it helps to have an understanding of how these methods are built and the common practices in sorting. Moreoever, sorting data is one of the most important and fundamental exercises in computer science, and taking the time to understand its best practices is a good review of topics that will come up again and again when solving cs problems. Plus, if asked an interview question in which having a sorted list would help in some way (such as to implement binary search), you should be able to demonstrate that you know how to sort a list without a specific language’s built-in method, and that you have a good understanding of the tradeoffs between different algorithms.