I moved my blog to GitHub! Here is the new address:
My Leetcode Repo
As I wrote in a past blog entry, I signed up for Leetcode a while back. A few months ago, I had the bright idea to make a GitHub repository for programs that I create that solve Leetcode problems.
Since then, I’ve designed and implemented hundreds of programs. At the time of this writing, the repo contains 220 programs (which represents just a portion of all the programs that I’ve written for Leetcode since I signed up). Here is the link to the repo.
And, as always, you can access my repo for all the code that I’ve written for this blog.
Backing Up Your Files
Recently I manually backed up files to a USB drive. During that extremely pleasant experience, I decided that I’m going to automate the process for the future.
Backing up files by hand is time-consuming, error-prone, tedious, and stressful. So, I created a little bash script that will do the work for me.
Here it is, for your viewing pleasure. Maybe it will help you, too.
The Coin Change Problem
The problem
How many ways can you make change for a dollar?
You have four denominations available. You can use quarters, dimes, nickels, and pennies, and you have an unlimited supply of all of them. Now find the total number of ways to make change for a dollar.
There are a lot of ways to make change for a dollar. You could make change for a dollar with 100 pennies. You could use four quarters. You could use three quarters, two dimes, and one nickel. You could use one quarter, two dimes, four nickels, and 35 pennies. How do you find the total number of ways?
In general, given a list of denominations D and an amount of money M, how do you find the total number of ways to make change for M?
To answer that question, we’re going to apply dynamic programming. First we’ll take a top-down approach. Then we’ll take a bottom-up approach.
The top-down approach
This is the top-down approach in a nutshell: If the given problem instance is trivial, then solve it; if it’s not trivial, then cut it down to size.
Given an instance of the problem, we continually reduce the size of the problem instance until we reach subinstances that are trivial to solve. To produce a solution to the original problem instance, we combine all of the solutions to the subinstances.
Two parameters define the coin change problem: an amount of money (M) and a list of coin denominations (D). So, you can reduce a problem instance in two ways: decrease M or shorten D. We’ll do both.
We divide a nontrivial problem instance into these two subinstances:
(1) Find the number of ways to make change for M using the first denomination in D
(2) Find the number of ways to make change for M without using the first denomination in D
To illustrate the procedure, let’s say that M = 100 and D = [quarters, dimes, nickels, pennies].
If you use the first denomination in D, then you put in 25 cents. Now you only have to make change for $0.75. So, you reduce the size of the problem instance because you reduce the size of its first parameter, M.
Let’s say that you don’t use the first denomination in D. So, you’ve effectively reduced D to [dimes, nickels, pennies]. So, you reduce the size of the given problem instance by reducing the second parameter of the problem.
You continue dividing problem instances until you reach trivial subinstances. The coin change problem is trivial in these instances:
-You must make change for no amount of money. There is only one way to solve that problem: You use no coins.
-You must make change for a negative amount of money. There are zero ways to do that.
-You must make change for some amount of money, but there are no denominations to choose coins from. There are no ways to do that, either.
The subproblems are the same type of problem that the original problem is, because the subproblems require you to find the number of ways to make change for a given amount of money, too. So, we apply the same problem-solving procedure to the subproblems that we do to the original problem. Consequently, it is natural to use a recursive algorithm, like it was when I implemented a solution to the Towers of Hanoi problem. So, I implemented the algorithm in Scheme.
The bottom-up approach
We just examined a top-down approach to the coin change problem. We applied a divide-and-conquer strategy. We started with a problem instance and divided it into smaller and smaller subinstances, working our way down until we arrived at problem instances that are trivial to solve.
We can also employ a bottom-up approach, where we start with the solutions to the smallest subinstances of the problem and continually build on them until we get up to a solution to the entire problem instance.
The top-down, recursive approach typically solves a lot of the same subinstances many times. The bottom-up approach does not. So, the bottom-up approach is typically a lot faster. In the specific case of the coin change problem, the bottom-up approach is O(mn), where m is the number of coin denominations and n is the amount of money (in cents). In contrast, if you don’t memoize the recursive algorithm, it runs in exponential time.
As I have in the past, I used dynamic programming to design just such a bottom-up strategy. Here is a Python program that implements it. The program also features a naive recursive solution and a memoized recursive solution.
Comments
In the past, I also implemented a top-down, recursive algorithm and then designed and implemented a bottom-up algorithm. The algorithms find the maximum independent set of a tree. Here is the Python program that implements the bottom-up algorithm. Here is the Python program that implements the top-down algorithm.
The algorithms that solve the maximum independent set problem and the coin change problem have a feature in common: The use of inclusion and non-inclusion to neatly divide a problem instance into just two subinstances.
The maximum independent set of a tree either includes the root of the tree or it doesn’t include the root of the tree. Exploiting that fact, you construct the independent set that includes the root and the independent set that doesn’t include the root, and then you take the larger of the two.
Likewise, when you count the total number of ways that you can make change for some amount of money, you count the number of ways that you can make change for it if you include the first denomination on the list and the number of ways if you don’t include that denomination.
I have found that many dynamic programming approaches feature this technique. For example, an approach to the discrete knapsack problem features it, too: To compute the maximum value that the knapsack can contain, you compute the value when you include the current item and when you don’t include the current item, and then you take the larger of the two. I have implemented that approach, too.
MIT professor Erik Demaine has said that an essential part of dynamic programming is guessing. In his opinion, dynamic programming is “careful brute force”. If you don’t know the solution to some problem, then try every possible solution and take a best one. And that is what is going on in the above procedures. The technique that all of these procedures deploy is just a clever way to partition the set of all possible solutions. Because of the law of excluded middle, a solution either includes an element or doesn’t include it. So, we only have to process two possibilities.
Miscellaneous Implementations
Over the past year, I have implemented several algorithms and data structures. I decided to do a brief round-up:
I implemented insertion sort for lists of numbers in Python.
I implemented insertion sort for linked lists in Python.
I implemented insertion sort for linked lists in Java.
I implemented prime factorization in Java.
Q-Learning
In reinforcement learning, an agent takes actions within an environment. When an agent acts, a reward function assigns feedback to the agent that either positively or negatively reinforces the agent’s action. The agent’s goal is to use this feedback to learn an optimal policy.
For any given state of the environment, a policy tells the agent an action to take when the environment is in that state. An optimal policy tells the agent the best action to take. Of course, there are several different ways to define what a best action is. So, let’s say that an optimal policy maximizes the sum of discounted rewards over time.
Say that Q(s, a) is the reward received from taking action a from state s, plus the discounted value of following the optimal policy thereafter. So, if the agent knows Q, then it can execute the optimal policy. Whenever the agent is in state s, the optimal policy is to take the action a that maximizes Q(s, a). So, the agent’s task is to learn Q.
To learn Q, create a table Q[s][a] and initialize the entries to zero. Then, over and over again, have the agent take actions from states and receive the ensuing rewards. Update Q[s][a] each time. Q[s][a] will converge to the true value of Q as the number of times that each state-action pair is visited converges to infinity.
I implemented Q-learning, and I applied it to a simple environment. The code is up at my GitHub.
References:
Mitchell, Tom. Machine Learning. McGraw-Hill, 1997.
Quines
A quine is a computer program that prints its own source code. Writing a quine is not as easy as you might think.
To learn how to write quines, I made use of David Madore’s discussion of quines and Introduction to the Theory of Computation, by Michael Sipser. However, I prefer Sipser’s discussion. I found it to be a lot clearer than Madore’s.
Sipser does not talk about computer programs. Instead, he talks about Turing machines. A computer program corresponds to a Turing machine. So, a quine corresponds to a Turing machine that outputs a description of itself.
Let QUINE be a Turing machine that outputs a description of itself. QUINE has two parts, C and D, each of which is itself a Turing machine. C outputs a description of D, and D outputs a description of C. So, QUINE outputs a description of its entire self.
D runs first. D outputs onto its tape a description of C. Refer to that description of C as <C>.
Let q(w) be the description of a Turing machine that outputs w. q(w) is a computable function. In fact, given any string w, it is easy to construct a Turing machine P_{w} that outputs w. On any input, P_{w} simply outputs w onto its tape, ignoring the input.
Now, C reads <C> off D’s tape. Then C computes q(<C>). So, now C has the description of a Turing machine that outputs <C>. But that’s D! So, now C can output a description of D.
So, a quine has two parts, the code and the data. The data represents the code. The code uses the data to print the code and the data.
I wrote a quine in C and a quine in Python. To verify that the C program is a quine, type the following commands at the terminal:
gcc -o quine quine.c
diff <(./quine) quine.c
To verify that the Python program is a quine, type the following command:
diff <(python quine.py) quine.py
You will find in both cases that diff produces no output, which means that there are no differences between the programs' outputs and their source code.
Turing Machines
In a previous post, I gave an informal explanation of the P=NP? problem. In that post, I described both deterministic and nondeterministic Turing machines. A couple of months ago, I decided to implement the deterministic Turing machine in Python.
I also implemented a special deterministic Turing machine that decides whether a given positive integer is divisible by 4, just like the hypothetical Turing machine that I describe in my previous post.
I include a Bash script that tests that implementation. The script inputs every multiple of 4, ranging from 4 to 40, into the Turing machine program. The program passes every test.
LeetCode
I signed up on LeetCode three days ago. In three days, I’ve solved 42 problems. Here is my profile.
Ranked Pairs and “The Wire”
A few days ago, a redditor asked the people of /r/TheWire to rank the five seasons of the HBO television show “The Wire”, and several people posted their rankings. I wanted to take their individual rankings and uncover one aggregate ranking that captured the overall preferences of the entire group of posters. In other words, I wanted to implement a preferential voting scheme.
I was aware of Arrow’s theorem, which says that no voting scheme can satisfy a certain small set of reasonable criteria when voters are ranking three or more alternatives. However, I was also aware that a number of countries employ preferential voting systems. So, I didn’t give up, and I searched for a preferential voting system that would fit the bill.
I found one that worked: the ranked pairs voting scheme. In the ranked pairs voting system, you first count all the times that voters ranked Alternative X ahead of Alternative Y, for all pairs of alternatives X and Y. If more voters ranked Alternative X ahead of Alternative Y, then we say that Alternative X is a majority over Alternative Y, and we represent X’s majority over Y as (X, Y).
Now you sort all the majorities. For example, say that we have two majorities, (X, Y) and (A, B). Voters ranked Alternative X ahead of Alternative Y three times, and they ranked Alternative A ahead of Alternative B five times. So, (A, B) comes before (X, Y) in the sort.
But what if the sorted list of majorities creates a cycle? For example, say that we have [(A, B), (B, C), (C, A)]. Then A is a majority over B and B is a majority over C. But C is a majority over A. So, by transitivity, A is a majority over A – but that is a contradiction.
Here’s how you resolve that issue. You build a directed acyclic graph (DAG), where the DAG contains a directed edge from X to Y only if X is a majority over Y. You build the DAG by going down the sorted list of majorities. For each majority, you try to add a corresponding edge to the DAG. If adding that edge would produce a cycle, then you don’t add it. If it wouldn’t produce a cycle, then you do add it. If you do add a majority, then that majority gets “locked in” to the final list of majorities.
The winner of the election is the source of the DAG. The source of the DAG is the vertex that doesn’t have any incoming edges. It corresponds to an alternative that no other alternative is a majority over.
However, I didn’t want to know just the winner. I wanted to know the aggregate ranking. So, I sorted the alternatives by the number of outgoing edges that their corresponding vertices have in the DAG. The number of outgoing edges of a vertex corresponds to the number of alternatives that an alternative is a majority over.
I collected the data on the night of September 1. I simply scrolled down the list of comments and recorded the rankings that commenters reported. The only complication was that a couple of commenters expressed indifference between some seasons. So, for example, one person wrote, “4 > 1 > 3/2 > 5”. In such a case, I ranked seasons in the order that they were written. So, in this particular case, I placed Season 3 before Season 2.
Then I ran the program, and the result was 4 > 1 > 2 > 3. Season 5 didn’t even make the list.
You can find my program up at my GitHub.
Further references:
jdanray 