Posts

• 23 Jul 2020

  The Stable Marriage Problem

  The stable marriage problem can be stated as follows: Given (a) two sets that have the same number of elements and (b) a...
• 21 Jul 2020

  The Sieve of Eratosthenes

  Given an integer N > 1, you want to find all of the prime numbers from 1 to N. For example, if N = 11, then you get {2, ...
• 21 Jul 2020

  Marbles in Three Baskets and Problem Theory

  Marbles in Three Baskets is an ACM-ICPC problem. My solution to it is up at my GitHub. Here are my thoughts on the probl...
• 18 Jul 2020

  Monty Hall meets Monte Carlo

  You are on a game show. You can pick between three doors (A, B, and C). One of the doors has a prize behind it. Each of ...
• 18 Jul 2020

  Adjacency Lists

  If you aren't familiar with graph theory, I advise you to read my post on minimum spanning trees, where I define several...
• 12 Jul 2020

  Disjoint-Set Data Structures

  The disjoint-set data structure is a data structure that represents set partitions. A set partition of a set S is a coll...
• 12 Jul 2020

  Kruskal's Algorithm

  Kruskal's algorithm is a popular algorithm for finding minimum spanning trees. Here is an outline of it: (1) Start with ...
• 12 Jul 2020

  Minimum Spanning Trees

  A minimum spanning tree of a weighted connected graph is a spanning tree whose weight is less than or equal to the weigh...
• 11 Jul 2020

  Vertex Coloring and the Min-Conflicts Algorithm

  In the vertex coloring problem, you are given a graph and a set of colors. You want to assign colors to the vertices of ...
• 11 Jul 2020

  The N Queens Problem

  The N queens problem is a classic problem. It can be stated as follows: Place N queens on an NxN chessboard such that no...
• 10 Jul 2020

  Simulated Annealing

  You have a problem. You already have some solution to your problem, but you want the very best solution. There is a set ...
• 08 Jul 2020

  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 lea...
• 08 Jul 2020

  Of Dijkstra and Priority Queues

  Although I’ve implemented variants of Dijkstra’s algorithm in the past, I wanted to implement the algorithm ...
• 07 Jul 2020

  Breadth-First Search

  Now that I’ve written about queues, I’ll write about breadth-first search. Breadth-first search is a graph s...
• 06 Jul 2020

  Queues

  The last element you push onto a stack will be the first element that’s popped off the stack. A stack is a last-in, firs...
• 06 Jul 2020

  Stacks

  A stack is a container, like an array. However, each element of an array can be accessed directly and in constant time. ...
• 27 Jun 2020

  There are more real numbers than natural numbers

  The natural numbers are the numbers 1, 2, 3, 4, 5, .... Real numbers are numbers such as 10.4541, 1, -2358.541, etc., et...
• 19 Jun 2020

  Turing Machines

  In a previous post, I gave an informal explanation of the P=NP? problem. In that post, I described both deterministic an...
• 19 Jun 2020

  An Informal Explanation of the P=NP? Problem

  You have an easy job. Every hour your manager comes into your office and gives you a positive integer. Your job is simpl...
• 19 Jun 2020

  The K-Nearest Neighbors Algorithm

  The k-nearest neighbors algorithm is a simple machine-learning algorithm that classifies a new data point according to t...
• 20 May 2020

  Write Loops Like Dijkstra

  You do the best you can. You try your hardest to get a program right, and it looks like you’ve done it. But then y...
• 11 May 2020

  My LeetCode Repo

  I signed up to LeetCode a while back. Click here to see my profile. A little while ago, I had the bright idea to make a ...
• 11 May 2020

  The ID3 Algorithm

  You are given the voting records of a set of Democrats and the voting records of a set of Republicans. Now you are given...