In Part 1 of this post we discussed a data structure called a de Bruijn graph and covered its application to genome assembly. To summarize, a de Bruijn graph is a type of graph that represents a set of k-mers as a set of directed edges on …
Posted in Computational Biology
To provide a bit of context for a discussion of Euler paths and Euler cycles: starting around December, a group of us in the Lab for Data Intensive Biology (DIB Lab) started working through the textbook Bioinformatics Algorithms: An Active Learning Approach and the associated website, Rosalind.info.
Rosalind.info is a site that is similar in style …
This is Part 3 of an N-part series.
The Josephus Problem for a …
This is Part 2 of an N-part series.
In this blog post we'll walk through two examples of …
This is Part 1 of an N-part series.
The following problem, Cat and Mice, is Puzzle 88 in Boris Kordemsky's The Moscow Puzzles.
Purrer has decided to take a nap. He dreams …
In Volume 4 Fascicle 0 of Donald Knuth's Art of Computer Programming, Knuth introduces a tool for exploring concepts in graph theory: the five-letter words. This is a collection …
In Volume 4, Facsimile 0 of Donald Knuth's Art of Computer Programming, in which Knuth covers graph theory, he introduces a list of five-letter words as part of a data set useful in exploring graph theory and graph algorithms.
The list of words is part of the Stanford Graph Base, a set of data sets that are useful for studying graph theory and networks.
See Five Letter Words on the charlesreid1.com wiki for details.
This post …
In today's post we're going to discuss the generation of permutations.
Often, in combinatorics problems, we are interested in how many different instances or configurations of a particular thing we can have (what we'll call "enumeration" or "counting"). However, that is different from wanting to actually see all of those configurations. Indeed, if we are counting something with an astronomical number of configurations, we don't want to try to list all of them.
However, as usual, Donald Knuth, who covers the topic of permutation generation in Volume 4A of his classic work, The Art of Computer Programming, uncovers …
Posted in Computer Science
NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?
The letter/word coverage problem, as presented by Donald Knuth in Volume 4, Facicle 0 of his masterpiece Art of …
NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?
NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?
Comedian John Cleese, in his memoir So Anyway..., described the social classes of his mother and father as "upper-uper-lower-middle class" and "middle-middle-middle-lower-middle class", respectively. Write a program that will sort individuals based on a labeling of their social standing by class.
The three main classes are upper, middle, and lower. Classes progress hierarchically from right to left. For example, lower-upper would come before lower-lower. There is also ordering within a class, so upper-upper is a higher class than middle-upper.
Once you have reached …
Table of Contents:
Recursion, particularly recursive backtracking, is far and away the most challenging topic I cover when I teach the CSE 143 (Java Programming II) course at South Seattle College. Teaching the concept of recursion, on its own, is challenging: the concept is a hard one to encounter in everyday life, making it unfamiliar, and that creates a lot of friction when students try to understand how to apply recursion.
The …
Revisiting the N queens problem, this time implementing the solution in Python.
Verb-oriented solution, functional, and based on Perl solution
More fair comparison - both are interpreted languages, not compiled languages
Compare Python and Perl, ease of implementation, speed, flexibility
As a recap from the …
In this post, we describe an implementation of the N Queens Problem, which is a puzzle related to optimization, combinatorics, and recursive backtracking. The puzzle asks: how many configurations are there for placing 8 queens on a chessboard such that no queen can attack any othr queen?
This problem was implemented in Perl …