Tag: java


Computing Square Roots: Part 2: Using Continued Fractions

Posted in Mathematics

permalink

Table of Contents

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

permalink

Table of Contents

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

permalink

Table of Contents

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
            add to southwest queue
        if in northwest …



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   


Enigma Cipher Implementation: Part 4: Combinatorics

Posted in Enigma

permalink

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.

Table of Contents

The Key Space

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



Tags:    ciphers    enigma    encryption    java   


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

Posted in Enigma

permalink

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 …



Tags:    ciphers    enigma    encryption    java