Tag: computer science


A Few of My Favorite PEPs

Posted in Python

permalink

Table of Contents



What's your favorite PEP?

PEPs, or Python Enhancement Proposals, are documents in which features, additions, or general ideas are proposed as additions to the core Python language.

As a Python user, we believe it's important to ask questions like this.

Picking a "favorite PEP" is not just about having a ready and clever answer to a question you might expect in a technical interview; the PEP documents really are important, and really do …



Tags:    python    pep    computer science    programming   


D3 Calendar Visualizations

Posted in Javascript

permalink

Table of Contents



Starting example

Let's begin with a D3 example. Mike Bostock provided a Calendar View block illustrating how to draw a very interesting visualization of large amounts of data over time:

You might recognize this type of graph from Github, whose activity graph shows the same visualization.

The data shown in this example consists of several years of stock market data. It is a simple but very large data set, with each data …



Tags:    javascript    d3    computer science    python    colors   


Project Euler Problem 172

Posted in Mathematics

permalink

Table of Contents



Overview: Problem 172

How many 18-digit numbers \(n\) (without leading zeros) are there such that no digit occurs more than three times in \(n\)?

Link to Project Euler Problem 172

Background

Project Euler Problem 172 is your classic Project Euler problem: short, simple, and overwhelmingly complicated.

To nail this one, it's important to start simple - very simple. What I'll do is walk through the process of …



Tags:    computer science    mathematics    factors    sequences    euler    project euler   


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   


Mad Combinatoric Castles

Posted in Mathematics

permalink

Table of Contents

Overview: The Problem

In an earlier post, I mentioned my efforts on Project Euler problems and the wide variety of problems there that can offer some profound mathematical insights.

Given that the first post covered Project Euler problem 1, I thought it would be nice if the next problem cranked up the difficulty factor by an order of magnitude. Project Euler Problem 502 is a very hairy combinatorics problem that required me to learn about a wide variety of combinatorial enumeration techniques.

Let's start with …



Tags:    computer science    mathematics    factors    sequences    project euler   


Project Euler Problem 1

Posted in Mathematics

permalink

Table of Contents

Overview: The Problem

Project Euler is a website that provides mathematically-oriented programming problems. There are many (over 500) and they are a rich source of profound mathematical insights.

I have been considering a writeup that goes deep into a particular problem, so why not do it with problem 1?

Problem 1 of Project Euler asks:

Find the sum of all the multiples of 3 or 5 below 1000.

It is a pretty simple task - one of the first things covered in a decent programming course is the …



Tags:    computer science    mathematics    factors    sequences    euler    project euler   


Shortest Lattice Paths and Multiset Permutations

Posted in Mathematics

permalink

Table of Contents

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right …




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 …



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 …




Traveling Schoolteacher Problem

Posted in Java

permalink

The Traveling Schoolteacher Problem

The Traveling Schoolteacher Problem (TSTP) is a variation on the Traveling Salesperson Problem (TSP).

The Traveling Schoolteacher Problem supposes a schoolteacher that is traveling from school to school in order to give lessons at different schools. Being a poor schoolteacher, they are only able to afford an older car that gets bad mileage and has a small gas tank.

After visiting each school …



Tags:    computer science    guava    graph    TSP   


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   


Better Timing of Guava Traveling Salesperson Problem Code: Timing Scripts

Posted in Java

permalink

Before We Begin: The Code

Note that all of the code discussed/shown in this post is available from the traveling salesperson problem repository on git.charlesreid1.com. The guava/ directory contains the guava solution to the traveling salesperson problem, along with the timing scripts discussed below, and several example output files.

Introduction

Timing a piece …



Tags:    computer science    command line    guava    graph    TSP    make    awk    performance   


Fixing Bottlenecks in the Guava Traveling Salesperson Problem Code

Posted in Java

permalink

Intro

In a prior blog post we introduced you to the traveling salesperson problem (TSP), which involves finding the shortest path through every city in a group of cities connected by a network of roads. Using Google Guava, we have implemented a solution to the TSP in Java.

Our philosophy toward timing, profiling, and optimization is that it is always best to work from data - and timing …



Tags:    computer science    guava    graph    TSP    performance   


Solving the Traveling Salesperson Problem with Java and Guava

Posted in Java

permalink

Tags:    computer science    guava    graph    TSP