Tag: recursion


Graphs for Bioinformatics, Part 2: Finding Eulerian Paths

Posted in Computational Biology

permalink

The Context: de Bruijn Graphs

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 …



Tags:    go    golang    rosalind    computational biology    bioinformatics    euler    recursion    backtracking    graphs    algorithms    hamiltonian    eulerian   


Graphs for Bioinformatics, Part 1: de Bruijn Graphs, Hamiltonian Paths, and Eulerian Paths

Posted in Computational Biology

permalink

The Context: Rosalind.info

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 …



Tags:    go    golang    rosalind    computational biology    bioinformatics    euler    recursion    backtracking    graphs    algorithms    hamiltonian    eulerian   


Recursive Backtracking in Go for Bioinformatics Applications: 3. Go Implementation of Backtracking

Posted in Computational Biology

permalink

This is the third in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.



Tags:    go    golang    rosalind    computational biology    bioinformatics    recursion    backtracking    strings    combinatorics   


Recursive Backtracking in Go for Bioinformatics Applications: 2. Generating Variations

Posted in Computational Biology

permalink

This is the second in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.



Table of Contents



Tags:    go    golang    rosalind    bioinformatics    recursion    backtracking    strings    combinatorics   


Recursive Backtracking in Go for Bioinformatics Applications: 1. Counting Variations

Posted in Computational Biology

permalink

This is the first in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.



Table of Contents



Tags:    go    golang    rosalind    computational biology    bioinformatics    recursion    backtracking    strings    combinatorics   


Teaching Recursion with the N Queens Problem

Posted in Computer Science

permalink

Table of Contents:

A Gentle Introduction to Recursion

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 …



Tags:    java    algorithms    recursion    n-queens   


Python vs. Perl: N Queens Problem

Posted in Computer Science

permalink

Table of Contents

Background

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

N Queens Problem

As a recap from the …



Tags:    python    perl    java    algorithms    recursion    n-queens   


Perl vs. Java: N Queens Problem

Posted in Computer Science

permalink

Table of Contents

Summary

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 …



Tags:    java    perl    algorithms    recursion    n-queens