Category: Computer Science


Let's Generate Permutations!

Posted in Computer Science

permalink

Generating Permutations

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 …




Five Letter Words: Part 3: Letter Coverage and Dynamic Programming

Posted in Computer Science

permalink

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?

Table of Contents

Introduction

The letter/word coverage problem, as presented by Donald Knuth in Volume 4, Facsimile 0 of his masterpiece Art of …




Five Letter Words: Part 2: More Five-Word Algorithms

Posted in Computer Science

permalink

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?

Table of Contents



Tags:    python    computer science    graphs    algorithms    art of computer programming    knuth    language   


Five Letter Words: Part 1: Getting Familiar With The List

Posted in Computer Science

permalink

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?

Table of Contents

About the Five-Letter …



Tags:    python    computer science    graphs    algorithms    art of computer programming    knuth    language   


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 …



CSE 143 Final Project: Hilbert Sort: 2. The Solution Algorithm

Posted in Computer Science

permalink

Table of Contents

This is the second in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post solves the problem.

Hilbert Sort Problem

In the prior post, we covered the Hilbert Sort problem, but we state it once more succinctly here before detailing a solution to the problem.

The Hilbert Sort problem asks the following: given a set of labeled \((x,y)\) points, how can we sort the points according to the order …




CSE 143 Final Project: Hilbert Sort: 1. The Problem

Posted in Computer Science

permalink

Table of Contents

This is the first in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post sets up the problem.

Hilbert Sort: Motivation

In the next few series of posts, we will cover the Hilbert Sort problem, how it works, and how to implement it.
However, before we describe the problem further, let's start with some motivation for solving this problem.

Suppose we're dealing with a very large number of independent objects …




CSE 143 Final Project: Classy

Posted in Computer Science

permalink

Table of Contents

Problem Description

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 …




CSE 143 Final Project: Checkers

Posted in Computer Science

permalink

Table of Contents

The Problem

This is a programming challenge that was assigned to some of my CSE 143 students as a final project for their class.

The origin of this problem was the Association of Computing Machinery (ACM)'s International Collegiate Programming Competition (ICPC), in particular the Pacific Northwest Regional Competition, Division 1 challenges from 2015.

Link to Pacific NW ACM ICPC page.

Problem Description: Checkers

In the Checkers problem …




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   


The Z-Machine: A Simple Turing Machine

Posted in Computer Science

permalink

Table of Contents

Background

Recently I discovered the wonderful blog of John Graham-Cumming. One of hist posts, from 2013, details a question that he had to answer for the Oxford University Department of Computer Science's "interviews" (which, I believe, are a kind of final …



Tags:    turing machine    computer science    computer engineering    apollo    assembly   


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