Ryan's Repository of Random Reflections

Dynamic Programming is a programming technique used to solve large, complex problems that have overlapping sub-problems. It does this by computing each sub-problem only once, ensuring non-exponential behavior. It differs from memoization (no, that's not a typo) in that instead of computing the result of a function then storing it in a cache, it instead generates a certain result before calculating any other result that relies on it. Dynamic Programming problems often require a different way of thinking than typical problems. Most often, dynamic programming becomes useful when you want to reverse engineer a tree recursive function. By that I mean you want to start of with the base case(s), then use those to generate the next few cases, and repeat this process until all points of interest have been calculated. Most often, at least in imperative languages, these dynamic programming algorithms are iterative, meaning they don't have recursive calls. That being said, it's still...

In this blog post, I will give some general background info about Markov Chains, a mathematical structure that arises in Probability theory. I was first introduced to Markov Chains last year and I found them extremely interesting. I found them particularly interesting because they combine ideas from linear algebra, graph theory, and probability theory. Markov chains have applications in many real world situations, including sabermetrics and stock market analysis. A Markov Chain can be thought of as a special type of graph or a non-deterministic finite automaton. Basically, that means that there are a set of states, and you can transition from a set of different states from any given state. The transitions are weighted by probability measures. There are lot's of interesting question you can ask about Markov chains - my favorite is the random walk type problems. Markov chains can be used to model a variety of real world situations, including baseball simulations, stock market behav...

The 2 biggest programming paradigms are functional and imperative, but they share very little in common. In this blog post, I will discuss the differences between the two as I understand them and talk about my experience with each. Functional programming languages are very mathematical - functions can be defined piece-wise, recursively, or in terms of other functions. They can also easily be combined forming composition of functions. Imperative languages use a slightly different approach - rather than telling the computer what something is, you must specify how to get it. The first functional programming language I learned was Racket, which is a similar to another functional programming language: Common Lisp. I always thought of Racket as a neat language with some nice abstractions but I always felt like it lacked some core functionality. Recently, however, my friend introduced me to Haskell, and I've been trying to pick it up.  Haskell is much more powerful than Racket, and it...

As a Junior in college, I need to start considering what I want to do after graduation. The two possibilities are to work in the corporate world and do application development or something of that flavor, or go to graduate school and pursue higher education. In this blog post, I will discuss my current understanding of some of the differences between the two, and I will share my knowledge/experience on the best way to prepare for each while in college. Working and the Corporate world is completely different than going to graduate school and pursuing a career in academia. Real world jobs have some nice virtues, but academia does as well. In my time here as a student, I have been involved in a lot of academic research, which is a very important thing to have when applying to graduate school. I also had a summer internship at JP Morgan last summer. I have had some experience from both sides of the spectrum and they are completely different. While I'm still undecided on what I want t...

In this blog post, I present a very interesting math problem that I came up with while pondering random walk problems. You are walking along the x axis and you start at $x=0$. At each time step you move to $x+1$ with probability $ \frac{1}{1+x} $ and to $ x-1 $ with probability $ \frac{x}{x+1} $.  What is the expected number of steps until you return to $ 0 $ for the first time? What makes this problem harder than a typical random walk problem is that the probability of moving to $x+1$ vs $x-1$ is not fixed -- it changes based on your position. That being said, the typical counting methods for solving problems of this type do not apply. There is a clever and fascinating solution that doesn't require too much advanced knowledge, but I will leave it to you to think about this problem.

As a Computer Science and Mathematics double major, a lot of the things I learn in my math classes I can apply in my computer science classes (and vice versa). But there's also a lot of material that I learn in math that's way different than anything I'd ever do in computer science (and vice versa). I've also met a lot of different people in each subject. In this post, I will talk about a recent experience I had when I posed the same question to math students and computer science students. Mathematicians and Computer Scientists think differently, and in some cases they approach problems differently. I will also talk about why some Mathematicians should broaden their horizons and explore the world of computing. Each week I send out weekly challenge problems on behalf of ACM (and Math Club for that matter). I usually think up and solve these problems myself so the answers don't necessarily exist out on the internet. For last weeks ACM weekly challenge, the problem ...

Here is a problem that came up a few days ago and I'm still thinking about: There is an amoebae in a box. At each time step, it either multiplies in 2, multiplies in 3, stays the same, or dies - all with equal probability. What is the probability that eventually, all the amoebae die out? Show/Hide Solution Solution One can quickly see that the probability is at least $\frac{1}{4}$ because there is a $\frac{1}{4}$ chance of dying on the first time step. Similarly, you could die on the first time step ($\frac{1}{4}$), stay the same then die ($\frac{1}{4^2}$), etc. Thus, the probability of eventual extinction is at least $\sum_{n=1}^{\infty} \frac{1}{4^n}$. Unfortunately, this strategy leads to a dead end. Instead, I use a clever interpretation of the problem that leads to a very simple and elegant solution. My key insight came from seeing an infinite continued fraction problem, which uses a simple technique to define the value of the continued fraction in terms of itself. T...