# Computing Square Roots: Part 2: Using Continued Fractions

Posted in Mathematics

## Continued Fractions

Let's start part 2 of our discussion of computing square roots by talking about continued fractions. When we first learn mathematics, we learn to count in the base 10 system: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We can construct representations of all of the integers using these 10 digits, by arranging them in a different order. So, for example, saying 125 is equivalent to saying …

# Computing Square Roots: Part 1: Using Newton's Method

Posted in Mathematics

## Newton's Method for Finding Roots of Equations

Suppose we have a function $$f(x)$$ and we want to compute values of $$x$$ for which $$f(x)=0$$. These values of $$x$$ are called the roots of $$f(x)$$.

We can compute the roots using Newton's Method, which utilizes the derivative of the function to iteratively compute the roots of the function.

Newton's method begins with an initial guess. It evaluates the derivative …

# CSE 143 Final Project: Hilbert Sort: 3. The Code

Posted in Computer Science

This is the third in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post deals with the code to solve the Hilbert Sort problem.

# Hilbert Sort: Pseudocode

From our prior post, here is the psudocode for our Hilbert Sort function:

define hilbert_sort( unsorted queue, square dimension ):
create southwest queue
create northwest queue
create northeast queue
create southeast queue
for each point:
if in southwest:
create new point using X -> Y, Y -> X
if in northwest …

# Teaching Recursion with the N Queens Problem

Posted in Computer Science

## 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 …

# Python vs. Perl: N Queens Problem

Posted in Computer Science

## 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 …

# Perl vs. Java: N Queens Problem

Posted in Computer Science

## 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 …

# Enigma Cipher Implementation: Part 4: Combinatorics

Posted in Enigma

In this, the fourth article in a series on implementing the Enigma cipher in Java, we use some big number libraries to explore the combinatorics of the Enigma encryption scheme and better understand the Enigma's strengths and weaknesses.

## The Key Space

Basically, what the Enigma did was to encrypt each character of a message one …

# Enigma Cipher Implementation: Part 3: Enigma in Java Without Objects

Posted in Enigma

As the title suggests, we're continuing with the third in a series of posts exploring a verb-oriented approach to programming - in an attempt to free ourselves from the fetishization of objects, we are attempting to learn how to use languages against their will.

This is all inspired by Steve Yegge's 2006 blog post, "Execution in the Kingdom of Nouns," an excellent read that inspired me to explore the subject more deeply.

## Java Pseudocode

In the last post, we ran through the pseudocode for an Enigma machine based entirely upon Strings, iterators, and integer indexes, leading to a vastly simpler abstraction …